[Python] 자료구조(Data Structure) / 3. 스택(Stack) / 4. 큐(Queue) / 5. 데크(Deque)

genie0000 2025. 4. 24. 02:26

선형구조

3. 스택 (Stack)

스택(Stack)은 LIFO (Last In, First Out) 구조
→ 즉, 마지막에 넣은 데이터가 가장 먼저 나오는 자료구조

✅ 주요 연산

연산 이름	설명
push(x)	x를 스택에 추가
pop()	스택의 가장 마지막에 있는 값 제거하고 반환
peek() 또는 top()	스택의 가장 마지막 값 보기만 함 (제거 안 함)
isEmpty()	스택이 비어 있는지 확인
size()	스택에 있는 요소의 개수

✅ 시간 복잡도

연산	시간 복잡도
push, pop, peek	O(1) (매우 빠름!)

✅ 스택 사용 예

접시 쌓기, 책 더미, 웹 브라우저의 '뒤로 가기' 버튼
→ 가장 마지막에 넣었던 것부터 꺼냄

✅ 스택 구현 (Python)

리스트를 사용하여 구현

stack = []

# push
stack.append(10)
stack.append(20)

# pop
print(stack.pop())   # 20
print(stack.pop())   # 10

# isEmpty
print(len(stack) == 0)  # True

collections.deque로 구현 (더 빠르고 안정적)

from collections import deque

stack = deque()
stack.append(10)
stack.append(20)
print(stack.pop())  # 20

✅ 스택이 사용되는 대표적인 예

예시	설명
괄호 검사	({[ ]}) 올바른 괄호인지 확인
웹 브라우저 '뒤로 가기'	방문한 페이지들을 스택에 저장
DFS (깊이 우선 탐색)	스택으로 구현
계산기 (후위 표기법)	스택으로 연산 수행
재귀 함수	내부적으로 스택 사용 (콜 스택)

✅ 스택을 배워야 하는 이유

알고리즘 문제 풀이에 자주 등장
다른 자료구조나 알고리즘의 기반
재귀 함수와 밀접한 관계

4. 큐 (Queue)

큐(Queue)는 FIFO (First In, First Out) 구조

→ 즉, 먼저 들어간 데이터가 먼저 나오는 자료구조

✅ 주요 연산

연산 이름	설명
enqueue(x)	큐에 x 값을 추가
dequeue()	큐에서 가장 먼저 들어온 값을 제거하고 반환
peek() 또는 front()	큐의 가장 앞(front) 값만 보기 (제거 안 함)
isEmpty()	큐가 비어 있는지 확인
size()	큐에 있는 요소의 개수

✅ 시간 복잡도

연산	시간 복잡도
enqueue, dequeue, peek	O(1) (빠름)

✅ 큐 사용 예

병원 대기실: 먼저 온 사람이 먼저 진료받음
영화관 티켓 판매: 먼저 줄을 선 사람이 먼저 티켓을 받음
프린터 대기열: 먼저 요청한 문서가 먼저 출력됨

✅ 큐 구현 (Python)

리스트를 사용하여 구현

queue = []

# enqueue
queue.append(10)  # 뒤에 추가
queue.append(20)

# dequeue
print(queue.pop(0))  # 10, 맨 앞의 값 제거
print(queue.pop(0))  # 20

리스트를 사용해서 큐를 구현할 수 있지만, pop(0) 연산이 **O(n)**이기 때문에 비효율적일 수 있다.

collections.deque로 구현 (더 빠르고 안정적)

from collections import deque

queue = deque()

# enqueue
queue.append(10)
queue.append(20)

# dequeue
print(queue.popleft())  # 10, 맨 앞의 값 제거
print(queue.popleft())  # 20

deque는 양쪽 끝에서 O(1) 시간 복잡도로 삽입/삭제가 가능하므로 큐 구현에 최적화되어 있다.

✅ 큐가 사용되는 대표적인 예

예시	설명
BFS (너비 우선 탐색)	큐로 구현
운영체제의 프로세스 스케줄링	CPU가 처리할 프로세스를 큐로 관리
웹 서버 요청 처리	클라이언트 요청을 큐에 넣고 순차적으로 처리
메시지 큐 시스템	여러 시스템 간에 메시지를 순차적으로 처리하는 시스템 (예: RabbitMQ, Kafka)

✅ 큐를 배워야 하는 이유

알고리즘에서 자주 등장: BFS, 프로세스 스케줄링 등에서 큐를 사용
효율적인 데이터 처리: 큐는 O(1) 시간 복잡도로 데이터를 처리할 수 있기 때문에 매우 효율적

5. 데크(Deque)

데크(Deque)는 Double-Ended Queue의 줄임말로,
양쪽(앞/뒤)에서 삽입과 삭제가 가능한 자료구조이다.

즉, 데크는 스택과 큐 둘의 장점을 섞은 양방향 자료구조이다.

✅ 주요 연산

메서드	설명
append(x)	오른쪽 끝에 x 추가
appendleft(x)	왼쪽 끝에 x 추가
pop()	오른쪽 끝 요소 제거
popleft()	왼쪽 끝 요소 제거
extend(iterable)	여러 값을 오른쪽에 추가
extendleft(iterable)	여러 값을 왼쪽에 추가 (역순으로 들어감)
rotate(n)	데크를 n만큼 회전 (양수: 오른쪽, 음수: 왼쪽)
reverse()	데크 뒤집기
clear()	모든 요소 제거

✅ 시간 복잡도

연산	시간 복잡도
앞/뒤 삽입, 삭제	O(1)
검색(임의 위치 접근)	O(n)

리스트(list)는 앞쪽 삽입/삭제가 O(n)이지만,
데크는 앞뒤 모두 O(1)이라 양방향 큐나 슬라이딩 윈도우 같은 문제에 매우 유용해.

✅ 데크 구현 (Python)

파이썬에서는 collections.deque 모듈을 사용해서 데크를 구현할 수 있어.
이 모듈은 스레드에 안전하고, **O(1)**의 시간 복잡도로 양쪽에서 삽입/삭제가 가능해!

from collections import deque

dq = deque()

# 뒤쪽에 추가
dq.append(1)
dq.append(2)

# 앞쪽에 추가
dq.appendleft(0)

# 뒤쪽에서 제거
print(dq.pop())       # 2

# 앞쪽에서 제거
print(dq.popleft())   # 0

print(dq)  # deque([1])

✅ 데크 사용 예

슬라이딩 윈도우 문제 (예: 최대값 유지하기)
회전 큐, 양방향 탐색이 필요한 경우
큐처럼 쓰되, 빠른 삽입/삭제가 앞뒤 모두 필요한 경우

✅ 예제: 슬라이딩 윈도우 최대값 문제(데크)

# deque를 이용한 O(n) 슬라이딩 윈도우 최대값
from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    result = []

    for i in range(len(nums)):
        # 범위 밖의 인덱스 제거
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # 현재 값보다 작은 값들 제거
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)

        # 윈도우가 꽉 찼을 때 결과에 추가
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

✅ 스택(Stack) / 큐(Queue) / 데크(Deque) 정리

구조	설명	주요 연산	시간 복잡도	사용 예시
스택 (Stack)	후입선출(LIFO) 구조	push, pop, peek	삽입/삭제: O(1), 조회: O(1)	함수 호출, 브라우저 히스토리
큐 (Queue)	선입선출(FIFO) 구조	enqueue, dequeue, front	삽입/삭제: O(1), 조회: O(1)	프린터 대기열, 프로세스 스케줄링
덱 (Deque)	양방향 큐 (양쪽 끝에서 삽입/삭제 가능)	addFirst, addLast, removeFirst, removeLast	삽입/삭제: O(1), 조회: O(1)	슬라이딩 윈도우, 회전 버퍼

📌 아직 배우는 중이라 부족한 부분이 있을 수 있습니다.
혹시 잘못된 내용이나 더 나은 방법이 있다면 알려주세요 🙏
감사합니다! 😄