[Python] - 자료구조 : 스택(Stack) 개념 및 사용

* Stack(스택)

• 스택은 LIFO(Last - In - First - Out)로써 가장 나중에 들어온 자료가 가장 먼저 꺼내어진다라고 이해하면 쉽다.

 

1. 정의

• 스택은 데이터를 한 쪽 끝에서만 넣고 뺄 수 있는 자료 구조이다.
• 큐는 대표적으로 FIFO 정책을 사용하지만 스택은 LIFO(Last In First Out) 후입선출 정책을 사용한다.
• 즉 가장 나중에 쌓은 데이터를 가장 먼저 제거할 수 있다. 또한 단어 그대로 쌓아 올린다는 것을 뜻한다.
• 프링글스 과자를 생각하면 쉽다.

 

2. 스택의 장단점

• -장점 
  
  • 구조가 단순해서 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.
• -단점
  
  • 스택에 데이터를 쌓을 수 있는 최대 범위를 미리 정해놓아야한다.
  • 이로인해 저장 공간의 낭비가 발생할 수 있다.

 

3. 스택의 메서드

파이썬 리스트 기능에서 스택은 두 가지 메서드를 제공한다.

- append(push) : 데이터를 집어넣기

- pop : 데이터를 빼기

 

4. 스택의 쓰임

- 웹브라우저의 방문기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기
- 실행 취소(undo)

 

* Python에서 Stack 구현하기

Python에서는 기본 클래스인 list를 통해 스택 자료구조를 쉽게 구현할수있다.

 

list pop / push 시간복잡도

pop Item	list.pop( )	O(1)
push Item	list.append(item)	O(1)

 

** list를 이용하여 Stack 구현하기 - 1

stack - Init

list는 파이썬에서 자주 쓰이기 때문에 리스트 자료형 생성은 매우 익숙할거같다.

stack = [] # []

stack = [1,2,3] # [1,2,3]

 

stack - push

스택에 원소를 넣을 때에는 append 메소드를 이용해 리스트의 가장 마지막에 원소를 넣으실 수 있다.

stack = []
stack.append(4) # [4]
stack.append(2) # [4,2]

 

stack - pop

스택에 원소를 제거할 때는 pop 메소드를 이용하여 리스트의 가장 마지막 원소를 제거한다.

이때 pop메소드에 의해 제거된 원소를 리턴 받는다.

리스트의 pop(0) 연산은 O(n) 시간 복잡도를 가진다. 즉, 리스트의 첫 번째 요소를 제거하면, 나머지 모든 요소를 왼쪽으로 이동해야 하기 때문에 큐의 크기가 커질수록 성능이 저하된다.

stack = [1,2,3,4]
top = stack.pop() # stack [1,2,3]

print(top) # 4

 

stack - top

스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1]을 이용하여 찾을 수 있다.

stack = [1,2,3,4]
top = stack[-1]# 4 , stack [1,2,3,4]

print(top) # 4

 

 

** deque를 사용하여 스택 구현하기 - 2

 

from collections import deque

stack = deque()

# 스택에 요소 추가 (push)
stack.append(1)
stack.append(2)
stack.append(3)

print(stack)  # deque([1, 2, 3])

# 스택에서 맨 뒤의 요소 제거 (pop)
top_element = stack.pop()
print(top_element)  # 3
print(stack)  # deque([1, 2])

# 스택에서 맨 앞의 요소 제거 (popleft)
print(queue.popleft())  # 1
print(queue.popleft())  # 2
print(queue.popleft())  # 3

 

• append(): 스택의 맨 위에 요소를 추가한다.
• pop(): 스택의 맨 위에서 요소를 제거하고 반환한다.
• popleft() : 스택의 맨 앞의 요소를 제거하고 반환한다. O(1) 시간 복잡도를 가지며, 이는 리스트의 pop(0)보다 훨씬 효율적이다. 따라서 큐의 크기가 커져도 성능이 일정하게 유지된다.