Section 1.1: Sequential and Linked Queues

Just like stacks, queues are abstract data structures that adhere to the FIFO principle. They allow for insertion at the back and removal from the front. So, how can we implement a queue?

Queues can be constructed using either arrays or linked lists. The array-based queue is termed a sequential queue, while the linked list-based version is called a linked queue.

To illustrate, here’s a simple Java implementation using an array, complete with detailed comments for clarity:

// Array implementation of queue

public class ArrayQueue {

private String[] items; // array to hold elements

private int n = 0; // size of the array

private int head = 0; // index of the front of the queue

private int tail = 0; // index of the back of the queue

public ArrayQueue(int capacity) {

items = new String[capacity]; // initialize array

n = capacity; // set size

}

public boolean enqueue(String item) {

if (tail == n) return false; // queue full

items[tail] = item; // add item

++tail; // move tail pointer

return true;

}

public String dequeue() {

if (head == tail) return null; // queue empty

String ret = items[head]; // retrieve front item

++head; // move head pointer

return ret;

}

}

As you can see, the array implementation of a queue is slightly more complex than that of a stack. Unlike stacks, which require only a single pointer, queues necessitate two: one for the head (front) and another for the tail (back).

After enqueueing elements a, b, c, and d, the head points to index 0, while the tail points to index 4. If we call dequeue() twice, the head shifts to index 2, but the tail remains at index 4.

However, as we continue to add and remove items, both the head and tail shift along the array. When the tail reaches the end of the array, we can no longer add items, even if there’s free space remaining. How can we resolve this?

Previously, we encountered a similar issue where deleting an element from an array resulted in discontinuous data. We solved it through data movement. However, each dequeue operation here would involve moving every element, increasing the time complexity from O(1) to O(n). Can we optimize this?

Indeed, we can prevent data shifting during dequeue operations. If the array is full, we only perform data movement when enqueueing. Thus, we can modify the enqueue() method accordingly:

public boolean enqueue(String item) {

if (tail == n) {

if (head == 0) return false; // queue full

for (int i = head; i < tail; ++i) {

items[i - head] = items[i]; // shift data

}

tail -= head; // reset tail

head = 0; // reset head

}

items[tail] = item; // add item

++tail; // move tail pointer

return true;

}

Now, we can keep the dequeue() function as it is while allowing the enqueue() operation to handle data movement efficiently. This way, the dequeue operation retains a time complexity of O(1).

Next, we’ll examine the implementation of a queue using linked lists.

Section 1.2: Circular Queues

The challenge we faced in the array-based implementation was the need for data shifting when the tail reached the end of the array. To overcome this, we can implement a circular queue.

As the name suggests, a circular queue connects the head and tail, forming a continuous loop. Here's a diagram to visualize it:

In this structure, when a new element is added, instead of moving the tail pointer to the end of the array, we can wrap it back to the beginning, thereby avoiding data shifting altogether.

The conditions for determining if a circular queue is empty or full are slightly different from those of a linear queue. While it remains true that a queue is empty when head == tail, a queue is considered full if (tail + 1) % n == head.

Here’s a simple Java implementation of a circular queue:

public class CircularQueue {

private String[] items; // array to hold elements

private int n = 0; // size of the array

private int head = 0; // index of the front of the queue

private int tail = 0; // index of the back of the queue

public CircularQueue(int capacity) {

items = new String[capacity]; // initialize array

n = capacity; // set size

}

public boolean enqueue(String item) {

if ((tail + 1) % n == head) return false; // queue full

items[tail] = item; // add item

tail = (tail + 1) % n; // move tail pointer

return true;

}

public String dequeue() {

if (head == tail) return null; // queue empty

String ret = items[head]; // retrieve front item

head = (head + 1) % n; // move head pointer

return ret;

}

}

The circular queue implementation efficiently avoids data shifting, which is crucial for performance.

Blocking and Concurrent Queues

While the previous sections may seem theoretical, they play a crucial role in real-world applications. Basic queues may not be directly implemented in typical development, but specialized queues like blocking and concurrent queues are extremely valuable.

A blocking queue introduces blocking operations to a standard queue. Essentially, if the queue is empty, any attempt to retrieve data will halt until new data is added. Conversely, if the queue is full, attempts to insert data will pause until space becomes available.

This behavior is similar to the "Producer-Consumer model," where the producer generates data at a faster rate than the consumer can handle. The blocking queue coordinates the production and consumption rates effectively.

In a multi-threaded scenario, multiple threads operating on a queue simultaneously can lead to thread safety concerns. A concurrent queue ensures safe operations across threads, often implemented through locking mechanisms or atomic operations to maintain efficiency.