Different Implementation of Queue

Definition

A queue implementation is the technique used to represent and operate a queue data structure in memory so that elements can be inserted at the rear and removed from the front according to FIFO order.

A queue can be implemented in multiple ways, such as:

Array-based implementation

Circular queue implementation

Linked list implementation

Deque-based or stack-based implementation

The choice of implementation depends on factors like memory efficiency, simplicity, insertion/deletion speed, and whether the queue size is fixed or dynamic.

Main Content

1. Array Implementation of Queue

Concept and structure

In an array implementation, queue elements are stored in a linear array. Two indices are usually maintained:

• front → points to the first element
• rear → points to the last inserted element

Initially, both may be set to -1 to indicate an empty queue.

Operations and behavior

• Enqueue (insert): Insert an element at the rear end and increment rear.
• Dequeue (delete): Remove an element from the front end and increment front.
• Peek/Front: Read the element at the front without removing it.

Example:

  Queue: [10, 20, 30]
  front -> 10
  rear  -> 30

Advantages and limitations

• Simple to understand and implement.
• Access is direct using array indexing.
• However, if elements are removed from the front, empty spaces may be wasted.
• In a normal linear array queue, when rear reaches the end of the array, no more elements can be inserted even if there is free space at the beginning.

2. Circular Queue Implementation

Concept and structure

A circular queue solves the waste problem of a linear array queue by treating the array as circular. The last position is logically connected to the first position, so when rear reaches the end of the array, it can wrap around to the beginning if space is available.

Pointer movement

The queue uses modulo arithmetic:

• rear = (rear + 1) % size
• front = (front + 1) % size

Example with size 5:

  Index:  0   1   2   3   4
  Queue: [ _ | _ | _ | _ | _ ]

  Insert 10, 20, 30
  front = 0, rear = 2

  Delete 10, 20
  front = 2, rear = 2

  Insert 40, 50
  rear wraps around to 0 and 1

Advantages and limitations

• Better space utilization than a simple linear queue.
• Avoids false overflow when unused space exists at the front.
• More efficient for repeated insertion and deletion.
• Slightly more complex because wrap-around logic must be handled carefully.
• Needs proper full and empty condition checks.

3. Linked List Implementation of Queue

Concept and structure

In a linked list implementation, the queue is formed using nodes. Each node contains:

• Data
• A pointer/reference to the next node

Two pointers are maintained:

• front → points to the first node
• rear → points to the last node

Operations and behavior

• Enqueue: Create a new node and attach it to the end of the list.
• Dequeue: Remove the node from the front and move front to the next node.
• If the queue becomes empty after deletion, both front and rear are updated appropriately.

Example:

  front -> [10] -> [20] -> [30] -> NULL
                               rear

Advantages and limitations

• Dynamic size, so it grows and shrinks as needed.
• No fixed size limit unless memory is exhausted.
• No space wastage due to preallocated unused slots.
• More memory is needed for storing pointers.
• Implementation is slightly more complex than array-based queue.

Working / Process

1. Insert elements at the rear

• In every queue implementation, insertion happens at the rear.
• The exact method depends on the structure:
  • Array: place element at the next rear index
  • Circular queue: place element using wrap-around index
  • Linked list: create a node and link it at the end

2. Remove elements from the front

• Deletion always happens from the front.
• The front element is processed first, and then the front pointer or index is moved forward.

3. Maintain queue state

• The implementation must correctly track whether the queue is:
  • Empty
  • Full
  • Partially filled
• This state management is essential for avoiding errors such as overflow, underflow, or incorrect element access.

Advantages / Applications

Flexible implementation choices

Different implementations allow the queue to be used in different situations, such as fixed memory environments or dynamic memory environments.

Efficient real-world scheduling

Queues are used in job scheduling, printer queues, CPU process management, and buffering in networking systems.

Support for other algorithms

Queue implementations are essential in algorithms like breadth-first search, level-order traversal of trees, and producer-consumer systems.

Summary

• A queue can be implemented using arrays, circular arrays, or linked lists.
• Each implementation follows FIFO behavior but differs in memory usage and efficiency.
• The best implementation depends on whether the queue needs fixed size, dynamic size, or better space utilization.
• Important terms to remember: FIFO, front, rear, enqueue, dequeue, circular queue, linked list, overflow, underflow