[05-1] 큐(Queue)란?

보자마자 살짝 멈칫하게 되는 그 이름 큐(Queue).

내가 코테를 공부하기 위해 자료구조를 공부하면서 항상 큐에서 멈췄다.

옛날 집합파트까지만 헌책이던 수학책 같은 느낌이랄까.

각설하고 큐에 대해 큰 흐름부터 이해해보자.

 

큐(Queue)는 Array list, Linked list, FIFO로 만들 수 있다.

하지만 Array list로 만들면 Queue의 장점이 하~나도 없다.

그래서 Linked list로 만드는 편이지만, 우리는 Queue를 따로 만들 필요가 없다.

왜? 파이썬에서 이미 Deque라는 자료구조로 제공하고 있으니까!

 

Queue는 FIFO(First In, First Out)의 방식으로 저장하는 데이터구조이다.

Queue의 뒤쪽(rear)에 자료를 저장하는 것을 enqueue, 앞(front)에서 데이터를 꺼내는 것을 dequeue라고 한다.

Queue의 구조

그림으로 보면 이해가 되는 것인가? Array의 형태로 쉽게 그려보았다(array로는 안쓰기 떄문에 실제 이런 구조는 아니다. 실제로는 Linked list처럼 주소값이 포함되어야 한다).

 

자 그러면 왜 Array로 안쓰냐? 시간복잡도가 O(n)이 되니까.

Array를 안쓰는 이유

# queue 제작
q = []
# enqueue
q.append(1)
q.append(2)
q.append(3)
q.append(4)
q.append(5)
# dequeue
q.pop(0)

append를 이용하면 쉽게 enqueue가 가능하다. 이러헥 1,2,3,4,5가 차례대로 넣어지니까.

하지만 pop을 할경우, First in Last Out (FILO)의 형식이 된다. 그래서 pop(0) 을 해주는데 문제는 Array는 앞이 비어있다면 옮기게 되어있다.

즉 n만큼의 길이라면, n번 옮겨야 하는 것이다. 그래서 굳이 이렇게 해야하나? 싶은것이지.

 

그래서 우리는 Linked list의 구조로 쓰는 것이고, 파이썬에서는 이미 구현이 되어 있으니 불러오기만 하면 된다.

from collections import deque
queue = deque() #front, rear 모두 있는 Linked list라고 생각하면 된다.

#enque() 
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

#dequeue() 
queue.popleft()

 

Deque의 구조

 

deque는 이렇게 자동으로 된다. 얼마나 편한가? 심지어 O(1) 이다.

deque = doublly ended que의 약자이기 때문에 앞뒤로 가능하다~ 라는 뜻이다.

우리는 큐를 써야한다면? deque를 쓴다 라고 생각하면 편하다.

 

Queue 총정리

 

장점

1. 파이썬에서 불러오기만 하면 된다.

2. 시간복잡도가 O(1)이다!

 

단점

1. 단점이라고 하긴 뭐하지만.. 단독으로 쓰이는 경우는 없고, 자료구조 및 알고리즘을 활용할 때 자연스럽게 사용된다. 특히 너비 탐색 (BFS)

 

총평

따로 만들필요가 없어 아주 편하다.