adamwhiles dot com

Imagine standing in line at your favorite coffee shop, as you progress through the line, you move from the back to the front. Finally reaching the counter, getting your coffee and leaving the shop as a satisfied customer. This is a real-life representation of a queue. Queues operate on the first in first out principle, also known as FIFO.

What is a Queue Data Structure?

A queue data structure has some similarities to the stack data structure except for some terminology and the order that objects leave the data structure. When we add an object to the stack, we push it. In a queue, when we add an object, we call that enqueue. Likewise, to remove an object from a stack, we pop it. In a queue, when we remove objects, this is called dequeue.

Where are Queues Used in Programming?

• Printer Queue
• Uploading / Copying / Moving Multiple Files
• CPU Schedulers

Have you ever sent multiple print jobs to a printer? Notice in windows that there is a utility that shows what is in the print queue currently, these will be printed in a FIFO fashion. Depending on the type of file program, a general way to approach moving, uploading or copying multiple files would be using FIFO.

Similar to how implemented the stack using a linked list, we can do the same for a queue. Before we get to that, let’s look at a visual example of a queue data structure.

Queue Data Structure in Java

To implement a queue data structure in Java, we have a Node class, which represents the items being added to the queue. We also have a Queue class which keeps track of what item is at the front and rear of the queue, so when we add/remove items, we can do so with a O(1), constant time complexity. This is what we would refer to as a linked list, the nodes connect to each other using the next property of the Node class.

If you happen to be using Manjaro Linux as I am, you can follow this guide from the credibleDEV for Installing Java for VScode on Manjaro Linux.

// Node class, next pointer and value variable to hold the data
class Node {
    Node next;
    int value;
}

// Queue class which initializes the initial empty state of the queue and defines the enqueue/dequeue methods
class Queue {

    // Declare front, rear and size for tracking the current front/rear nodes and the queue size
    private Node front;
    private Node rear;
    private int size;
    
    public Queue() {
        // Initialize empty queue, front and rear=null, size=0
        this.front = null;
        this.rear = null;
        this.size = 0;
    }
    
    // Enqueue a new value in the queue
    public void enqueue(int value) {
        // Create a new node
        Node node = new Node();
        // Set the new nodes value
        node.value = value;
        
        if (node != null) {
            // Check if the queue is empty
            if (this.front != null) {
                this.rear.next = node;
                this.rear = node;
            } else {
                this.front = node;
                this.rear = node;
            }
            // Increase node size counter
            this.size++;
        }
    }
        
    // Remove the front node from the queue
    public void dequeue() {
        // Verify the queue is not empty
        if (this.front != null) {
        
            System.out.println("Removing item from front of the queue, value of: " + this.front.value);
            
            this.front = this.front.next;
            // Check if the queue is now empty
            if (front == null) {
                this.rear = null;
            }
            
            // Reduce the queue size counter by 1
            this.size--;

        } else {
            // Catch the case that the dequeue method is called on an empty queue
            System.out.println("Queue empty, nothing to remove");
        }
    }

}
   
// Main Program class
public class Main {
    public static void main(String[] args) {
    
        // Initialize a new queue instance called q
        Queue q = new Queue();
        
        // Enqueue items 1,2,3
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        
        // Dequeue items 1,2,3
        q.dequeue();
        q.dequeue();
        q.dequeue();
    }
}

Filed under: Languages,Data Structures,Java - @ October 12, 2022 7:23 am

Tags: data structure, fifo, java, linked list, queue