Sequential Queue and Circular Queue: Definitions, Operations, and Java Implementation

The underlying structure of a queue is an array; the commonly used queue is a sequential queue whose data structure is defined with a head pointer (front) pointing to the first element and a tail pointer (rear) pointing to the position after the last element.

To avoid the complication when the queue contains only one element (head and tail coincide), two pointers are used: front points to the head element, and rear points to the position after the tail element. When front == rear the queue is empty; when front == rear + 1 the queue contains a single element.

Enqueue operation (push):

// send value to tail
queue[rear] = x;
// tail pointer +1
rear++;

Dequeue operation (pop):

// take head element
x = queue[front];
// head pointer +1
front++;

Sequential queues suffer from a false overflow problem: even when there is free space in the array, the tail pointer may reach the end of the array and prevent further enqueues. An example with an array of size 5 shows that after enqueuing A, B, C, D and dequeuing A and B, attempting to enqueue E fails because rear would exceed the array bounds.

Three ways to solve this issue are:

Allocate a larger storage space (low space utilization).

Shift all existing elements toward the head after each dequeue (high time complexity).

Use a circular queue, treating the head and tail as connected in a ring.

Therefore, a circular queue is the best solution for the false overflow problem.

Circular Queue

The circular queue data structure is defined with a fixed length array where the head and tail are connected to form a ring; when the tail reaches the last array position, the next position is the first element of the array.

Implementation steps:

Define an array and two pointers front and rear. Initially front = rear = 0, representing an empty queue.

Enqueue: check if the queue is full using (rear + 1) % capacity == front. If not full, store the element at queue[rear] and move rear = (rear + 1) % capacity.

Dequeue: check if the queue is empty with front == rear. If not empty, retrieve the element at queue[front] and move front = (front + 1) % capacity.

The number of elements at any time is (rear - front + capacity) % capacity.

Java implementation of a circular queue based on an array:

public class CircularQueue {
    // array to store elements
    private int[] data;
    private int front, rear;
    // array size
    private int capacity;

    public CircularQueue(int k) {
        capacity = k;
        data = new int[capacity];
        front = 0;
        rear = 0;
    }

    // enqueue
    public boolean enqueue(int element) {
        if (isFull()) {
            return false;
        } else {
            data[rear] = element;
            rear = (rear + 1) % capacity;
            return true;
        }
    }

    // dequeue
    public boolean dequeue() {
        if (isEmpty()) {
            return false;
        } else {
            front = (front + 1) % capacity;
            return true;
        }
    }

    // get front element
    public int front() {
        if (isEmpty()) {
            return -1;
        } else {
            return data[front];
        }
    }

    // get rear element
    public int rear() {
        if (isEmpty()) {
            return -1;
        } else {
            return data[(rear - 1 + capacity) % capacity];
        }
    }

    // check if empty
    public boolean isEmpty() {
        return front == rear;
    }

    // check if full (sacrificing one slot to distinguish empty and full)
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}

Key points summary:

Empty queue: front = rear Dequeue: front = (front + 1) % capacity Enqueue: rear = (rear + 1) % capacity Queue length: (rear - front + capacity) % capacity Full queue (one slot reserved):

(rear + 1) % capacity = front