스택(stack)

ADT(Abstract Data Type)

• 인터페이스만 있고 실제로 구현은 되지 않은 자료형
  • 연산시 해야 할 동작과, 상태가 가지고 있어야 할 값을 정의하지만 세부 구현은 되어있지 않음.
• 언어에 따라 표준 라이브러리에서 스택을 제공하기도, 안하기도 함

스택의 ADT

구분	정의	설명
연산	boolean isFull()	스택에 들어있는 데이터 개수가 maxsize인지 확인 -> true/false
연산	boolean isEmpty()	스택에 데이터가 하나도 없는지 확인 -> true/false
연산	void push(ItemType item)	스택에 데이터를 푸시
연산	ItemType pop()	마지막으로 푸시한 데이터를 팝하고, 리턴. 최초 위치가 0이므로 데이터가 없으면 -1로 표현.
상태	int top	스택에서 마지막으로 푸시된 데이터의 위치
상태	ItemType data[maxsize]	스택의 데이터를 관리하는 배열. 최대 maxsize개의 데이터를 관리.

• 파이썬의 경우 스택을 제공하지 않지만 대안으로 리스트의 append(), push()를 이용하여 대체할 수 있음
  • 덱(deque)은 한쪽만 삽입 삭제가 가능한 스택과 달리 양쪽에서 삽입 삭제가 가능하므로, 응용하면 스택처럼 사용할 수 있음
  • 스택의 원소는 반드시 배열이 아닌 다른 자료구조로도 관리할 수 있음

스택의 세부 동작

push(3)을 호출하는 과정

• isFull() 을 사용하여 스택이(data 배열이) 가득 찼는지 확인
• 가득 차지 않았다면, top을 1만큼 증가
• top이 가리키는 위치의 data[n]=3을 추가

pop()을 호출하는 과정

• isEmpoty() 함수를 수행하여 data배열이 비어있는지 확인
• 데이터가 있다면 top을 1만큼 감소. 감소한 값이 -1이라면 스택은 비어있는 것으로 취급.
• data[n] = 3이므로 3을 반환

스택 구현하기

• 순서와 상관 없이 임의 접근하는 경우는 배열을 사용해도 무관하지만, 최근에 삽입한 데이터를 다루는 경우라면 스택을 고려해야 함.
• 파이썬의 리스트를 사용하는 경우에는 크기가 동적으로 관리돠고 append(), pop(), push() 함수를 이용할 수 있어 top변수를 별도로 관리할 필요가 없음
  • stack[-1]을 하면 리스트의 마지막 요소를 바로 얻을 수 있음
  • push나 pop이 호출될 때 마다 top값을 갱신하는 로직이 추가로 처리되어야 하므로 리스트를 사용하는 경우라면 복잡도 측면에서 중복, 비효율적임.
• 배열로 스택을 구현하려는 경우에는, 크기가 고정되어 있으므로 어느 위치에서 연산을 수행할지 명확히 관리해야 하므로 top변수를 별도 관리.

stack = []
max_size = 10


 def isFull(stack):
    return len(stack) == max_size

def isEmpty(stack):
    return len(stack) == 0

def push(stack, item):
    if isFull(stack):
        print("Stack is full")
    else:
        stack.append(item)
        print("Pushed item: ", item)

def pop(stack):
    if isEmpty(stack):
        print("Stack is empty")
        return None
    else:
        return stack.pop()

여기서 파이썬의 리스트의 특성을 이용하여 조금 더 개선해보자면

• 크기를 동적으로 관리하므로 사실상 max_size, isFull(), isEmpty()가 필요 없음
• push() ,pop()의 실질적 동작은 리스트의 append(), pop()을 호출하는 것 뿐이므로 함수로 처리될 필요도 없음

stack = []

stack.append(1)
stack.append(2)
stack.append(3)

top_element = stack.pop()
next_element = stack.pop()

stack_size = len(stack)

이렇게 되면 사실상 리스트를 스택 그 자체로 활용할 수 있게 되며, 파이썬의 리스트와 스택을 구분하는 것은 거의 의미가 없어보임.