이번 포스팅에서는 가장 대표적인 자료구조인 스택(Stack)과 큐(Queue)에 대해 알아보고자 한다.
1. 📚 스택(Stack)이란?
스택(Stack)은 가장 나중에 들어온 데이터가 가장 먼저 나가는 구조를 가진 자료구조이다.
이를 후입선출(LIFO, Last In First Out) 구조라고 한다.
1.1 ✔️ 기본 연산
스택은 다음과 같은 핵심 연산을 가진다.
-
push : 데이터를 스택에 삽입
-
pop : 가장 위에 있는 데이터를 제거
-
peek (또는 top) : 가장 위의 데이터를 확인하는 연산
-
empty : Stack이 비어있는지 확인하는 메서드
👉 모든 연산은 스택의 맨 위(top) 에서만 이루어진다.
1.2 특징
- 후입선출 구조(LIFO)
- 리스트의 한쪽으로 삽입과 삭제 연산 수행
1.3 ✅ 스택의 사용 사례 (후입선출)
- 웹 방문기록 뒤로가기
- 실행 취소(undo)
- 역 문자열 만들기
1.4 💻 구현 코드 (연결 리스트 활용)
class Stack:
def __init__(self):
self.items = []
def push(self, data):
self.items.append(data)
def pop(self):
if self.isEmpty():
print("Stack is Empty")
return None
return self.items.pop()
def peek(self):
if self.isEmpty():
print("Stack is Empty")
return None
return self.items[-1]
def isEmpty(self):
return len(self.items) == 01.5 📌 [프로그래머스] 올바른 괄호 - 스택(Stack)을 활용한 풀이 (Lv.2)
구현 코드
class Stack:
def __init__(self):
self.items = []
def push(self, data):
self.items.append(data)
def pop(self):
if self.isEmpty():
return 0
return self.items.pop()
def isEmpty(self):
return len(self.items) == 0
def solution(s):
stack = Stack()
for char in s:
if char == '(':
stack.push(char)
elif char == ')':
if stack.isEmpty():
return False
stack.pop()
return stack.isEmpty()2. 📚 큐(Queue)란?
큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 구조를 가진 자료구조이다.
식당의 대기열이나 매표소에서 줄을 서는 모습을 생각하면 이해하기 쉽다. 이를 선입선출(FIFO, First In First Out) 구조라고 한다.
2.1 ✔️ 기본 연산
큐는 다음과 같은 핵심 연산을 가진다.
-
enqueue : 큐의 뒤쪽(Rear)에 새로운 데이터를 삽입
-
dequeue : 큐의 앞쪽(Front)에서 데이터를 제거하고 반환
👉 스택과 달리 삽입은 뒤(Rear) 에서, 삭제는 앞(Front) 에서 양방향으로 이루어지는 것이 특징이다.
2.2 ✔️ 특징
- 선입선출 구조(FIFO)
- 입구와 출구가 다름 (데이터가 들어오는 곳과 나가는 곳이 분리되어 있음)
2.3 ✅ 큐의 사용 사례
- 프린터의 인쇄 대기열
- 콜센터 고객 대기시간 (먼저 전화한 고객부터 상담)
- 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘
- 운영체제의 프로세스 스케줄링
💻 구현 코드 (연결 리스트 활용)
스택에서 사용한 Node 클래스를 그대로 활용하여 큐를 구현할 수 있다.
class Queue:
def __init__(self):
self.items = []
def enqueue(self, data): # 데이터 추가
self.items.append(data)
def dequeue(self): # 데이터 제거 (앞에서)
if self.isEmpty():
print("Queue is Empty")
return None
return self.items.pop(0)
def peek(self): # 맨 앞 요소 확인
if self.isEmpty():
print("Queue is Empty")
return None
return self.items[0]
def isEmpty(self):
return len(self.items) == 0
3. deque 라이브러리
앞서 파이썬의 기본 리스트(List)를 활용하여 큐를 구현하고 pop(0)을 사용해 데이터를 맨 앞에서 빼내었다. 하지만 이 방식에는 아주 치명적인 단점이 있다.
파이썬의 리스트 구조상 맨 앞의 데이터를 빼내면, 그 뒤에 있는 수많은 데이터들이 모두 한 칸씩 앞으로 이동해야 한다. 이로 인해 시간 복잡도가 이 되어 데이터가 많을수록 속도가 기하급수적으로 느려진다.
이를 해결하기 위해 파이썬 내장 라이브러리인 collections.deque를 사용한다.
데크(deque)는 Double-Ended Queue의 약자로, 큐의 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 이중 연결 큐 자료구조이다. 기차 칸처럼 연결된 구조를 띄고 있어, 양 끝의 데이터를 넣거나 뺄 때 시간 복잡도가 로 압도적으로 빠르다.
3.1 핵심 연산
- append(x) : 데크의 오른쪽에 데이터를 삽입한다.
- popleft(x) : 데크의 왼쪽에서 데이터를 제거하고 반환한다.
- appendleft(x) : 데크의 왼쪽에 데이터를 삽입한다.
- pop() : 데크의 오른쪽에서 데이터를 제거하고 반환한다.
