파이썬 스택, 큐 deque (with 백준 18258)

✅ 스택(Stack)과 큐(Queue)는 기본적인 자료구조로 다양한 알고리즘에서 활용된다.

✅ 파이썬에서는 list와 deque를 활용하여 스택과 큐를 구현할 수 있다.

✅ 백준 18258번 문제(큐2)를 통해 deque를 연습해 본다!

 

📌 스택과 큐의 차이점

자료구조	동작 방식	특징
스택 (Stack)	LIFO (Last In First Out)	나중에 들어간 요소가 먼저 나옴
큐 (Queue)	FIFO (First In First Out)	먼저 들어간 요소가 먼저 나옴

 

📌 스택 (Stack) - 리스트 활용

 

파이썬에서는 list 객체를 이용하여 스택을 구현할 수 있다.

stack = []

# 요소 추가 (push)
stack.append(1)
stack.append(2)
stack.append(3)

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

# 요소 제거 (pop)
print(stack.pop())  # 3
print(stack.pop())  # 2
print(stack)  # [1]

 

📌 큐 (Queue) - deque 활용

 

파이썬에서는 collections.deque를 사용하여 큐를 구현할 수 있다.

 

✅ list를 사용하면 pop(0) 연산이 느리지만, deque는 O(1) 시간 복잡도로 빠르게 작동한다.

from collections import deque

queue = deque()

# 요소 추가 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

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

# 요소 제거 (dequeue)
print(queue.popleft())  # 1
print(queue.popleft())  # 2
print(queue)  # deque([3])

 

📌 deque의 주요 메서드

메서드	설명
append(x)	오른쪽에 요소 x 추가
appendleft(x)	왼쪽에 요소 x 추가
pop()	오른쪽 요소 제거 후 반환
popleft()	왼쪽 요소 제거 후 반환
extend(iterable)	iterable의 요소들을 오른쪽에 추가
extendleft(iterable)	iterable의 요소들을 왼쪽에 추가 (순서가 뒤집힘)
rotate(n)	n만큼 오른쪽으로 회전 (-n이면 왼쪽 회전)

 

📌 deque 활용 예제

 

1️⃣ deque의 maxlen 차이점

from collections import deque

# maxlen을 지정하지 않은 deque
x = deque([1, 2, 3, 4, 5])
x.append(6)  
print(x)  # deque([1, 2, 3, 4, 5, 6])

# maxlen을 지정한 deque
y = deque([1, 2, 3, 4, 5], maxlen=5)
y.append(6)  
print(y)  # deque([2, 3, 4, 5, 6]) → 기존 1이 삭제됨

 

2️⃣ rotate()와 reverse() 활용

x = deque([1, 2, 3, 4, 5])
x.reverse()  # 요소 순서 뒤집기
print(x)  # deque([5, 4, 3, 2, 1])

x.rotate(1)  # 오른쪽으로 한 칸 회전
print(x)  # deque([1, 5, 4, 3, 2])

x.rotate(-1)  # 왼쪽으로 한 칸 회전
print(x)  # deque([5, 4, 3, 2, 1])

 

📌 백준 18258번 - 큐2 (deque 활용)

 

[문제 링크] 🔗 백준 18258번 - 큐2

 

📝 문제 설명

• push X → 정수 X를 큐에 넣는다.

• pop → 큐에서 가장 앞에 있는 정수를 제거하고 출력, 없으면 -1 출력

• size → 큐의 크기 출력

• empty → 큐가 비어있으면 1, 아니면 0 출력

• front → 큐의 가장 앞 정수 출력 (없으면 -1)

• back → 큐의 가장 뒤 정수 출력 (없으면 -1)

 

💡 해결 방법

 

✅ 입력이 최대 2,000,000개이므로 sys.stdin.readline()을 사용하여 빠르게 입력을 처리해야 한다.

✅ deque를 사용하면 pop 연산이 빠르다.

 

🔹 코드 구현

import sys
from collections import deque
#입력값 받기
N = int(sys.stdin.readline().rstrip())
cmd = [sys.stdin.readline().rstrip().split(" ") for _ in range(N)]
queue = deque()
#문제풀이
for i in range(0, N):
    #print(cmd[i][0])
    if (cmd[i][0] == 'push'):
        x = cmd[i][1]
        queue.append(x)
    elif cmd[i][0] == 'pop':
        if (len(queue) > 0):
            x = queue.popleft()
            print(x)
        else:
            print(-1)
    elif cmd[i][0] == 'size':
        x = len(queue)
        print(x)
    elif cmd[i][0] == 'empty':    
        if (len(queue) == 0):
            print(1)
        else:
            print(0)
    elif cmd[i][0] == 'front':
        if (len(queue) > 0):
            print(queue[0])
        else:
            print(-1)
    elif cmd[i][0] == 'back':
        if (len(queue) > 0):
            print(queue[-1])
        else:
            print(-1)

 

🔹 실행 예제

 

입력

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

 

출력

1
2
2
0
1
2
-1
0
1
-1
0
3

 

📌 마무리 - 정리

✅ 스택은 LIFO (Last In, First Out), 큐는 FIFO (First In, First Out)

✅ 파이썬에서 list는 스택으로 사용 가능하지만, 큐는 deque를 활용하는 것이 효율적

✅ 백준 18258번 문제를 통해 큐의 기본 연산을 연습할 수 있음

✅ sys.stdin.readline()을 활용하여 빠르게 입력을 받아야 함