Implementing Queues using Linked List
To implement a queue using a Linked List,
- Maintain two pointers, front and rear. The front points to the first item of the queue and rear points to the last item.
- enQueue(): This operation adds a new node after the rear and moves the rear to the next node.
- deQueue(): This operation removes the front node and moves the front to the next node.
Now, some of the implementations of queue operations are as follows:
- Create a class QNode with data members integer data and QNode* next (pointer to the next node)
- Create a class Queue with data members QNode front and rear
- Enqueue Operation with parameter x:
- Initialize QNode* temp with data = x
- If the rear is set to NULL then set the front and rear to temp and return (Base Case)
- Else set rear next to temp and then move rear to temp
- Enqueue has O(1) time complexity.
- Dequeue Operation:
- If the front is set to NULL return (Base Case)
- Initialize QNode temp with front and set front to its next
- If the front is equal to NULL then set the rear to NULL
- Delete temp from the memory.
- Dequeue has O(1) time complexity.
- Overall Space Complexity: O(N)
Queue Notes for GATE Exam [2024]
A Queue is defined as a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order. Queue is a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end. The element, which is first pushed into the order, the operation is first performed on that.
FIFO Property in Queue
Table of Content
- Implementing Queues using Arrays:
- Implementing Queues using Linked List:
- Implementation of Queue using Stack:
- Circular Queue:
- Priority Queue:
- Double Ended Queue:
- GATE Archives – Previous Years Questions on Queue:
Contact Us