![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
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 = newNode5 first = newNode6 else :7 // store last node in oldLast8 Node oldLast = last910 // update newNode as the last element11 last = newNode1213 // add connection to last element14 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 exception45 else :6 Node peek = first78 // remove first element by updating first to next element9 first = first.next10 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 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 {23 // Node class4 class Node {5 Node next;6 int data;78 public Node(int data) {9 this.data = data;10 }11 }1213 // 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;1819 // 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);2324 // 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 }3738 // 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;4546 // now remove first by updating first to its next element47 first = first.next;4849 // if queue does not have any elements50 // update last to null51 if(isEmpty()){52 last = null;53 }54 return data;55 }5657 // 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 }6465 // method to check queue is empty or not66 public boolean isEmpty() {67 return first == null;68 }6970 // 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 }8081 // 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 }9596}