- 삽입(Push): 항상 맨 위(top)에 추가 — \(O(1)\)
- 추출(Pop): 항상 맨 위(top)에서 제거 — \(O(1)\)
- 최상위 조회(Top): 제거 없이 top 원소 확인 — \(O(1)\)
- 다양한 알고리즘과 프로그램에서 사용됨
- 스택: 먼저 들어온 데이터가 나중에 나가는 자료구조
- 흔히 박스가 쌓인 형태를 스택(stack)이라고 한다. 예) ‘Deep Learning 알고리즘의 구조가 stacked 되어 있는 구조다’ 라고 표현
- 우리가 박스를 쌓은 뒤에 꺼낼 때는, 가장 마지막에 올렸던 박스부터 꺼내야 한다.
- 새로운 원소를 삽입할 때는 마지막 위치에 삽입한다. (가장 최근에 삽입된 원소가 가장 끝에 위치)
- 새로운 원소를 삭제할 때는 마지막 원소가 삭제된다. (가장 최근에 삽입된 원소가 제거됨)
- head = 최상위 원소 = 가장 최근에 삽입이된 원소
- 함수 호출 스택(call stack): 재귀 함수 호출이 LIFO 방식으로 관리된다.
- 웹 브라우저 뒤로가기: 방문 기록을 스택으로 관리한다.
- 괄호 유효성 검사: 열린 괄호를 스택에 push하고 닫힌 괄호를 pop으로 검증한다.
- DFS(깊이 우선 탐색): 스택 기반으로 구현된다.
- 스택은 굉장히 기본적인 자료구조이다.
- 기계 학습 분야뿐 아니라 다양한 프로그램을 개발할 때 빠지지 않고 사용된다.
- 스택은 여러 가지 연산을 제공한다.
- 파이썬의 기본적인 리스트 자료형은 다음의 두 가지 메서드를 제공한다.
- append() 메서드: 마지막 위치에 원소를 삽입하며, 시간 복잡도는 \(O(1)\) 이다.
- pop() 메서드: 마지막 위치에서 원소를 추출하며, 시간 복잡도는 \(O(1)\) 이다.
- 따라서 일반적으로 스택을 구현할 때, 파이썬의 리스트(list) 자료형을 사용한다.
- Python의
list는 스택으로 바로 사용할 수 있다:arr.append(x)/arr.pop() - 두 메서드 모두 \(O(1)\) 이므로 별도의 Stack 클래스 구현이 불필요한 경우가 많다.
arr[-1]로 top 원소를 꺼내지 않고 확인할 수 있다.- 스택을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 \(O(1)\) 을 보장한다.
- 연결 리스트로 구현할 때는 머리(head)를 가리키는 하나의 포인터만 가진다.
- 머리(head): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터
- 삽입할 때는 기존의 머리 뒤에 데이터가 들어가고 포인터가 가장 최근에 삽입된 데이터를 가리키도록 머리(head) 위치를 바꿔준다.
- 삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.
- 즉, 포인터를 삭제할 데이터에 앞에 있는 데이터로 머리 위치를 바꾸는 것만으로 삭제는 이루어진다.
- 삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.
- 함수 호출 스택(Call Stack): 함수가 호출될 때마다 스택 프레임이 쌓이고, 반환 시 제거된다. 재귀 함수의 동작 원리이다.
- 괄호 유효성 검사:
(,[,{를 push하고 닫는 괄호가 나오면 pop하여 매칭을 확인한다. - 웹 브라우저 뒤로가기: 방문 페이지를 스택에 쌓아 뒤로가기 시 pop한다.
- DFS(깊이 우선 탐색): 방문할 노드를 스택에 넣어 깊이 우선으로 탐색한다.
- 수식 계산기: 후위 표기법(Postfix) 연산에서 피연산자를 스택으로 관리한다.
1 Stack
정의: 스택 (Stack)
스택은 마지막에 삽입된 데이터가 가장 먼저 제거되는 LIFO(Last-In, First-Out) 자료구조다.
직관적 이해: 식당 주방의 접시 더미와 같다. 새 접시는 항상 맨 위에 올리고(Push), 꺼낼 때도 항상 맨 위에서 꺼낸다(Pop). 바닥의 접시를 꺼내려면 위의 접시를 모두 치워야 한다.
동작 원리 (시각화):
초기 push(7) push(2) pop() pop()
┌───┐ ┌───┐
│ 7 │ │ 2 │ ┌───┐
└───┘ │ 7 │ │ 7 │
└───┘ └───┘
(빈 스택) top=7 top=2 top=7 (빈 스택)
2 왜 필요한가
3 스택 자료구조의 중요성
4 스택 자료구조의 시간 복잡도
| Number | Methods | Time Complexity | Description |
|---|---|---|---|
| 1 | 삽입(Push) | \(O(1)\) | 스택에 원소를 삽입하는 연산 |
| 2 | 추출(Pop) | \(O(1)\) | 스택에서 원소를 추출하는 연산 |
| 3 | 최상위 원소 (Top) | \(O(1)\) | 스택의 최상위 원소(마지막에 들어온 원소) 를 확인(조회)하는 연산 |
| 4 | Empty | \(O(1)\) | 스택이 비어 있는지 확인하는 연산 |
See 표 1.
5 Python에서 스택을 구현하는 방법 1: 리스트 자료형
아래 코드는 Python list를 이용해 스택을 구현한다. append()가 push, pop()이 pop 역할을 한다.
class Stack:
def __init__(self):
self.stack = []
def push(self, data):
# 마지막 위치에 원소 삽입
self.stack.append(data)
def pop(self):
if self.is_empty():
return None
# 마지막 원소 추출
return self.stack.pop()
def top(self):
if self.is_empty():
return None
# 마지막 원소 반환
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
stack.push(x)
while not stack.is_empty():
print(stack.pop())
# 출력:
# 2
# 4
# 6
# 5
# 2
# 7
# 9
핵심 포인트
6 연결 리스트로 스택 구현하기
연결 리스트로 구현한 스택은 동적 메모리를 사용하여 크기 제한이 없다. head 포인터가 스택의 top을 가리킨다.
6.1 삽입 연산
6.2 삭제 연산
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
# 원소 삽입
def push(self, data):
node = Node(data)
node.next = self.head
self.head = node
# 원소 추출하기
def pop(self):
if self.is_empty():
return None
# 머리(head) 위치에서 노드 꺼내기
data = self.head.data
self.head = self.head.next
return data
# 최상위 원소(top)
def top(self):
if self.is_empty():
return None
return self.head.data
# 먼저 추출할 원소부터 출력
def show(self):
cur = self.head
while cur:
print(cur.data, end=" ")
cur = cur.next
# 스택이 비어있는지 확인
def is_empty(self):
return self.head is None
stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
stack.push(x)
stack.show()
print()
while not stack.is_empty():
print(stack.pop())
# 출력:
# 2 4 6 5 2 7 9
# 2
# 4
# 6
# 5
# 2
# 7
# 9