Queue (Data structure)

The Queue data structure is one of the commonly used important data structures in computer science. A queue processes data according to the "First-In-First-Out" (FIFO) principle and reflects this characteristic in many true life scenarios. It is particularly used in process scheduling, source sharing, network communication, and simulation applications to ensure systems operate more active and just. Therefore, understanding the queue structure is critically important in algorithm design and software development.

Queue Structure Basic Terminology

• Front (Head): The position of the entry ready to be processed, that is, the first item to be removed from the queue, is called the front.
• Rear: The location of the last element added to the queue. It is the position where the next element will be inserted.
• Size: Represents the number of elements in the queue.
• Capacity: Indicates the maximum number of values the queue can hold.

Basic Queue Operations

Enqueue

• This is the operation of adding a new element to the queue.
• The element is added to the rear of the queue.

Dequeue

• This is the operation of removing an element from the queue.
• The element removed is the first one at the front of the queue.

Peek / Front

• This operation retrieves the value of the element at the front of the queue without removing it.

IsEmpty Check

• This checks whether the queue contains any elements.
• Returns true if the queue is empty, false if it is not.

isFull Check

• This checks whether the queue has reached its maximum capacity.
• Returns true if the queue is full, false otherwise.
• Primarily used in static queues.

Size Retrieval

• This is used to determine the number of elements currently in the queue.

Clear

• This removes all elements from the queue, making it empty.

Types of Queues

Simple Queue

A simple queue strictly follows the FIFO structure. Elements can only be added to the rear of the queue and removed from the front.

Double-Ended Queue (Deque)

In a double-ended queue, insertion and deletion operations can be performed at both ends. There are two types:

• Input-Restricted Queue: This is a simple queue in which input can only be accepted from one end, but deletion can occur from either end.
• Output-Restricted Queue: This is also a simple queue in which input can be accepted from either end, but deletion can only occur from one end.

Circular Queue

This is a special type of queue in which the last position is connected back to the first position. Operations still follow the FIFO order.

Priority Queue

A priority queue is a special queue in which elements are accessed according to their assigned priority. There are two types:

• Ascending Priority Queue: In an ascending priority queue, elements are arranged in increasing order of priority values. The element with the smallest priority value is removed first.
• Descending Priority Queue: In a descending priority queue, elements are arranged in decreasing order of priority values. The element with the highest priority is removed first.