큐(Queue) 이론과 파이썬 구현

큐(Queue)

 

큐는 FIFO(First-In First-Out) 형식을 가집니다.

 

큐의 예는 매표소에서 표 구매, 은행 창구에서 순서 기다리는 것이 있습니다.

매표소에서 표를 사기 위해서는 사람들이 줄을 서고 줄을 선 순서대로 표를 살 수 있습니다.

즉, 가장 먼저 줄을 서서 앞에 있는 사람이 먼저 표를 사게 되는 방식입니다.

 

큐의 삽입과 삭제는 다른 쪽에서 일어납니다.

삽입이 일어나는 곳은 후단(rear)이라 하고 삭제가 일어나는 곳은 전단(front)라고 합니다.

 

큐에서는 Enqueue와 Dequeue를 알아야 합니다.

Enqueue은 큐의 요소를 추가하는 연산으로 큐의 가장 뒤에 새로운 요소를 추가합니다.

Dequeue은 큐의 가장 앞에 있는 요소를 반환합니다.

 

큐는 파이썬 라이브러리 Queue()를 사용해 구현할 수 있습니다.

 

큐에는 여러 연산이 있습니다.

push : 큐의 가장 뒤에 데이터 넣기

pop : 큐의 가장 앞에 데이터 제거

front : 큐의 가장 앞의 값 확인

empty : 큐가 비었는지 확인

 

 

큐의 파이썬 코드입니다.

import queue

que = queue.Queue()

que.put(1)
que.put(2)
que.put(3)
que.put(4)
que.put(5)

# 출력>>deque([1, 2, 3, 4, 5])
print(que.queue)

que.get()
# 출력>>deque([2, 3, 4, 5])
print(que.queue)

que.get()
# 출력>>deque([3, 4, 5])
print(que.queue)

que.get()
# 출력>>deque([4, 5])
print(que.queue)

 

---

파이썬 라이브러리 Queue()를 사용해 기본적인 큐 외에도 다양한 큐를 구현할 수 있습니다.

 

LifoQueue() : 기존 큐와 다르게 LIFO(last-In First-Out) 형식을 가지는 큐입니다.

즉, 스택과 같은 구조를 가집니다.

 

LifoQueue의 파이썬 코드입니다.

import queue

lque = queue.LifoQueue()

lque.put(1)
lque.put(2)
lque.put(3)
lque.put(4)
lque.put(5)

# 출력>>[1, 2, 3, 4, 5]
print(lque.queue)

lque.get()
# 출력>>[1, 2, 3, 4]
print(lque.queue)

lque.get()
# 출력>>[1, 2, 3]
print(lque.queue)

lque.get()
# 출력>>[1, 2]
print(lque.queue)

 

PriorityQueue() : 데이터마다 우선순위를 넣어 우선순위가 높은 순으로 출력되는 형식을 가진 큐입니다.
(우선순위, 데이터) 형식의 튜플로 넣어야 합니다.
또한 데이터는 튜플로 저장됩니다.

 

PriorityQueue의 파이썬 코드입니다.

import queue

pque = queue.PriorityQueue()

pque.put((1,1))
pque.put((3,2))
pque.put((2,3))
pque.put((4,4))
pque.put((5,5))

# 출력>>[(1, 1), (3, 2), (2, 3), (4, 4), (5, 5)]
print(pque.queue)

pque.get()
# 출력>>[(2, 3), (3, 2), (5, 5), (4, 4)]
print(pque.queue)

pque.get()
# 출력>>[(3, 2), (4, 4), (5, 5)]
print(pque.queue)

pque.get()
# 출력>>[(4, 4), (5, 5)]
print(pque.queue)