스택이 먼저 삽입된 데이터가 나중에 추출되는 자료구조였다면, 큐는 반대로 먼저 들어온 데이터가 먼저 추출되는 구조입니다. 큐도 게임 좋아하시는 분들이, 특히 온라인 게임을 즐겨하시는 분들이 많이 들어보셨을 용어입니다. 게임에서 큐라고 하면 흔히 매칭 대기 순서를 뜻하고, 먼저 대기한 사람이 먼저 매칭되는 구조를 갖는 거죠.
큐의 예시
스택에서와 마찬가지로 큐에 여러 개의 데이터를 삽입, 삭제하는 예시를 보겠습니다. 전체 연산은 아래와 같고, 지난 포스트에서 다룬 스택에서 썼던 예시 연산과 동일합니다.
큐와 다른 점이라면 삽입 위치와 삭제 위치가 서로 반대에 자리잡는다는 점입니다. 스택 연산이 한 쪽이 막힌 파이프였다면, 큐는 양쪽 구멍이 모두 뚫려 마치 파이프 속에 물이 흐르듯 자료가 삽입, 삭제되는 특징이 있습니다.
연결 리스트로 큐 구현하기
다음으로 큐를 직접 구현해보겠습니다. 파이썬의 리스트 자료형을 이용해서 큐를 구현할 수도 있습니다. 그러나 이 방법의 문제점은 시간복잡도가 비효율적으로 증가한다는 것입니다. 따라서 일반적으로 연결 리스트의 형태로 구현하게 됩니다. 큐를 연결 리스트로 구현하면, 삽입과 삭제에 있어서 $O\left(1\right)$의 시간복잡도를 보장할 수 있습니다. 스택에서 가장 먼저 들어온 데이터를 가리키는 포인터로써 머리(head)를 정의한 것과 같이, 큐에서는 꼬리(tail)라는 이름의 또다른 포인터를 더 필요로 합니다. def) 꼬리 (tail): 남아있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터
삽입 연산
삽입할 때는 꼬리 위치에 데이터를 넣습니다.
삭제 연산
삭제할 때는 머리 위치에서 데이터를 꺼내옵니다. 삭제 연산만 스택과 동일하군요.
파이썬에서의 구현 방식
연결 리스트를 이용해 파이썬에서 큐를 구현해 보겠습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.head = None
self.next = None
def enqueue(self, data):
node = Node(data)
if self.head == None:
self.head = node
self.tail = node
# Insert a new node at tail
else:
self.tail.next = node
self.tail = self.tail.next
def dequeue(self):
if self.head == None:
return
data = self.head.data
self.head = self.head.next
return data
def show(self):
cur = self.head
while cur:
print(cur.data, end=" ")
cur = cur.next
queue = Queue()
data_list = [3, 5, 9, 8, 5, 6, 1, 7]
for data in data_list:
queue.enqueue(data)
print("\nPrint entire node:", end= " ")
queue.show()
print("\n[Delete element]")
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
print("\n[Insert element]")
queue.enqueue(2)
queue.enqueue(5)
queue.enqueue(3)
print("Print entire node:", end= " ")
queue.show()
구현 방식에 따른 연산 속도 비교
앞서 말한 것처럼 파이썬 리스트를 그대로 사용해 큐를 구현할 경우 비효율적인 시간 소모가 되기 때문에 우리는 연결 리스트를 이용해 구현한다고 했습니다. 실제로 그런지 예제를 통해 알아보겠습니다. 소요 시간 비교를 위해 time 라이브러리를 이용해 소모시간을 체크합니다. 이 예제에 사용된 데이터 리스트의 크기는 100,000입니다.
import time
# 1. 파이썬 리스트로 구현한 예시
data_list = [i for i in range(100000)]
start_time = time.time()
queue = []
for data in data_list:
queue.append(data)
while queue:
queue.pop(0)
print(f"Elapsed time: {time.time() - start_time} seconds.")
print(queue)
# 2. 연결 리스트로 구현한 예시
start_time = time.time()
queue = Queue()
for data in data_list:
queue.enqueue(data)
while queue.head != None:
queue.dequeue()
print(f"Elapsed time: {time.time() - start_time} seconds.")
queue.show()
아래 두 이미지는 각각 파이썬 리스트 구현한 큐와 연결 리스트로 구현한 큐의 실행 결과입니다.
강의 예제에서는 약 3~4배 정도 차이가 난다고 했는데, 제 컴퓨터에서는 약 5배에 가까운 차이가 났습니다. 물론 강의 예제
결과와 제 실행 결과 모두 연결 리스트로 구현한 예시가 더 빨랐습니다.
23일차 후기
챌린지 완수까지 약 1주일 남았습니다. 기왕 습관 잡힌 거 챌린지가 끝나더라도 꾸준히 달려보겠습니다.
