[자료구조] 큐(Queue)

큐(Queue)란?

• 양 쪽이 뚫린 통에서 한 쪽은 자료를 삽입, 다른 한 쪽으로 자료를 삭제하는 구조
• 스택과 반대로 FIFO ( First In Frist Out ) 의 구조
• 데이터는 Back ( Rear라고 부른다) 으로 들어와서 Front로 나간다.
• 예시) 키오스크 음식 주문

출처: 위키피디아 - 큐

 

---

큐의 연산

• Enqueue: 데이터를 삽입하는 과정
• Dequeue: 데이터를 삭제하는 과정 ( 이 때 큐가 비어있는지 확인한 후 실행 )
• peek: Front 위치에 있는 데이터가 어떤 값인지 return함 ( 이 때 데이터를 꺼내지는 않음 )
• isEmpty: 현재 큐가 비어있는지 확인

---

큐의 구현

list를 사용한 구현

queue = [1, 2, 3]

queue.append(4)
print(queue)

queue.pop(0)
print(queue)

리스트의 append()와 pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있다.

(반대 방향으로 큐를 만들고 싶으면 insert(0, x)와 pop()를 사용)

하지만, 이 경우에는 데이터가 많아질 수록 성능이 크게 저하될 수 있다.

append()의 시간 복잡도는 O(1)이지만, pop()과 insert()의 경우 시간 복잡도가 O(n)이기 때문이다.

 

<--- 결과 --->

 

[1, 2, 3, 4]
[2, 3, 4]

---

큐 모듈을 이용한 구현

queue 모듈의 Queue클래스를 불러와서 사용한다.

put(n)을 통해 데이터를 삽입할 수 있고

get()을 통해 데이터를 불러올 수 있다.

 

이 경우 스레드 프로그래밍에서 주로 사용하며, 필요한 모든 로킹(Locking) 개념을 구현한다.

from queue import Queue

queue = Queue()
queue.put(1)
queue.put(2)
print(queue.get())
print(queue.get())

 

<--- 결과 --->

 

1
2

---

덱(deque)을 이용한 구현

Collections 모듈의 deque를 통해 큐를 구현할 수 있다.

list와 마찬가지로 append(n)을 통해 데이터를 삽입할 수 있으며

popleft()를 통해 데이터를 제거할 수 있다.

 

사실 deque의 경우 데이터를 양 방향에서 삽입, 삭제할 수 있는 구조다.

( Double- Ended Queue - > Deque )

 

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])