[파이썬 자료구조] 스택의 개념, 특징 (리스트, 디큐로 구현)

0. 스택의 정의

• 스택은 FILO(선입후출) 또는 후입선출(LIFO) 방식으로 아이템을 저장하는 선형 데이터 구조이다.
• 스택에서는 한쪽 끝에 새로운 원소가 추가되고, 그 끝에서만 원소가 삭제된다.
• 이러한 작업을 push 및 pop이라고 한다.
• 쉽게 설명하면 박스는 아래에서 위로 쌓고, 아래 박스를 치우기 위해서는 위에서부터 박스를 내린다.

 

1. 스택에서 지원하는 함수

• empty() : 스택이 비어있는지 리턴한다. [시간복잡도 O(1)]
• size() : 스택의 크기를 리턴한다.  [시간복잡도 O(1)]
• top() / peek() : 스택의 제일 윗부분 원소의 참조를 리턴한다. [시간 복잡도 O(1)]
• push(A) : 스택의 제일 윗 부분에 A라는 원소를 추가한다. [시간 복잡도 O(1)]
• pop() : 스택의 제일 윗부분을 삭제한다. [시간복잡도 O(1)]

 

 

2. 파이썬에서 스택의 활용용도

파이썬에서 스택은 다양한 용도로 변형되어 사용될 수 있다.

• list
• Collections.deque
• queue.LifoQueue

 

 

3. 스택을 리스트로 구현

 

3-1 스택을 리스트로 구현할 때 특징

• 리스트의 크기가 커질수록 속도가 느려질 수 있다.
• 리스트에서 각 아이템들은 메모리에 서로 옆에 저장되어 있으며, 스택이 만약 메모리 블록의 크기보다 커질 경우 파이썬은 메모리 할당을 추가적으로 해야 한다. 
• 이로 인해 append() 호출이 다른 함수들보다 느려질 수도 있다. 

 

3-2 스택을 리스트로 구현한 코드

stack = []

stack.append(2)
stack.append(4)
stack.append(7)

#delete stack top element (delete 7) 
stack. pop()  

print(stack)
print(stack[::-1])

Output :

[2, 4]

[4, 2]

 

 

4. 스택을 디큐로 구현

 

4-1 스택을 디큐로 구현할 때 특징

• 파이썬으로 큐로 구현할 때는 Coleections.deque를 사용한다.
• deque는 스택과 큐의 장점을 모두 채택한다.
• 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이다. [시간 복잡도 O(1)]
• queue 라이브러리를 이용하는 것보다 더 간단한다.

 

4-2 스택을 디큐로 구현한 코드

from collections import deque

#큐 구현을 위해 deque 라이브러리 사용
stack = deque()

stack.append(5)
stack.append(3)
stack.append(4)

#제일 왼쪽 원소 삭제 (5 삭제)
stack.popleft()
print(stack)

#LIFO 후입선출로 4, 3 순서로 나옴
print(stack.pop())
print(stack.pop())

Output :

deque([3, 4])

4

3

 

 

 

 

 

참조

https://www.geeksforgeeks.org/stack-in-python/