[CS/자료구조] Stack, Queue, Deque

선우·2026년 1월 4일

CS

목록 보기

17/20

[CS/자료구조] 03. Stack, Queue, Deque

⚡ 한 줄 요약: 데이터의 출입 순서와 방향에 따라 달라지는 세 가지 핵심 자료구조의 특성을 이해하고, 모든 연산은 $O(1)$ 로 처리하는 최적의 구현 방법을 배웁니다.

1. 👋 들어가며: "어떤 순서로 데이터를 다룰 것인가?"

자료구조의 핵심은 데이터를 단순히 저장하는 것을 넘어, 필요한 시점에 어떤 순서로 꺼내 쓸 것인가에 있습니다.

뒤로 가기를 눌렀을 때 직전 페이지가 나와야 하는 상황과, 프린터에 보낸 문서가 순서대로 출력되어야 하는 상황은 전혀 다른 논리를 필요로 합니다.

🧐 Why:
- 스택과 큐는 알고리즘 문제 해결의 필수 도구일 뿐만 아니라, 운영체제의 프로세스 관리나 자바스크립트의 Call Stack / Task Queue 동작 원리를 이해하는 뿌리가 됩니다.
🎯 Goal:
- LIFO(스택), FIFO(큐)의 차이점을 명확히 설명할 수 있습니다.
- 배열 기반 구현의 성능 한계를 인지하고, 연결 리스트를 활용한 최적화 방법을 익힙니다.
- 상황에 따라 Deque를 사용하여 유연하게 대응하는 법을 배웁니다.

📂 2. Stack

📌 2-1. 핵심 개념

스택은 데이터를 한쪽 끝에서만 넣고 뺄 수 있는 제한적인 구조를 가집니다.
이 '제한적'이라는 특성이 오히려 특정 상황에서는 강력한 무기가 됩니다.

동작 원리
- 접시를 쌓는 것과 같습니다. 가장 마지막에 올려둔 접시를 가장 먼저 집게 되는 원리인 후입선출(LIFO) 방식으로 동작합니다.
활용 사례
- 문서 편집기의 실행 취소(Undo), 웹 브라우저의 뒤로 가기, 함수 호출 시 사용하는 시스템 스택 등이 대표적입니다.

📌 2-2. 주요 연산 및 시간 복잡도

스택의 모든 주요 연산은 맨 위의 데이터만 다루기 때문에 매우 빠릅니다.

연산	설명	시간 복잡도
`push(e)`	스택의 맨 위에 요소를 추가합니다.	$O(1)$
`pop()`	스택의 맨 위 요소를 제거하고 반환합니다.	$O(1)$
`peek()`	스택의 맨 위 요소를 확인만 합니다.	$O(1)$
`isEmpty()`	스택이 비어 있는지 확인합니다.	$O(1)$

📌 2-3. 연결 리스트 기반 스택 구현 (Python)

스택은 배열로도 구현할 수 있지만, 메모리를 효율적으로 쓰기 위해 연결 리스트를 활용하는 경우가 많습니다.

last라는 포인터가 항상 스택의 맨 위(최신 데이터)를 가리키게 설계합니다.

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Stack:
    def __init__(self):
        self.last = None

    def push(self, val):
        # 새로운 노드를 만들고 기존의 last를 next로 연결합니다.
        self.last = Node(val, self.last) 

    def pop(self):
        if not self.last: return "Stack is Empty"
        popped = self.last.val
        self.last = self.last.next # 포인터를 이전 노드로 옮깁니다.
        return popped

📌 2-4. 헷갈리기 쉬운 포인트 / 오해 정리

스택에서 중간 데이터를 꺼낼 수 있나요?
- 이론적인 스택 구조에서는 불가능합니다. 중간 데이터를 꺼내려면 그 위에 쌓인 데이터들을 모두 pop해야 합니다.
- 만약 중간 접근이 빈번하다면 스택이 아닌 리스트를 써야 합니다.
Stack Overflow
- 스택 메모리 공간이 꽉 찼는데 계속 push를 시도할 때 발생하는 에러입니다.
- 주로 끝도 없이 반복되는 재귀 함수 때문에 자주 마주하게 됩니다.

📌 2-5. 한 줄 정리

스택은 최상단 데이터만 다루는 LIFO 구조로, 모든 핵심 연산이 $O(1)$ 인 매우 효율적인 자료구조입니다.

📂 3. Queue

📌 3-1. 핵심 개념

큐의 핵심은 '공정함'입니다. 데이터가 들어오는 통로와 나가는 통로가 분리되어 있어, 먼저 들어온 데이터가 대기열의 맨 앞에서 먼저 처리되는 구조를 가집니다.

동작 원리
- 맛집 대기 줄이나 프린터 대기열을 생각하면 쉽습니다.
- 데이터가 추가되는 곳을 '뒤(Rear/Back)', 제거 되는 곳을 '앞(Front)'이라고 부릅니다.
활용 사례
- 프린터 작업 대기열, 네트워크 패킷 처리, 프로세스 스케줄링 등 순차적인 작업 처리가 필요한 모든 시스템에 사용됩니다.

📌 3-2. 주요 연산 및 시간 복잡도

큐 역시 스택과 마찬가지로 양 끝단의 데이터만 다루기 때문에 매우 효율적입니다.

연산	설명	시간 복잡도
`enqueue(e)`	큐의 맨 뒤에 요소를 추가합니다.	$O(1)$
`dequeue()`	큐의 맨 앞 요소를 제거하고 반환합니다.	$O(1)$
`peek()`	큐의 맨 앞 요소를 확인만 합니다 (제거 X)	$O(1)$
`isEmpty()`	큐가 비어 있는지 확인합니다.	$O(1)$

📌 3-4. 연결 리스트 기반 큐 구현

큐를 배열로 구현하면 데이터를 뺄 때마다 뒤의 요소들을 앞으로 당겨야 해서 $O(n)$ 의 비용이 들 수 있습니다.

그래서 실무와 면접에서는 연결 리스트를 활용해 양방향 접근을 최적화하는 방식을 선호합니다.

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Queue:
    def __init__(self):
        self.head = None # 맨 앞(Front) 
        self.last = None # 맨 뒤(Back) 

    def enqueue(self, val):
        new = Node(val) 
        if not self.head: # 비어있는 상태라면
            self.head = new
            self.last = new
        else:
            self.last.next = new
            self.last = self.last.next # last 포인터 이동

    def dequeue(self):
        if not self.head: return "Queue is Empty"
        popped = self.head.val
        self.head = self.head.next # head 포인터를 다음 노드로 이동
        if not self.head: # 마지막 노드까지 뺐다면
            self.last = None
        return popped

📌 3-5. 헷갈리기 쉬운 포인트 / 오해 정리

배열 기반 큐의 함정
- 파이썬의 list를 사용해 list.pop(0)으로 큐를 구현하면, 첫 번째 요소를 뺀 뒤 모든 요소를 앞으로 한 칸씩 옮겨야 하므로 $O(n)$ 이 걸립니다.
- 면접에서 큐를 구현할 때는 반드시 이 효율성 문제를 언급하거나, 연결 리스트 구조(또는 collections.deque)를 제안하는 것이 좋습니다.

📌 3-6. 한 줄 정리

큐는 FIFO 원칙을 지키며 대기열을 관리하는 자료구조로, 모든 핵심 연산은 $O(1)$ 로 처리됩니다.

📂 4. Deque

📌 4-1. 핵심 개념

덱(Double-ended Queue)은 이름 그대로 '양방향' 대기열입니다.

데이터가 들어오고 나가는 입구가 하나였던 스택, 입구와 출구가 정해져 있던 큐와 달리, 덱은 앞(Front)과 뒤(Rear) 어디서든 요소를 넣고 뺄 수 있습니다.

스택 + 큐의 결합
- 앞뒤 모두를 활용하기 때문에 필요에 따라 스택처럼 쓸 수도, 큐처럼 쓸 수도 있습니다.
압도적인 속도
- 양방향 삽입과 삭제 연산 모두 $O(1)$ 로 매우 빠릅니다.

📌 4-2. 주요 연산 및 시간 복잡도

연산	설명	시간 복잡도
`append(e)`	덱의 맨 뒤에 요소 추가	$O(1)$
`appendleft(e)`	덱의 맨 앞에 요소 추가	$O(1)$
`pop()`	덱의 맨 뒤 요소 제거 및 반환	$O(1)$
`popleft()`	덱의 맨 앞 요소 제거 및 반환	$O(1)$
`isEmpty()`	덱이 비어 있는지 확인	$O(1)$

📌 4-3. 실전 활용: 파이썬에서의 덱

파이썬에서는 collections.deque 모듈을 사용해 deque를 효율적으로 구현할 수 있습니다.

from collections import deque

dq = deque()

# 뒤에서 추가 (append)
dq.append(10)
dq.append(20)

# 앞에서 추가 (appendleft)
dq.appendleft(5)
dq.appendleft(1)

print(dq) # deque([1, 5, 10, 20])

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

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

📌 4-4. 헷갈리기 쉬운 포인트 / 오해 정리

파이썬 리스트(list)로 큐를 만들면 안 되나요?
- 리스트의 pop(0)은 첫 번째 요소를 뺀 후 모든 데이터를 앞으로 한 칸씩 당겨야 해서 $O(n)$ 이 걸립니다.
- 하지만 덱의 popleft()는 데이터 이동 없이 포인터만 조작하므로 데이터가 백만 개라 하더라도 즉시 처리됩니다.

📌 4-5. 한 줄 정리

덱은 양방향 $O(1)$ 연산을 보장하는 다재다능한 자료구조로, 성능 최적화가 필요한 대기열 관리의 핵심 도구입니다.

🎁 5. 정리

🔑 요약

특성	스택(Stack)	큐(Queue)	덱(Deque)
관리 원칙	LIFO (후입선출)	FIFO (선입선출)	양방향 자유 출입
주요 연산	`push`, `pop`	`enqueue`, `dequeue`	`append`, `appendleft` 등
시간 복잡도	전 연산 $O(1)$	전 연산 $O(1)$	전 연산 $O(1)$
실무 예시	뒤로 가기, Undo/Redo, 콜 스택	프린터 대기열, 메시지 큐	양방향 스케줄링, 슬라이딩 윈도우
핵심 포인트	중간 접근 불가	배열 구현 시 $O(n)$ 주의	스택과 큐의 장점 결합

선우

이전 포스트

[CS/자료구조] 배열과 리스트

다음 포스트