Queue – Linked List Implementation
In the previous post, we introduced Queue and discussed array implementation. In this post, linked list implementation is discussed. The following two main operations must be implemented efficiently.
In a Queue data structure, we maintain two pointers, front and rear. The front points the first item of queue and rear points to last item.
enQueue() This operation adds a new node after rear and moves rear to the next node.
deQueue() This operation removes the front node and moves front to the next node.
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | #include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; // integer data struct Node* next;// pointer to the next node }*rear = NULL, *front = NULL; // Utility function to allocate the new queue node struct Node* newNode(int item) { // allocate a new node in a heap struct Node* node = (struct Node*)malloc(sizeof(struct Node)); // check if the queue (heap) is full. Then inserting an element would // lead to heap overflow if (node != NULL) { // set data in the allocated node and return it node->data = item; node->next = NULL; return node; } else { printf("\nHeap Overflow"); exit(EXIT_FAILURE); } } // Utility function to dequeue the front element int dequeue()// delete at the beginning { if (front == NULL) { printf("\nQueue Underflow"); exit(EXIT_FAILURE); } struct Node* temp = front; printf("Removing %d\n", temp->data); // advance front to the next node front = front->next; // if the list becomes empty if (front == NULL) { rear = NULL; } // deallocate the memory of the removed node and optionally return the removed item int item = temp->data; free(temp); return item; } // Utility function to add an item to the queue void enqueue(int item)// insertion at the end { // allocate a new node in a heap struct Node* node = newNode(item); printf("Inserting %d\n", item); // special case: queue was empty if (front == NULL) { // initialize both front and rear front = node; rear = node; } else { // update rear rear->next = node; rear = node; } } // Utility function to return the top element in a queue int peek() { // check for an empty queue if (front != NULL) { return front->data; } else { exit(EXIT_FAILURE); } } // Utility function to check if the queue is empty or not int isEmpty() { return rear == NULL && front == NULL; } int main() { enqueue(1); enqueue(2); enqueue(3); enqueue(4); printf("The front element is %d\n", peek()); dequeue(); dequeue(); dequeue(); dequeue(); if (isEmpty()) { printf("The queue is empty"); } else { printf("The queue is not empty"); } return 0; } |
DownloadRun Code
Java Program to Implement the queue data structure
In this example, we will learn to implement the queue data structure in Java.
To understand this example, you should have the knowledge of the following Java programming topics:
- Java Queue Interface
- Java Generics
Linked List implementation of Queue
Due to the drawbacks discussed in the previous section of this tutorial, the array implementation can not be used for the large scale applications where the queues are implemented. One of the alternative of array implementation is linked list implementation of queue.
The storage requirement of linked representation of a queue with n elements is o(n) while the time requirement for operations is o(1).
In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each element of the queue points to its immediate next element in the memory.
In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue.
Insertion and deletions are performed at rear and front end respectively. If front and rear both are NULL, it indicates that the queue is empty.
The linked representation of queue is shown in the following figure.