Tagged

Queue Using Linked List

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)
Linked List Based Implementation

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

Create a new node for the data given. Let us assume newly created node as newNode
If queue is empty (no elements left in the queue)
- update first and last to newNode
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 element
11        last = newNode  
12
13        // add connection to last element 
14        oldLast.next = last

Dequeue Algorithm

If queue is empty (first == null)
- throw exception
Else
- remove the first element by updating first = first.next

1int dequeue() : 
2    if(first == null) :
3      throw exception
4
5    else :   
6       Node peek = first 
7
8       // remove first element by updating first to next element
9       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 class
4    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 last
14    // 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 queue
20    public void enqueue(int data) {
21        // create new node for given data
22        Node node = new Node(data);
23
24        // if queue is empty, newly created node will be the
25        // first and last node in the queue
26        if(isEmpty()) {
27            last = node;
28            first = node;
29            return;
30        }
31        // Queue already has some nodes
32        // newly created node will be the last node of the queue
33        Node oldLast = last;
34        last = new Node(data);
35        oldLast.next = last;
36    }
37
38    // dequeue method to remove element at front of the queue
39    public int dequeue() {
40        if(isEmpty()) {
41            throw new RuntimeException("Queue Underflow");
42        }
43        // capture the data of first node in the queue
44        int data = first.data;
45
46        // now remove first by updating first to its next element
47        first = first.next;
48
49        // if queue does not have any elements
50        // update last to null
51        if(isEmpty()){
52            last = null;
53        }
54        return data;
55    }
56
57    // method to return peek element of the queue
58    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 not
66    public boolean isEmpty() {
67        return first == null;
68    }
69
70    // Method to print queue data
71    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 method
82    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}

...