Queues: Queues as ADT

Definition

A queue ADT is a linear abstract data type in which insertion is performed at one end called the rear and deletion is performed at the other end called the front, following the FIFO (First In, First Out) principle.

In a queue, elements are added using the enqueue operation and removed using the dequeue operation. The element that has been in the queue for the longest time is always the first to be removed.

Main Content

1. Queue as an Abstract Data Type (ADT)

A queue is called an ADT because it defines what operations are allowed and what behavior is expected, not how the data is stored internally.
The queue ADT usually includes operations such as:
enqueue(x): insert an element at the rear
dequeue(): remove an element from the front
front() / peek(): view the first element without removing it
isEmpty(): check whether the queue has no elements
isFull(): check whether the queue is full, mainly in fixed-size implementations

A queue ADT can be represented in many ways:

Array-based queue

Linked-list-based queue

Circular queue

Deque-based implementation for special cases

The essential point is that, regardless of implementation, the user experiences the same logical behavior. For example, if you place three customers into a service queue in the order A, B, C, then they must be served in the order A, then B, then C.

Example: If a queue contains:

Front → 10, 20, 30 ← Rear

enqueue(40) makes it:

Front → 10, 20, 30, 40 ← Rear

dequeue() removes 10, leaving:

Front → 20, 30, 40 ← Rear

2. Basic Queue Operations

Enqueue operation

This operation inserts a new element at the rear of the queue. It increases the number of elements by one. If the queue is full in an array implementation, insertion may fail or require resizing.

Dequeue operation

This operation removes the element at the front. It decreases the number of elements by one. If the queue is empty, deletion is not possible and may cause underflow.

Other commonly used operations include:

Front/Peek

returns the front element without deleting it

Rear

returns the last element

IsEmpty

checks whether the queue has zero elements

IsFull

checks whether the queue has reached its capacity

Illustration of operations:

Initial queue:

Front → 5, 8, 12 ← Rear

After enqueue(15):

Front → 5, 8, 12, 15 ← Rear

After dequeue():

Front → 8, 12, 15 ← Rear

These operations are usually designed to be efficient. In many implementations, enqueue and dequeue can be performed in constant time, O(1), because only the front and rear positions are accessed.

3. Representation and Implementation of Queues

Array implementation

A queue can be stored in a linear array. Two variables or pointers are usually maintained: front and rear.

front points to the first valid element
rear points to the last valid element

However, a simple linear array queue may waste space after repeated deletions because empty positions at the front cannot be reused easily.

Linked list implementation

A queue can also be implemented using a linked list.

Insertion happens at the tail
Deletion happens at the head

This implementation is flexible because the queue can grow dynamically as needed, limited only by memory.

Circular queue implementation

To solve the wasted-space problem in arrays, a circular queue connects the end of the array back to the beginning. This allows reuse of empty spaces created by deletions.

Example of array-based queue:

Suppose the queue has capacity 5 and contains:

Index: 0 1 2 3 4 Data : 11 22 33 _ _ Front = 0, Rear = 2

After deleting 11 and 22:

Index: 0 1 2 3 4 Data : _ _ 33 _ _ Front = 2, Rear = 2

If using a simple linear array, spaces 0 and 1 may remain unused. A circular queue solves this problem by wrapping around.

Example of linked list queue:

Head node represents the front
Tail node represents the rear
enqueue() inserts after the tail
dequeue() removes from the head

This makes the queue ADT easy to manage and efficient for dynamic data.

Working / Process

A new element is inserted at the rear using the enqueue operation.
Elements already in the queue move forward logically as the front element gets removed by dequeue.
The oldest element remains at the front and is always served first, preserving FIFO order.

Example process:

Start:

Front → A ← Rear

Enqueue B:

Front → A, B ← Rear

Enqueue C:

Front → A, B, C ← Rear

Dequeue:

Front → B, C ← Rear

This process continues until the queue becomes empty. If a dequeue is attempted on an empty queue, it results in underflow. If an enqueue is attempted in a fixed-size full queue, it results in overflow.

Advantages / Applications

Queues ensure fair and orderly processing because elements are handled in the exact order of arrival.
They are very useful in real-world systems such as printer spooling, CPU scheduling, traffic control, and customer service lines.
They are essential in many algorithms and computing tasks such as breadth-first search, buffering data streams, and handling asynchronous requests.

Common applications include:

Printer queues
CPU job scheduling
Keyboard buffering
Network packet buffering
Breadth-first traversal of graphs
Simulation of waiting lines
Request handling in servers

Because the queue ADT separates behavior from implementation, it can be adapted to many environments efficiently. For example, linked-list queues are good for dynamic size, while circular queues are good for fixed-size memory-efficient systems.

Summary

A queue is a linear ADT based on the FIFO rule.
Elements are inserted at the rear and removed from the front.
Common operations include enqueue, dequeue, peek, isEmpty, and isFull.
Important terms to remember: FIFO, front, rear, enqueue, dequeue, underflow, overflow.