Queue

우리는 우선 순위 큐(priority Queue)를 알기 위해서 queue를 알아야 한다. queue는 FIFO이다. 즉, Stack과는 반대로 먼저 들어간 인자가 먼자 출력되는 것이다. 먼저 코드를 살펴보자.

 

#FIFO 이기때문에 먼저 들어간 인자가 먼저 나온다. stack과 반대이다.

from collections import deque

queue = deque([1,2,3])

queue.append(4)

print(queue)

print(queue.popleft())

print(queue)

 

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

위의 코드에서 보이 듯 popleft로 먼저 들어왔던 인자를 pop했다. queue에는 enque와 deque라는 개념이 존재하는데 enque는 값을 오른쪽으로 삽입하는 것이고 deque는 왼쪽에 있는 값을 제거하는 개념이다. 따라서 queue는 FIFO가 원칙이다. 하지만 deque에는 pop이라는 함수가 따로 존재한다. 아래 코드를 살펴보자.

#FIFO 이기때문에 먼저 들어간 인자가 먼저 나온다. stack과 반대이다.

from collections import deque

queue = deque([1,2,3])

queue.append(4)

print(queue)

print(queue.popleft())

print(queue)

queue.append(5)

print(queue)

print(queue.pop())

print(queue)

 

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

 

stack과 같이 pop을 이용해서 마지막에 들어간 값을 먼저 pop했다. 그렇다면 FIFO의 원칙에서 벗어나는 것 아닌가 할 것이다. 이는 list의 값을 제거 할 수 있기에 pop이 기본적으로 내장 되어 있는 함수인 것이다. 그래서 원칙적으론 popleft를 사용해야 FIFO의 원칙을 따를 수 있는 것이다.

우리는 queue를 통해서 앞으로 우선 순위 큐를 공부 할 것이다. 이후 Heap을 공부할 것인데 이것을 알기 전에 이진 트리구조를 공부하고 Heap을 공부할 것이다. Heap은 완전 인진 트리라는 것을 기억하자. 지금까지 공부한 것들이 많이 얽혀 있어서 알고리즘을 공부하고 정리하는데 시간이 걸린 부분들이 많다. 하나하나 차분히 풀어 나가보자. (앞으로 바킹독의 실전 알고리즘 강의를 중점으로 포스팅할 예정이다.)