본문 바로가기
Algorithm

스택(stack)

by isn`t 2024. 9. 7.

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)

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

'Algorithm' 카테고리의 다른 글

재귀(recursive)  (3) 2024.09.15
배열  (8) 2024.09.01
데이터 타입, 앱실론, 함수, 람다표현식  (0) 2024.08.24
시간 복잡도와 빅오 표기법  (0) 2024.08.17