A queue is an linear data structure that serves as a collection of elements, with three main operations: enqueue, dequeue and peek. We have discussed about these operations in previous post and covered array implementation of queue data structure. In this post, linked list implementation of queue is discussed.
A queue can be easily implemented using a linked list. In singly linked list implementation, enqueueing happens at the tail of the list and dequeueing of items happens at head of the list. We need to maintain pointer to the last node to keep O(1) efficiency for insertion.
Since a doubly linked list offers O(1) insertion and deletion at both ends, it can be used if we want enqueueing to happen in the beginning and dequeueing to happen at the tail of the linked list.
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 the new node in the heap struct Node* node = (struct Node*)malloc(sizeof(struct Node)); // check if queue (heap) is full. Then inserting an element would // lead to heap overflow if (node != NULL) { // set the data in allocated node and return the node node->data = item; node->next = NULL; return node; } else { printf("\nHeap Overflow"); exit(EXIT_FAILURE); } } // Utility function to remove front element from the queue 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 list becomes empty if (front == NULL) rear = NULL; // deallocate the memory of removed node and // optionally return the removed item int item = temp->data; free(temp); return item; } // Utility function to add an item in the queue void enqueue(int item) // insertion at the end { // Allocate the new node in the 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 top element in a queue int peek() { // check for 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; } // main function int main() { enqueue(1); enqueue(2); enqueue(3); enqueue(4); printf("Front element is %d\n", peek()); dequeue(); dequeue(); dequeue(); dequeue(); if (isEmpty()) printf("Queue is empty"); else printf("Queue is not empty"); return 0; } |
Output:
Inserting 1
Inserting 2
Inserting 3
Inserting 4
Front element is 1
Removing 1
Removing 2
Removing 3
Removing 4
Queue is empty
The advantage of using linked list over arrays is that it is possible to implement a queue that can grow or shrink as much as needed. Since each new node will be dynamically allocated, overflow is not possible unless heap memory is exhausted. Using static array will put a restriction to the maximum capacity of the array which can lead to queue overflow.
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply