Java

About Queues

Queues are opposite of stacks, they are implemented as a first in first out basis. They are used across many different applications such as printers, and web servers.

It is exactly like a line of queue in the real world. People line up from the back, and is served at the front according to their turn.

Queue Usages in applications

We use queue when programming requires a shared resource among many consumers, these consumers would form a queue and await for resource availability.

a few notable examples:

Printer Jobs
Operating system processes
Web servers
Live support systems (Live chat customer services)

Common Queue operations

Similiar to stacks, the following common queue operations all run at O(1) constant time complexity.

enqueue adds an item to the queue
dequeue removes an item from the queue
peek returns the item in the queue without removing it
isEmpty bool if queue is empty
isFull bool if queue is full.

Conventions in Java

The Java framework provides the queue interface that sets the guidelines of implementing a queue.

Java
public class Queue<E> implements Queue<E> {
    @Override  
    public boolean add(Object o) {  
        return false;  
    }  
      
    @Override  
    public boolean offer(Object o) {  
        return false;  
    }  
      
    @Override  
    public Object remove() {  
        return null;  
    }  
      
    @Override  
    public Object poll() {  
        return null;  
    }  
      
    @Override  
    public Object element() {  
        return null;  
    }  
      
    @Override  
    public Object peek() {  
        return null;  
    }  
      
    @Override  
    public int size() {  
        return 0;  
    }  
      
    @Override  
    public boolean isEmpty() {  
        return false;  
    }  
      
    @Override  
    public boolean contains(Object o) {  
        return false;  
    }
    //... and more
}

Here there are 2 note worthy differences in naming conventions:

add & remove works the same as enqueue and dequeue
offer(E e) attempts to enqueue an item to the queue, will not throw an exception if fails.
poll(E e) attempts to dequeue, and returns null if the list is empty instead of throwing an exception.
element() is an unsafe version of peek(), will throw an exception instead of returning null when queue is empty.

Usecase: Reverse a queue

We can use a stack to reverse a queue.

C#
public static void reverse(Queue<int> queue) {
    var stack = new Stack<int>();
    while(queue.Count > 0) {
        stack.Push(queue.Dequeue());
    }
    
    while(stack.Count > 0) {
        queue.Enqueue(stack.Pop());
    }
}

Implementations

A basic structural bone

A queue implementation using an array.

C#
public class Queue<T> {
    private T[] storage;
    private int lastEmptyIndex = 0;
    private int headIndex = 0;
    
    public Queue<T>(int size) {
        storage = new T[size];
    }
    
    public void enqueue(T item) {
        if (isFull()) 
            throw new Exception("Queue is full");
            
        this.storage[lastEmptyIndex++] = item;
    }
    
    public T dequeue() {
        if (isEmpty())
            throw new Exception("Queue is empty");
            
        return this.storage[headIndex++];
    }
    
    public bool isEmpty() {
        return this.lastEmptyIndex < 1;
    }
    
    public bool isFull() {
        return this.lastEmptyIndex >= this.storage.Length;
    }
}

However, there are a few limitations with this implementation. The head after dequeuing does not reset. Thus, we cannot add any more items once the rear index is maxed out.

Plain Text

On a fully loaded queue
[0] [1] [3] [4] [5]
 ^               ^
 head            tail
 
Dequeue. The frame does not shift.
[0] [1] [3] [4] [5]
     ^           ^
     head        tail

Circular array solution

Let's look at the previous implementation issue and solve it.

Plain Text

On a fully loaded queue
[0] [1] [3] [4] [5]
 ^               ^
 head            tail
 
Dequeue. 
[0] [1] [3] [4] [5]
     ^           ^
     head        tail
     
Enqueue new item.
[0] [1] [3] [4] [5] ...
     ^               ^
     head            tail. Out of bounds.

Because of the way we keep track of the tail, even when the queue is freed up, our tail will point in an incremental direction.

To solve this efficiently we should not try to resize the array, or perform a copy and frameshift. Instead we should make our tail pointer point back to origin.

Plain Text

Dequeue. 
[0] [1] [3] [4] [5]
     ^           ^
     head        tail
     
Enqueue new item. 
[0] [1] [3] [4] [5]
 T   H                Here tail should point back to 0.

We use the modulus operator to have the head and tail index to always revert back to 0 when they go beyond the size of our array.

Here's the full implementation.

C#
public class Queue<T> {
    private int count = 0;
    private int headIndex = 0;
    private int tailIndex = 0;
    
    private T[] storage;
    private int size
    
    public Queue<T>(int size) {
        storage = new T[size];
        this.size = size;
    }
    
    public void enqueue(T item) {
        if (isFull()) 
            throw new Exception("Queue is full");
            
            
        this.storage[tailIndex] = item;
        
        tailIndex = (tailIndex + 1) % size;
        count++;
    }
    
    public T dequeue() {
        if (isEmpty())
            throw new Exception("Queue is empty");
        
        var item = this.storage[headIndex];
        headIndex = (headIndex + 1) % size;
        count--;
        
        return item;
    }
    
    public bool isEmpty() {
        return this.count < 1;
    }
    
    public bool isFull() {
        return this.count >= this.size;
    }
}

Implementation - using stack

Stacks are exact polar opposites of Queues. Building a Queue using a stack requires reversing the stack order.

This of course is not an efficient implementation, as everytime we dequeue, we need to reverse the stack order.

C#
public class Queue<T> {
    private Stack<T> storage
    
    public Queue<T>(int size) {
        storage = new Stack<T>(5);
    }
    
    public void enqueue(T item) {
        storage.push(item);
    }
    
    public T dequeue() {
        var newStorage = new Stack<T>(5);
        
        while (!storage.isEmpty()) {
            newStorage.push(storage.pop())
        }
        var item = newStorage.pop();
        
        while(!newStorage.isEmpty()) {
            storage.push(newStorage.pop());
        }
        
        return item;
    }
}

Priority Queues

In priority queues objects are process and sorted according to an arbitrary priority not, by its order of insertion

Java
PriorityQueue<Integer> queue = new PriorityQueue();
queue.add(5);
queue.add(1);
queue.add(3);
queue.add(2);

while (!queue.isEmpty()) {
    System.out.println(queue.remove());
}

When you add an item to the queue and process them...

Plain Text

>>>
1
2
3
4
5

Process finished with exit code 0

Implementations

We will implement the Priority queue using an array. The items must be sorted via an ascending order.

The first problem of this implementation is how to shift the numbers in our Array

Plain Text

            insert(2)
            [1, 3, 5, 7]
Index:       0  1  2  3

If we try to insert the number 2 between 1 and 3. We need to shift 3, 5, and 7. However a tyical loop wont be so ideal as you can see.

Plain Text

[1, 3, 5, 7]
    ^
items[i + 1] = items[i]


[1, 3, 3, 7]   ??       Doing so lost num 5.
    ^   
items[i + 1] = items[i]

Instead, a common approach is to loop the array in reverse order:

Plain Text

[1, 3, 5, 7]
          ^
items[i + 1] = items[i]

[1, 3, 5, 7, 7]
          ^   
items[i + 1] = items[i]


[1, 3, 5, 7, 7]
       ^   
items[i + 1] = items[i]

[1, 3, 5, 5, 7]
       ^   
items[i + 1] = items[i]

Array based priority queue

We start by declaring a simple array with a predefined size. We will work on resizing later on.

Java
public class PriorityQueue {
    private int[] queue = new int[5];
    private int count = 0;
    
    public PriorityQueue() {
        
    }
    
    public void enqueue(int item){
        for (int i = count - 1; i >= 0; i--) {
            if (queue[i] > item)
                queue[i + 1] = queue[i];
            else {
                queue[i + 1] = item;
                count++;
                break;
            }
        }
    }
    
    @Override 
    public String toString() {
        return Arrays.toString(queue);
    }
}

We can continue and apply an array resizing block that expands the array when its full:

Java
public void enqueue(int item){
    if (count == queue.length) {
        var newQueue = int[count * 2];
        queue = newQueue;
    }
    
    for (int i = count - 1; i >= 0; i--) {
        if (queue[i] > item)
            queue[i + 1] = queue[i];
        else {
            queue[i + 1] = item;
            count++;
            break;
        }
    }
}

and a dequeue method that discards the largest item in the queue (from the back of the array):

Java
public int dequeue() {
    if (isEmpty()) {
        throw new IllegalStateException();
    }
    
    return items[--count];
}

public boolean isEmpty() {
    return (count == 0);
}