[자료구조] 큐(Queue) (python 파이썬)

큐(Queue)

큐는 가장 먼저 넣은 데이터가 가장 먼저 나오는 자료구조다.

스택이랑 비교하면 스택은 입구가 1개인 통 같은 구조이고, 큐는 터널 같은 구조다. 가장 먼저 들어온 차가 가장 먼저 나간다.

이런 구조를 First In First Out(FIFO, 일명 피포)라고 한다.

출처: 위키피디아

큐에는 두개의 포인터가 존재한다. 하나는 rear, 다른 하나는 front다. 

rear에서는 Enqueue, front에서는 dequeue연산이 수행된다.

 

큐의 연산

- enqueue(): 큐가 가득찼는지 확인하고 가득차있지 않으면 rear 위치에 데이터 삽입.

- dequeue(): 큐가 비어있는지 확인하고 비어있지 않으면 front위치에 있는 데이터 return하고 remove.

- peek(): 큐의 front 위치에 있는 데이터 return. 

- isFull(): 큐가 가득 찼는지 확인. 가득 찼다면 return 1. 아니면 return 0.

- isEmpty(): 큐가 비어 있는지 확인. 비어 있으면 return 1. 아니면 return 0.

 

큐 in 파이썬

파이썬에서는 queue라이브러리가 있다. 근데 보통 deque를 사용해서 구현한다. deque가 좋다bb

 

예)

from collections import deque

Queue = deque()

Queue.appendleft(2) # enqueue
Queue.appendleft(3) # enqueue
Queue.appendleft(5) # enqueue
Queue.appendleft(8) # enqueue

print(Queue) # deque([8, 5, 3, 2])

print(Queue.pop()) # 2 / dequeue
print(Queue.pop()) # 3 / dequeue

print(Queue) # deque([8, 5])

print(Queue[-1]) # 5 / peek