스택(Stack)은 LIFO(Last In First Out, 후입선출) 방식으로 동작하는 선형 자료구조입니다. 즉, 가장 먼저 들어간 요소가 가장 마지막에 처리되며, 가장 나중에 들어간 요소가 가장 먼저 꺼내집니다.
스택의 이해를 돕는 예시
스택 자료구조는 접시를 쌓아 놓은 모습으로 쉽게 이해할 수 있습니다.
접시를 한 장씩 위로 포개어 쌓는다고 생각해 봅시다. 가장 처음 놓인 접시는 맨 아래에 위치하고, 가장 나중에 놓인 접시는 맨 위에 놓이게 됩니다. 접시가 필요할 때 우리는 항상 맨 위에 있는 접시, 즉 가장 나중에 올려놓은 접시를 집게 됩니다. 반대로 맨 처음 놓았던 접시는 가장 마지막에야 사용할 수 있습니다. 이처럼 스택은 나중에 들어온 것이 먼저 나가는 LIFO 원리를 따릅니다.
파이썬에서 스택 구현하기
파이썬에서는 다른 선형 자료구조나 표준 라이브러리의 내장 모듈을 활용해 스택을 다양한 방식으로 구현할 수 있습니다. 대표적인 세 가지 방법을 살펴보겠습니다.
방법 1 − 리스트(list)로 구현
파이썬의 기본 자료형인 리스트를 사용하면 간단히 스택을 구현할 수 있습니다. 다만 리스트를 활용한 구현은 성능 면에서 효율적이지 않기 때문에 실무에서는 권장되지 않습니다.
주요 연산
append() − 스택의 끝(맨 위)에 새로운 요소를 추가합니다.
pop() − 스택의 마지막(맨 위) 요소를 제거하고 반환합니다. 요소는 LIFO 순서로 꺼내집니다.
예제 코드
stack=[]
stack.append(1)
stack.append(2)
stack.append(3)
print("Intial Stack",stack)
print("Element popped from the stack")
print(stack.pop())
print(stack.pop())
print("Stack after popping some elements",stack)실행 결과
Intial Stack [1, 2, 3] Element popped from the stack 3 2 Stack after popping some elements [1]
주의할 점은, 스택이 비어 있는 상태에서 더 이상 요소를 제거하려고 하면 예외가 발생한다는 것입니다.
stack.pop() IndexError: pop from empty list
방법 2 − queue.LifoQueue로 구현
파이썬 내장 모듈인 queue의 LifoQueue 클래스를 사용하는 방법입니다. queue 모듈에서 LifoQueue를 임포트한 뒤, 원하는 크기를 지정하여 초기화할 수 있습니다. 크기를 0으로 설정하면 무제한 용량의 스택이 됩니다.
주요 연산
maxsize − 스택에 허용되는 최대 요소 개수입니다.
get() − 스택의 마지막(맨 위) 요소를 제거하고 반환합니다. 스택이 비어 있으면 요소가 하나 이상 들어올 때까지 대기합니다.
get_nowait() − 스택의 마지막 요소를 제거하고 반환합니다. 스택이 비어 있으면 예외를 발생시킵니다.
put(item) − 스택의 끝에 요소를 추가합니다. 스택이 가득 차 있으면 빈 공간이 생길 때까지 대기합니다.
put_nowait(item) − 스택의 끝에 요소를 추가합니다. 스택이 가득 차 있으면 예외를 발생시킵니다.
full() − 스택이 가득 차 있으면 True, 아니면 False를 반환합니다.
empty() − 스택이 비어 있으면 True, 아니면 False를 반환합니다.
qsize() − 스택에 현재 들어 있는 요소의 개수를 반환합니다.
예제 코드
from queue import LifoQueue
s=LifoQueue(maxsize=3)
s.put(1)
s.put(2)
s.put(3)
print("Is stack full",s.full())
print("Element popped from the stack")
print(s.get())
print(s.get())
print("Number of elements in stack",s.qsize())
print("Is stack empty",s.empty())실행 결과
Is stack full True Element popped from the stack 3 2 Number of elements in stack 1 Is stack empty False
방법 3 − collections.deque로 구현
세 번째 방법은 collections 모듈의 deque(덱)를 활용하는 것입니다. deque는 양방향 삽입과 삭제가 가능한 자료구조로, 스택 구현 시 우수한 성능을 보여줍니다.
주요 연산
append() − 스택의 끝에 새로운 요소를 추가합니다.
pop() − 스택의 마지막 요소를 O(1) 시간 복잡도로 제거하고 반환합니다.
예제 코드
from collections import deque
stack=deque()
stack.append(1)
stack.append(2)
stack.append(3)
print("Intial stack: ",stack)
print("Element popped from the stack")
print(stack.pop())
print(stack.pop())
print("Stack after popping some elements: ",stack)실행 결과
Intial stack: deque([1, 2, 3]) Element popped from the stack 3 2 Stack after popping some elements: deque([1])
마찬가지로, 비어 있는 deque에 pop() 함수를 호출하면 예외가 발생합니다.