[DataStructure] Stack

Stack (스택)

• 선형구조

• LIFO (Last In First Out)

• 데이터 추가 및 제거를 하나의 방향으로만 가능

Method

• push : 임의의 데이터 추가

• pop : 최상단의 데이터 꺼낸 뒤 해당값 반환

• get_top : 최상단에 위치하는 값 반환

• get_size : 데이터 갯수 (사이즈) 반환

• is_empty : 비어있는지 유무 반환 (bool)

Python Implementation Code

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None  # prev == previous
        

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0
    
    def push(self, data):
        new = Node(data)  # 새로운 node 인스턴스 생성
        new.prev = self.top  # 새로생긴 node 인스턴스의 prev(previous)에 현재 top 연결
        self.top = new  # top 이 새로운 node 인스턴스를 참조하도록 지정
        self.size += 1  # Stack 의 크기 1 증가
    
    def pop(self):
        if not self.is_empty():
            tmp = self.top.data  # 현재 top 을 반환가능하도록 임시 변수에 값 할당
            self.top = self.top.prev  # top 이 현재 top 의 prev(previous) 값을 참조하도록 지정
            self.size -= 1  # Stack 의 크기 1 감소
            return tmp  # 저장해두었던 tmp 를 반환
        else:
            print('Empty Stack')
    
    def get_top(self):
        if not self.is_empty():
            return self.top.data
        else:
            print('Empty Stack')
    
    def get_size(self):
        return self.size
             
    def is_empty(self):
        return False if self.get_size() else True

push

새로운 노드 new 인스턴스를 생성한 뒤
new 의 prev (new.prev)가 현재 top 을 참조하도록 하는 것이 우선되어야한다.
Stack 의 top 을 new 로 먼저 할당할 경우 이전의 top 을 참조할 수가 없어지기 때문이다.

pop

Stack 의 top 이 self.top.prev 를 참조하도록 하는 것으로
이전 top 이었던 Node 인스턴스는 제거된다. (해당 인스턴스를 참조하는 값이 없기 때문)
제거된 값을 반환할 수는 없기 때문에 제거하기전 tmp 에 self.top.data 값을 저장해둔 뒤, 마지막에 반환한다.