---

코딩테스트에서 자주 사용되는 대표적인 선형 자료구조인 Stack, Queue, Deque에 대해 정리해보려고 합니다.

셋 모두 데이터를 저장하고 꺼낸다는 점은 같지만, 어떤 순서로 데이터를 꺼내는지, 그리고 어느 방향에서 삽입과 삭제가 가능한가에 따라 용도가 달라집니다.

---

1. Stack

Stack은 후입선출(LIFO, Last In First Out) 구조입니다.

즉,

가장 마지막에 들어온 데이터가 가장 먼저 나온다.

접시를 차곡차곡 쌓아두고 가장 위에 있는 접시부터 꺼내는 모습을 생각하면 이해하기 쉽죠.

Stack에서는 데이터를 넣는 작업을 push, 꺼내는 작업을 pop이라고 부릅니다.
삽입과 삭제가 모두 Stack의 가장 위쪽인 Top에서 이루어집니다.

Python에서 Stack 사용하기

Python에는 별도의 Stack 자료형이 존재하지 않습니다.

대신 일반적으로 list를 Stack처럼 사용합니다.

stack = []

stack.append(1)
stack.append(2)
stack.append(3)

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

Stack의 주요 연산

값을 추가할 때는 append()를 사용합니다.

stack.append(4)

# [1, 2, 3, 4]

가장 마지막에 들어온 값을 꺼낼 때는 pop()을 사용합니다.

stack.pop()
# 4

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

pop()은 값을 단순히 삭제하는 것이 아니라 삭제한 값을 반환하기도 합니다.

값을 제거하지 않고 현재 Stack의 가장 위 값을 확인하고 싶다면 [-1]을 사용합니다.

stack[-1]
# 3

다른 언어에서 사용하는 top()과 같은 역할이라고 보면 됩니다.

Stack이 비어 있는지 확인할 때는 다음과 같이 사용할 수 있습니다.

if not stack:
    print("Stack이 비어 있습니다.")

Python에서는 빈 리스트 []를 False로 취급하기 때문에 not stack으로 간단하게 확인할 수 있습니다.

Stack 주요 연산 정리

기능	Python	시간복잡도
값 삽입	stack.append(x)	O(1)
Top 값 삭제	stack.pop()	O(1)
Top 값 확인	stack[-1]	O(1)
비어 있는지 확인	not stack	O(1)

Stack은 뒤쪽에서만 삽입과 삭제가 발생하기 때문에 Python의 list만으로도 충분히 효율적으로 구현할 수 있습니다.

---

2. Queue

Queue는 선입선출(FIFO, First In First Out) 구조입니다.

Stack과 반대로,

가장 먼저 들어온 데이터가 가장 먼저 나온다.

마트 계산대나 놀이공원의 대기줄을 생각하면 쉽습니다.

먼저 줄을 선 사람이 먼저 나가는 것처럼 Queue 역시 데이터가 들어온 순서대로 처리됩니다.

삽입                                      삭제
 ↓                                          ↑

Rear  →  [ 4 ] [ 3 ] [ 2 ] [ 1 ]  →  Front

Queue에서는 일반적으로 데이터가 Rear에서 들어오고 Front에서 나갑니다.

예를 들어 1 → 2 → 3 순서로 데이터가 들어왔다면,

입력

1 → 2 → 3

나가는 순서 역시

출력

1 → 2 → 3

가 됩니다.

이를 Stack과 비교하면 차이가 명확합니다.

Stack

입력 : 1 → 2 → 3
출력 : 3 → 2 → 1


Queue

입력 : 1 → 2 → 3
출력 : 1 → 2 → 3

Python에서 Queue 사용하기

Queue 역시 Python에 코딩테스트에서 바로 사용하는 별도의 내장 Queue 자료형이 있는 것은 아닙니다.

처음 생각하면 list를 이용해 다음과 같이 구현할 수도 있습니다.

queue = []

queue.append(1)
queue.append(2)
queue.append(3)

queue.pop(0)

하지만 이렇게 구현하는 것은 권장되지 않습니다.

왜일까요?

list의 pop(0)이 느린 이유

다음과 같은 리스트가 있다고 해봅시다.

[1, 2, 3, 4]

맨 앞에 있는 1을 제거하면

[2, 3, 4]

가 됩니다.

겉으로 보기에는 단순히 1만 제거한 것 같지만, 실제로는 뒤에 있는 원소들을 한 칸씩 앞으로 이동시켜야 합니다.

[1, 2, 3, 4]

    ↓  ↓  ↓
   앞으로 이동

[2, 3, 4]

따라서

queue.pop(0)

의 시간복잡도는 O(N) 입니다.

Queue에서는 맨 앞의 데이터를 계속 제거하는 경우가 많기 때문에 데이터가 많아질수록 비효율적이겠죠.

그래서 Python에서는 Queue를 구현할 때 일반적으로 deque를 사용합니다.

---

3. Deque

Deque는 Double Ended Queue의 약자입니다.

말 그대로

양쪽 끝에서 데이터를 삽입하고 삭제할 수 있는 자료구조

입니다.

일반적인 Queue는 한쪽에서 데이터를 넣고 반대쪽에서 데이터를 꺼내지만, Deque는 왼쪽과 오른쪽 모두 사용할 수 있습니다.

appendleft()                              append()
      ↓                                      ↓

      [ 1 ] [ 2 ] [ 3 ] [ 4 ]

      ↑                                      ↑
  popleft()                                pop()

Python에서 Deque 사용하기

Python에서는 collections 모듈의 deque를 사용합니다.

from collections import deque

dq = deque()

기존 리스트를 바로 deque로 변환하는 것도 가능합니다.

from collections import deque

dq = deque([1, 2, 3])

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

Deque의 주요 연산

오른쪽에 데이터를 추가할 때는 append()를 사용합니다.

dq.append(4)

# deque([1, 2, 3, 4])

왼쪽에 데이터를 추가할 때는 appendleft()를 사용합니다.

dq.appendleft(0)

# deque([0, 1, 2, 3, 4])

오른쪽 데이터를 제거할 때는 pop(),

dq.pop()

왼쪽 데이터를 제거할 때는 popleft()를 사용합니다.

dq.popleft()

따라서 다음 네 가지가 Deque의 핵심이라고 볼 수 있습니다.

dq.append(x)       # 오른쪽 삽입
dq.appendleft(x)   # 왼쪽 삽입

dq.pop()           # 오른쪽 삭제
dq.popleft()       # 왼쪽 삭제

양 끝의 값을 제거하지 않고 확인하는 것도 가능합니다.

dq[0]      # 가장 왼쪽 값
dq[-1]     # 가장 오른쪽 값

Deque 주요 연산 정리

기능	Python	시간복잡도
오른쪽 삽입	append()	O(1)
왼쪽 삽입	appendleft()	O(1)
오른쪽 삭제	pop()	O(1)
왼쪽 삭제	popleft()	O(1)

deque의 가장 큰 장점은 양쪽 끝의 삽입과 삭제가 모두 O(1) 이라는 점입니다.

---

4. Deque로 Stack과 Queue 구현하기

여기까지 보면 한 가지 의문이 생길 수 있습니다.

Deque는 양쪽에서 모두 넣고 뺄 수 있으니 Stack과 Queue 둘 다 만들 수 있지 않을까?

맞습니다.

Deque는 사용하는 방향에 따라 Stack처럼 사용할 수도 있고 Queue처럼 사용할 수도 있습니다.

Deque를 Stack처럼 사용

오른쪽에서 넣고 오른쪽에서 다시 꺼내면 됩니다.

from collections import deque

stack = deque()

stack.append(1)
stack.append(2)
stack.append(3)

stack.pop()

                  append()
                     ↓

[ 1 ] [ 2 ] [ 3 ]

                  ↑
                 pop()

가장 마지막에 들어온 3이 가장 먼저 나오기 때문에 LIFO, 즉 Stack이 됩니다.

다만 Stack은 list만으로도 뒤쪽 삽입과 삭제가 O(1)이기 때문에 일반적으로는 굳이 deque를 사용할 필요가 없습니다.

stack = []

정도로 충분합니다.

Deque를 Queue처럼 사용

이번에는 오른쪽에서 넣고 왼쪽에서 꺼냅니다.

from collections import deque

queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)

queue.popleft()

popleft()                         append()
    ↑                                ↓

[ 1 ] [ 2 ] [ 3 ]

가장 먼저 들어온 1이 가장 먼저 나오기 때문에 FIFO, 즉 Queue가 됩니다.

Python 코딩테스트에서 Queue를 구현할 때 가장 흔하게 보는 형태입니다.

---

5. list와 deque의 차이

Stack과 Queue를 Python으로 구현할 때 list와 deque를 구분해서 사용하는 이유는 시간복잡도에 있습니다.

연산	list	deque
오른쪽 삽입	O(1)	O(1)
오른쪽 삭제	O(1)	O(1)
왼쪽 삽입	O(N)	O(1)
왼쪽 삭제	O(N)	O(1)

list는 오른쪽에서 데이터를 넣고 빼는 것은 빠르지만, 왼쪽에서 데이터를 넣거나 제거하려면 기존 원소들을 이동시켜야 합니다.

반면 deque는 양쪽 끝에서 삽입과 삭제를 빠르게 수행할 수 있도록 만들어져 있습니다.

따라서 코딩테스트에서는 일반적으로 다음과 같이 기억하면 편합니다.

Stack → list

Queue → deque

Deque → deque

---

6. Stack / Queue / Deque 한눈에 보기

자료구조	특징	동작 방식	Python
Stack	한쪽에서 삽입 / 삭제	LIFO	list
Queue	뒤에서 삽입 / 앞에서 삭제	FIFO	deque
Deque	양쪽에서 삽입 / 삭제	양방향	deque

조금 더 간단하게 그림으로 정리하면 다음과 같습니다.

Stack

             ↓ append()

          [ 3 ] ← Top
          [ 2 ]
          [ 1 ]

             ↑ pop()

LIFO
Last In First Out

Queue

popleft() ← [ 1 ] [ 2 ] [ 3 ] ← append()

FIFO
First In First Out

Deque

appendleft() → [ 1 ] [ 2 ] [ 3 ] ← append()
                 ↑             ↑
             popleft()        pop()

---

마무리

Stack, Queue, Deque는 결국 데이터가 들어오고 나가는 순서와 방향을 이해하는 것이 핵심입니다.

문제에서 가장 최근에 들어온 데이터를 먼저 처리해야 한다면 Stack,

먼저 들어온 데이터를 순서대로 처리해야 한다면 Queue,

양쪽 끝에서 데이터를 자유롭게 추가하거나 제거해야 한다면 Deque를 생각할 수 있습니다.

Python에서는 마지막으로 다음 정도만 확실하게 기억해두면 좋을 것 같습니다.

# Stack
stack = []

stack.append(x)
stack.pop()
stack[-1]


# Queue
from collections import deque

queue = deque()

queue.append(x)
queue.popleft()


# Deque
dq.append(x)
dq.appendleft(x)

dq.pop()
dq.popleft()

Stack → list
Queue → deque
Deque → deque

자료구조 자체는 단순하지만 실제 문제에서는 어떤 자료구조를 선택해야 하는지를 판단하는 것이 더 중요하다고 생각합니다.