Queue is a linear data structure which follows FIFO i.e. First-In-First-Out method. The two ends of a queue are called Front and Rear, where Insertion always takes place at the Rear and the elements are accessed or removed from the Front. While implementing queues using arrays: - We cannot increase the size of array, if we have more elements to insert than the capacity of array.
- If we create a very large array, we will be wasting a lot of memory space.
Therefore if we implement Queue using Linked list we can solve these problems, as in Linked list Nodes are created dynamically as an when required. So using a linked list we can create a Queue of variable size and depending on our need we can increase or decrease the size of the queue. Thus instead of using the head pointer with Linked List, we will use two pointers, front and rear to keep track of both ends of the list, so that we can perfrom all the operations in O(1).
![]() Source Code - C++Time Complexity - Each Operation is O(1)
|
