Basic Operations on Queue in C++
The following are the basic operation on the queue in C++ that is implemented using linked list:
Operation | Description | Time Complexity | Space Complexity |
---|---|---|---|
Enqueue | It adds the new element to the end of the queue. | O(1) | O(1) |
Dequeue | It removes the element from the front of the queue. | O(1) | O(1) |
Peek | It retrieves but does not remove then the front element of the queue. | O(1) | O(1) |
IsEmpty | Returns true is the queue is empty otherwise returns false. | O(1) | O(1) |
Implementation of Basic Operations
The above basic operations are implemented using the following algorithms:
Algorithm of Enqueue
- Create the new node with the given data.
- Check if the queue is empty.
- If it is empty then set the front and rear pointers to this new node.
- If it is not empty then link the current rear nodes next pointer to this new node.
- Update the rear pointer to the point to the new node.
Algorithm of Dequeue
- Check if the queue is empty.
- If queue is empty then return from the function or throw an error.
- Save the current front node in the temporary variable.
- Move the front pointer to next node in the queue.
- Delete the old front node.
- If the queue becomes the empty then update the rear pointer to nullptr as well.
Algorithm of Peek
- Check if queue is empty.
- If queue is empty then throw the error or return the sentinel value indicating the queue is empty.
- Return the data from the front node.
Algorithm of isEmpty
- Return the true if the front pointer is nullptr otherwise return false.
C++ Program to Implement Queue using Linked List
Queue is the fundamental data structure that follows the First In, First Out (FIFO) principle where the elements are added at the one end, called the rear and removed from other end called the front. In this article, we will learn how to implement queue in C++ using a linked list.
Contact Us