Tagged
• Data Structure
• Queue
•

Introduction

Queue is a linear data structure to store and manipulate data which follows FIFO (First In First Out) order during adding and removing elements in it. There are two basic ways to implement queue data structure :

• Array based Implementation Using Array or Static Array (Array size is fixed and has to be given during initialization) Using Dynamic Arrays or Resizable Arrays (Arrays can grow or shrink based on requirement)

In this post we are going to discuss about linked list based implementation of queue data structure. Before proceeding with this post, it is highly recommended to understand what is linked list and how queue operations are performed.

Prerequisite

In a linked list, whenever we want to add/delete an element we either add/delete at the beginning or at random position or at the end of the linked list. Whereas in case of queue we do restrict adding elements at one end point (which is known as last or rear or back) and removing elements at other end (which is known as first or front or front) to maintain First In First Out ordering. So we need to maintain two pointers first and last to perform queue operations.

Algorithm

Queue algorithm is defined in terms of adding an element which is called Enqueue and removing an element from the queue which is called Dequeue.

Initialization :

• Initialize variable last which points to the last node of the linked list.
• Initialize variable first which points to the front first node of the linked list.

If there are no elements in the queue, both first and last node points to null and peek element always points first node.

Enqueue Algorithm

1. Create a new node for the data given. Let us assume newly created node as newNode

2. If queue is empty (no elements left in the queue)

• update first and last to newNode
3. Else

• in this case newNode will be the last element and the current last element will be the oldLast element.

• update newNode as the last element.

• oldLast element next points to the last node in the queue.

```1void enqueue(int data) : 2      Node newNode = new Node(data) 3      if(first == null) : 4            last = newNode 5            first = newNode  6      else : 7        // store last node in oldLast 8        Node oldLast = last  9
10        // update newNode as the last element11        last = newNode  12
13        // add connection to last element 14        oldLast.next = last ```

Dequeue Algorithm

1. If queue is empty (first == null)
• throw exception
2. Else
• remove the first element by updating first = first.next
```1int dequeue() : 2    if(first == null) :3      throw exception4
5    else :   6       Node peek = first 7
8       // remove first element by updating first to next element9       first = first.next  10    return peek.data ```

Queue Operations Dry Run

To understand enqueue and dequeue operations clearly, let us perform enqueue and dequeue operations. Let us consider there are few persons standing in a queue at a ticket counter and each gets ticket at some time.

• Empty Queue at ticket counter

• Person p1 entered into queue to get ticket. As p1 is the only person in the queue, he is the first and last person in the queue

• Person p2 entered into the queue to get ticket. As p1 already in queue, p2 will be the last person in the queue

• Person p3 entered into the queue, so the last person in the queue will be updated to p3 from p2.

• Person p1 got ticket and he left the queue, so the person standing behind him i.e., p2 is now becomes first person in the queue.

• Person p4 entered into the queue, so the last person in the queue will be updated to p4 from p3.

• Person p5 entered into the queue, so the last person in the queue will be updated to p5 from p4

• Person p2 got ticket and he left the queue, so first person in the queue will be p3.

Java Implementation

```1public class QueueUsingLinkedList {2
3    // Node class4    class Node {5        Node next;6        int data;7
8        public Node(int data) {9            this.data = data;10        }11    }12
13    // Initialize two pointers first and last14    // first always for deque(removing) 15    // last is always for enqueue(adding)16    private Node first;17    private Node last;18
19    // enqueue method to add element at end of the queue20    public void enqueue(int data) {21        // create new node for given data22        Node node = new Node(data);23
24        // if queue is empty, newly created node will be the25        // first and last node in the queue26        if(isEmpty()) {27            last = node;28            first = node;29            return;30        }31        // Queue already has some nodes32        // newly created node will be the last node of the queue33        Node oldLast = last;34        last = new Node(data);35        oldLast.next = last;36    }37
38    // dequeue method to remove element at front of the queue39    public int dequeue() {40        if(isEmpty()) {41            throw new RuntimeException("Queue Underflow");42        }43        // capture the data of first node in the queue44        int data = first.data;45
46        // now remove first by updating first to its next element47        first = first.next;48
49        // if queue does not have any elements50        // update last to null51        if(isEmpty()){52            last = null;53        }54        return data;55    }56
57    // method to return peek element of the queue58    public int peek() {59        if(isEmpty()) {60            throw new RuntimeException("Queue Underflow");61        }62        return first.data;63    }64
65    // method to check queue is empty or not66    public boolean isEmpty() {67        return first == null;68    }69
70    // Method to print queue data71    public void print() {72        Node current = first;73        System.out.println("Elements in queue are");74        while(current != null){75            System.out.print(current.data+" -> ");76            current = current.next;77        }78        System.out.println("NULL");79    }80
81    // driver method82    public static void main(String[] args) {83        QueueUsingLinkedList queue = new QueueUsingLinkedList();84        for(int i=0;i<10;i++){85            queue.enqueue(i);86        }87        queue.print();88        System.out.println("Dequeue Operation");89        for(int i=0;i<5;i++){90            System.out.println("Element removed from queue is "+queue.dequeue());91        }92        System.out.println("End of Dequeue Operation");93        queue.print();94    }95
96}```

• Data Structure
• Queue