큐 queue

큐(queue)는 순서가 있는 선형 자료구조이다.

가장 큰 특징은 FIFO(First In First Out) 방식으로, 데이터들은 들어온 순서대로 나간다.

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

 

 

Front : 원소의 삭제(출력)가 일어남

Rear : 새로운 원소가 삽입됨

 

C로 쓴 자료구조론 2판 p.121

 

 

큐 연산자

• IsFullQ : 큐가 꽉 찼는지 검사 -> *rear == MAX_QUEUE_SIZE-1 인지 검사
• IsEmptyQ : 큐가 비었는지 검사 -> front == rear 인지 검사
• AddQ (Enqueue) : 큐의 rear에 원소를 삽입 
  1) *rear = *rear + 1      // rear의 위치를 +1
  2) queue[*rear]           // rear에 item을 삽입
• DeleteQ (Dequeue): 큐의 front의 원소 삭제
  1) *front = *front + 1            // front의 위치를 +1
  2) return queue[*front]      // 삭제 후 마지막 item 꺼냄

 

=> rear와 front를 두고, 이를 증가시키며 item을 삽입 or삭제!

 

 

 

원형 큐 (Circular queue)

큐의 문제점은 job queue에서 드러난다.

큐가 full 되었을 시에, 전체 큐를 삭제되어 빈칸이 존재하는 왼쪽으로 옮겨야 한다. 이는 시간을 크게 소모하게 된다.

원형 큐를 통해 이를 해결할 수 있다.

 

원형 큐는 queue[마지막 칸] -> 다음이 queue[0] 인 큐이다.

 

 

 

[python] 큐의 구현

1. 리스트로 큐 흉내내기
- 삽입 : q.append()
- 삭제 : q.pop()

 

pop시 자동으로 리스트를 옆으로 미뤄주므로 편리!

2. deque 사용

from collections import deque
- 생성 : q = deque([1, 2, 3])
- 삽입 : q.append()
- 삭제 : q.popleft()

 

3. queue 사용
from queue import Queue
- 생성 : q = Queue()
- 삽입 : q.put()
- 삭제 : q.get()