Queues
Last updated
Last updated
A Queue is a linear data structure that operates under the First-In, First-Out (FIFO) principle. It is open at both ends, with all additions to the list made at one end and all deletions from the list made at the other end. The operations are performed in FIFO order, meaning the element which is first pushed into the queue is the first one to be operated on. This is similar to a real-world queue such as a line of people waiting to purchase tickets, where the first person in line is the first person served.
There are several types of queues in data structures:
Linear Queue: In a simple queue, insertion takes place at the rear and removal occurs at the front. It strictly follows the FIFO (First in First out) rule.
Circular Queue: In a circular queue, the last element points to the first element making a circular link. The main advantage of a circular queue over a simple queue is better memory utilization.
Priority Queue: A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.
Double Ended Queue (Deque): In a double ended queue, insertion and removal of elements can be performed from either from the front or rear.
Here are the common operations performed on various data structures:
Insertion: This operation adds an element to a queue.
Deletion: This operation removes an element from a queue.
Update: This operation modifies the value of an element.
Access: This operation retrieves an element from a queue.
Search: This operation finds a particular element in a queue.
Sort: This operation arranges elements in a specific order.
| Operation | Best Case | Average Case | Worst Case |
|---|---|---|---|
Access (Peek) | O(1) | O(1) | O(1) |
Search | O(N) | O(N) | O(N) |
Insertion (Enqueue) | O(1) | O(1) | O(1) |
Deletion (Pop) | O(1) | O(1) | O(1) |
Update | O(N) | O(N) | O(N) |