Queue

Posted on | In

Queue is a linear data structure where insertion of items takes place at the rear and deletion takes place at the head - Following the FIFO principal: First In First Out.

Queue and stack have many features in common. They are linear data structures, so they both can be implemented based on an array or a list. The insertion and deletion of items are not allowed to take place at the middle of the data structure. There is only one difference: for stack, the insertion and deletion takes place at one end; for queue, the two operations takes place at different ends - and this has made all the differences on how these two data structures are used.

Applications of queue include:

  • BFS
  • Producer-Consumer problem, e.g. message queue

Implementation of Queue

There are three basic operations:

  • enqueue: insert a new item at the rear
  • dequeue: delete the item at the head
  • peek: access to the item at the head

As mentioned above, queue can be implemented based on an array or a list. Actually, in Java, the class LinkedList implements the interface Queue and can be directly used as a queue.

Unlike stack, where the push operations reuse the space left by the pop operations, queue does not make good use of the space. If you use an array of fixed size to implement a queue, you will soon run out of space, but there is a solution to this problem - circular queue.

Circular queue

A circular queue is a queue built on a fixed-size array where the first position is connected to the last position to make a circle. In this way, the space left by the dequeue operations can be reused.

The trick to implement a circular queue is to manipulate the head pointer and rear pointer in a circular way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class CircularQueue<T> {
    private List<T> array;
    private int len;
    private int head;
    private int rear;
    private int count;

    public CircularQueue(int len) {
        this.len = len;
        this.array = new ArrayList<>(len);
        head = 0;
        rear = 0;
        count = 0;
    }

    public void enqueue(T obj) {
        if (count == len) {
            throw new RuntimeException();
        }
        rear = (rear + 1) % len;
        array.set(rear, obj);
        count++;
    }

    public T dequeue() {
        if (count == 0) {
            throw new RuntimeException();
        }
        T obj = array.get(head);
        head = (head + 1) % len;
        count--;
        return obj;
    }

    public T peek() {
        if (count == 0) {
            throw new RuntimeException();
        }
        return array.get(head);
    }
}

Double ended queue

Double ended queue, aka. deque, supports the insertion and deletion of items at both ends. Thus, it can be used as either a queue or a stack.

A deque can be implemented using a double-linked list or a circular array.

Applications of deque:

  • A-Steal job scheduling algorithm
  • undo operations: note that stack can be used for the undo operations, but when the stack gets too full, it’s unlikely to remove the oldest operations from it, so deque is used instead of stack to make it more workable
  • palindrome checker

Priority queue

A priority queue is a regular queue except that an element with high priority is always served before an element with low priority. Thus, when an item is inserted into a priority queue at the rear, the items in the queue will be sorted, and the item with the highest priority will be moved to the head.

This sounds like a heap, right? A priority queue can be implemented with a heap, but apart from a heap, it can use a self-balancing binary search tree or other data structure. In Java, there is no collection class implementing heap, but we can use PriorityQueue for substitution.