큐(queue), 덱(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풀어볼 문제
덱(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() # []풀어볼 문제
Last updated