Queue Data Structure

Queue is a collection of elements that accepts input of new elements from one side and removal from the other side. Queue is a data structure based on the First In First Out (FIFO) principle. The side which accepts new entries is the back side of the queue and the elements are removed from front side.

Queues and Stacks can be used as a buffer to keep some data for later processing and is an important part of the Backtracking concept, which forms the code of most algorithms of data structures.

Queues can be considered as an Abstract Data Type (ADT), since these are modified versions of either Linked List or Array data structures. To these data structures, if we just add two more functionalities (methods), it becomes a queue. First is a push() method that inserts elements to the back of the queue. Second is a pop() method to remove elements from the front.

Another common method that most queue implementations have is a peek() method, that fetches the first element without actually removing it.

Let us see how we can convert an Array or Linked List to Queue. We will use Java because, Java has built-in Array and Linked List data structures.

Queue implementation using Array Data Structure

Let us see how we can make a Queue out of an Array. We are going to add 3 functionalities to push data to the rear end of the array, fetch data from the front, and peek the first item without actually removing it.

In push() method, we are checking if all the nodes are occupied. If not, data is inserted to last position.

In pop() method, check if at-least one item is present. If so, it is removed from the array and returned. Rest of the items are shifted to the next position so that we can always insert items to the limit of the array.

peek() method returns the first element of the array, without removing it.

class Queue   
{
    private int itemsCount;
    private int[] arry;
    
    Queue(int size)  
    {
        this.itemsCount = 0;
        this.arry = new int[size];
    }  
  
    public void push(int num)  
    {
        if(itemsCount < arry.length) {
            arry[itemsCount] = num;
            itemsCount++;
            System.out.println(num + ", added to queue");
        }
        else {
            System.out.println("Max size reached");
        }
    }

    public int pop()
    {
        int popItem = -1;
        if(itemsCount > 0) {
            popItem = arry[0];
            for (int i = 0; i < itemsCount; i++) {
                arry[i] = arry[i + 1];
            }
            itemsCount--;
        }
        return popItem;
    }

    public void peek()  
    {
        if(itemsCount > 0) {
            System.out.println("First item : " + arry[0]);
        }
        else {
            System.out.println("Queue is empty");
        }
    }
    public static void main(String[] args)   
    {  
        Queue q = new Queue(5);
        q.push(1);
        q.push(2);
        q.push(3);
        System.out.println(q.pop() + ", removed from queue");
        System.out.println(q.pop() + ", removed from queue");
        q.peek();
        System.out.println(q.pop() + ", removed from queue");
        q.peek();
        q.push(4);
        q.push(5);
        q.peek();
        q.push(6);
        q.push(7);
  }  
}

Output: 1, added to queue 2, added to queue 3, added to queue 1, removed from queue 2, removed from queue First item : 3 3, removed from queue Array is empty 4, added to queue 5, added to queue First item : 4 6, added to queue 7, added to queue

Queue implementation using Linked List Data Structure

Java has a built-in LinkedList data structure within java.util.LinkedList namespace. And there are built-in methods as well to make the LinkedList work like a queue. Let us check which methods can be used to make a linked list work like a queue.

Use push() method to insert data to the rear end of the queue.

Use pollLast() method to remove and return the first element.

Use peekLast() to check the first element, without removing it.
Copied

import java.util.LinkedList; class Queue { public static void main(String[] args) { LinkedList<Integer> ll = new LinkedList<Integer>(); ll.push(1); ll.push(2); ll.push(3); System.out.println(ll.pollLast() + ", removed from queue"); System.out.println(ll); System.out.println(ll.peekLast()); ll.push(4); System.out.println(ll); System.out.println(ll.peekLast()); } }
Output: 1, removed from queue [3, 2] 2 [4, 3, 2] 2
When to use Linked List and when to use Array for a Queue

Fixed length based queues are of not much use in real-world scenarios. Can be used when we know the maximum size use it only for shorter length queues. Using dynamic arrays to build queues is followed in some languages.

Linked List based queues perform better for larger sized data and if we are not sure about the maximum size.

As we know, Linked Lists perform better than arrays for insert, update and delete tasks, queues based on Linked List gives the optimum performance in most cases, since insert and delete are the most frequent operations happening in a queue.
Types of Queues

Different types of queues can be implemented to perform some practical applications. Let us see some of those.
1. Deque
  
  Deque is the abbreviation for Double Ended Queue. Deques allow inserting or removing elements from both sides of the queue.
  
  Deques are generally implemented using a Doubly Linked List or sometimes using a Dynamic Array. Practical applications include some algorithms like Work Stealing Algorithm.
2. Priority Queue
  
  For Priority Queues a priority number is also given while inserting the value. Elements with highest priority is removed and returned when using pop() function, instead of the first element. For two elements with same priority, first inserted element is returned in most implementations.
  
  Priority Queues can be implemented using a Heap Data Structure or Linked List or Ordered Arrays.
  
  Algorithms like Dijkstra's Algorithm, Huffman Coding, BFS, Prim's Algorithm, etc can be implemented using Priority Queues.

Queue Data Structure

Queue implementation using Array Data Structure

Queue implementation using Linked List Data Structure

When to use Linked List and when to use Array for a Queue

Types of Queues

Deque

Priority Queue