[자료구조] 스택(Stack)

스택(Stack)은 한 쪽 끝에서만 자료를 추가/반환/삭제할 수 있는 후입선출(LIFO - Last In First Out) 형식의 선형 자료구조이다.
stack은 '어떤 물체들이 쌓아올려진 더미'를 뜻한다.

가령 접시를 잔뜩 쌓아올릴 때, 가장 처음 올려둔 접시는 맨밑에 위치한다.
접시를 뺄 때는 맨위 접시(top)를 빼게 되며, 이는 가장 마지막에 올려둔 것이다.
(접시를 쌓음 = 데이터 추가 = push,  접시를 뺌 = 데이터 반환 = pop)

---

핵심 연산

• push(item) : 스택 맨위에 데이터 삽입
• pop() : 스택 맨위 데이터 삭제 및 반환
• top() : 스택 맨위 데이터 반환
• size() : 스택 크기 반환
• empty() : 스택이 비었는지 여부 반환
• full() : 스택이 가득 찼는지 여부 반환

참고 :
꽉 찬 스택에 push하려는 경우를 오버플로우(Overflow), 텅 빈 스택에서 pop하려는 경우를 언더플로우(Underflow)라고 한다.

---

스택의 활용

• 콜 스택(Call Stack) :
  컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조
• 컴파일러가 출력하는 에러도 맨마지막 에러가 가장 먼저 출력
• 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어의 이름
• 가장 마지막에 실행했던 명령어 취소 (Ctrl + Z)

---

구현 [Python]

1. 배열(Array)

class Stack:
    maxlen = 10

    def __init__(self):
        self.tos = 0
        self.array = [None] * self.maxlen

    def push(self, item):
        if not self.full():
            self.array[self.tos] = item
            self.tos += 1

    def pop(self):
        if not self.empty():
            self.tos -= 1
            return self.array[self.tos]

    def top(self):
        return self.array[self.tos - 1]

    def size(self):
        return self.tos

    def empty(self):
        return self.size() == 0

    def full(self):
        return self.size() == self.maxlen

2. 연결 리스트(Linked List)

class Node:
    def __init__(self, item, link=None):
        self.item = item
        self.link = link

class Stack:
    maxlen = 10

    def __init__(self):
        self.tos = None
        self.length = 0

    def push(self, item):
        if not self.full():
            self.tos = Node(item, self.tos)
            self.length += 1

    def pop(self):
        if not self.empty():
            item = self.tos.item
            self.tos = self.tos.link
            self.length -= 1
            return item

    def top(self):
        return self.tos.item

    def size(self):
        return self.length

    def empty(self):
        return self.size() == 0

    def full(self):
        return self.size() == self.maxlen

만약 위 코드에서 1, 2, 3, 4, 5를 차례로 push하면 구현된 스택은 아래와 같은 상태를 나타내고 있을 것이다.