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.
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.
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 #include // 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
Queue using linked list
Queue using an array - drawback
If we implement the queue using an array, we need to specify the array size at the beginning[at compile time].
We can't change the size of an array at runtime. So, the queue will only work for a fixed number of elements.
Solution
We can implement the queue data structure using the linked list.
In the linked list, we can change its size at runtime.
Basic Operation:
Following are basic operations of Queue:
Main Queue Operations:
1]EnQueue[]: Inserts an element at the rear of the Queue.
2]DeQueue[]: Remove and return the front element of the Queue.
Auxiliary Queue operation:
1]Front[]: Display the data front of the Queue.
2]QueueSize[]: Returns the number of elements stored in the Queue.
3]display[]: Display elements of queue.
There are many different operations that we can implement.
For ex.:- Merging of Two Queue,Sorting of Queue etc..
- Let's see implementation of Queue and its operations,with example.
For linked list we will make structure of Node using struct keyword.In which we here taking int data and one pointer of that struct to point another Node. - First we will take two pointers of that struct Node, front=NULL and rear=NULL.
EnQueue
Inserting an element in Queue.
- Initially both of our pointers pointing to the front and rear are NULL.
- Now,If We enter the 12 in Queue we will checking weather there is any element present or not.If rear is NULL,We make our front and rear pointers to point our newly inserted Node with having data '12'.
- Now,again if we want to enter new data,Let say 45.We will check for rear NULL or not.Now our rear would be pointing to '12'.So 45 will added next to the rear Node and 45 would be our rear Node.
- Same way if i add 26, it would be added after 45 and rear will point to the Node having data '26'.
Pseudocode:
DeQueue
Deleting an element from Queue.
- Now, by doing three EnQueue operation we will be having Queue having 3 elements as shown in figure.
- First we check that front is NULL?If it is then Queue is empty we can not perform DeQueue operation.But here front will be pointing to '12'.
- So if we want to delete element from Queue. As our Queue is FIFO[first in first out] 12 is first inserted, so 12 will be removed.Our front pointer will be pointing to the '12'.To,remove it first we make our front pointer to point the element inserted after '12'.And then simply we free the memory.
- As simple as that 45 and 26 will be removed if we perform two more DeQueue operation.And again our Queue will be empty[rear and front will be eqal to NULL].
Display
- To display all elements present in Queue, we will take one temp[you can give whatever name you want] pointer and make that to point front.
- Then we traverse up-to rear or we can say temp!=NULL using temp=temp->next [which will make our pointer to move towards rear] and print temp->data.