큐(queue), 덱(deque)

자료구조

• 스택(stack)

• 큐(queue), 덱(deque) - 현재 글

알고 있어야 하는 내용

• 리스트(list)

• 자주 사용하는 모듈(collections.deque)

자료구조의 마지막 파트인 큐, 덱 파트입니다. 알고리즘 문제에서 큐, 덱만을 이용하는 문제는 거의 없는 편이기 때문에 문제 풀이 없이 딱 3문제만 내겠습니다.

큐(queue)

개념

우리가 5주차에서 스택이란 내용을 배웠었는데요.

스택은 위 사진들과 같이 밑이 닫혀있는 상자처럼 생겨서 값을 담으면 맨 아래부터 차곡차곡 쌓고, 값을 빼야 할 때는 제일 마지막에 들어온 값인 맨 위에 있는 값을 빼내고 있습니다.

큐는 여기서 상자를 맨 아래부터 차곡차곡 쌓는 것이 스택과 똑같지만, 값을 빼낼 때는 처음에 들어온 값을 빼야 하기 때문에 스택과 다르게 아래가 뚫려있는 상자처럼 표현합니다.

그래서 첫 번째 값이 첫 번째로 나간다는 FIFO(First In, First Out) 방식을 가지고 있는 자료구조라고 합니다.

값이 들어올 때는 스택처럼 차곡차곡 쌓다가

값을 빼낼 때는 제일 먼저 들어간 값을 빼내는 방식입니다.

코드

파이썬에서는 queue 모듈도 있지만, 알고리즘 문제를 풀기엔 시간이 오래 걸려서 collections.deque를 사용합니다.

from collections import deque

q = deque()

값을 넣을 때는 스택과 똑같이 q.append()를 사용하면 됩니다. 하지만 값을 뺄 때는 q.popleft()를 사용하여 첫 번째 값을 빼야 합니다.

from collections import deque

q = deque()

# 값을 넣을 때
for i in range(5):
    q.append(5-i)
    print(5-i)

# 5
# 4
# 3
# 2
# 1

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


# 값을 뺄 때
for i in range(5):
    x = q.popleft()
    print(x)

# 5
# 4
# 3
# 2
# 1

풀어볼 문제

• https://www.acmicpc.net/problem/10845

• https://www.acmicpc.net/problem/1966

덱(deque)

개념

덱은 거의 쓰이지 않아서 살짝만 알려드리고 넘어가겠습니다. 덱이라는 말은 doubly-ended-queue의 약자입니다.

덱은 양쪽에서 값을 넣거나, 빼오는 자료구조 입니다.

위 사진을 보면 스택, 큐의 완벽한 상위호환 버전이라 많이 쓰일 것 같지만, 알고리즘 문제를 풀 때 양쪽으로 값을 넣고 빼는 기능이 필요한 문제가 없어서 거의 쓰이지 않는 자료구조 입니다.

코드

큐에서는 q.popleft()를 사용하였는데요. 덱에서는 popleft()뿐만 아니라 appendleft()까지 사용 가능합니다.

# append : 리스트 오른쪽에 값을 추가
# appendleft : 리스트 왼쪽에 값을 추가
# pop : 리스트 오른쪽에 있는 값을 빼냄
# popleft : 리스트 왼쪽에 있는 값을 빼냄

from collections import deque

dq = deque()

dq.append(1) # [1]
dq.append(2) # [1, 2]
dq.appendleft(3) # [3, 1, 2]
dq.appendleft(5) # [5, 3, 1, 2]

dq.pop() # [5, 3, 1]
dq.popleft() # [3, 1]
dq.popleft() # [1]
dq.popleft() # []

풀어볼 문제

• https://www.acmicpc.net/problem/10866