큐(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