Chapter 4: Queue

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

Queue

What is Queue?

▶ Logical (or ADT) level

 

Queue is an ordered group of homogeneous items (elements).

New elements are added at one end (the rear) -- enqueue.

Elements are removed from the other end (the front) -- dequeue.

 

A queue is a FIFO "First In, First Out" structure. (선입선출)

e.g., Job buffers, Network buffers, and many others (일을 순서대로 처리해야 되는 모든 상황)

 

※ buffer: 원하는 기능이 완성될 때까지 임시로 보관하는 기능

• 버퍼링 e.g., 영상 끊김 - 영상 재생을 위해 필요한 것들이 다 도착하지 않은 상황

Operations

▶ Logical Level

 

Definition

▶ Implementation Level

 

Queue Constructor

▶ Implementation Level

• 원형 큐(Circular Queue) 구현 방식
• + 1 을 해주는 이유는 큐에서 한 칸을 비워두기 위함임

 

 

원형 큐에서 한 칸을 비워두는 이유

1. 한 칸을 비워두지 않는다면

▶ 공백 상태와 포화 상태를 구별할 수 없다.

 

2. 한 칸을 비워둔다면

▶ 공백 상태와 포화 상태를 구별할 수 있다.

Queue Design Considerations 

option 1

▶ Time Complexity of Enqueue(): O(1)

▶ Time Complexity of Dequeue(): O(N)

 

option 2 - Improved

▶ Time Complexity of Dequeue(): O(1)

▶ Time Complexity of Eequeue(): O(1)

• rear = 0

Circular Queue!

 

Circular Queue

enqueue(1)

▶ rear = rear + 1

 

enqueue (2)

▶ rear = 0; if rear == maxQueue - 1

 

dequeue (1)

▶ front = front + 1

 

dequeue (2)

▶ front = 0; if front == maxQueue - 1

 

Problem 

▶ Case #1

Queue is Full! How do we know?

 

front == rear + 1

▶ Case #2

Queue is Empty! How do we know?

 

front == rear + 1

▶ Full vs. Empty

• Full과 Empty 사이의 ambiguity(모호성)를 해결해야 한다.

Solution

▶ Reserved Space

• reserved space: 실제로 값을 보관하지는 않고 항상 Queue의 front 역할을 하는 비어있는 공간이다.

Have a reserved space in front of the queue.
"front" always points to it.

 

▶ Full Queue - 1

Queue is Full! How do we know?

 

Rear + 1 == front

▶ Full Queue - 2

 

(rear + 1) % maxQueue == front

▶ Empty Queue

Queue is Empty! How do we know?

 

rear == front

▶ Comparison

 

reserved space를 두는 방법 말고도 length라는 변수를 만들면 Full과 Empty 구별이 가능하다.

 

Circular Queue with a Reserved Space

It allows us to distinguish "Full" from "Empty".

• Full: (rear + 1) % maxQueue == front
• Empty: rear == front

One memory location is wasted for the reserved space. (reserved space 사용 시 단점)

• e.g., integer, float array의 경우 4 byte가, short integer의 경우 2 byte가 버려진다. ( 한 칸만큼의 메모리 낭비)

 

Initialization

▶ Place the reserved space at the last location in the queue. (이렇게 해야 첫 칸부터 깔끔하게 채울 수 있음)

• You can place the reserved space at any location.

Review: Queue Constructor

▶ Implementation Level

• 동적 할당 -> Heap에 저장한다.

Queue Constructor

▶ Implementation Level

• 동적 할당이므로 메모리 할당 해제가 필요하다.

Queue Observers

▶ Implementation Level

 

enqueue() & dequeue()

▶ Implementation Level

• maxQueue는 현재 Queue의 size가 아니라, Queue의 최대 크기로 변하지 않는 값이다.
• front는 데이터가 담기지 않는 reserved space를 가리키기에,, 데이터를 꺼내올 땐 front + 1 로 꺼내주어야 한다.

Queue Operations

▶ Time Complexity

---

참고자료

https://shitandcomputer.tistory.com/67

원형큐 구현하기