Queues:
- A queue is a linear data structure in which elements are inserted from one end called the rear end and deleted from another end called the front end.
- It follows FIFO (First In First Out) technique.
- Insertion in the queue is called enqueue and deletion in the queue is called dequeue.
- Queues can be implemented in two ways: Array-based queues and list-based queues.
Array-based queues and List-based queues:
Array-based queues and List-based queues are two common implementations of the Queue data structure in computer science.
Array-based queues use an array as the underlying data structure to store the elements of the queue. In this implementation, elements are added to the rear of the array and removed from the front of the array. This operation is known as enqueue and dequeue, respectively. One advantage of array-based queues is that they have constant-time access to any element in the queue. However, the size of the array needs to be fixed at the time of creation, and if the queue becomes full, it needs to be resized, which can be an expensive operation.
List-based queues, on the other hand, use a linked list as the underlying data structure. Each node in the linked list represents an element in the queue, and the first node represents the front of the queue, while the last node represents the rear of the queue. Elements are added to the rear of the list and removed from the front of the list. List-based queues do not have a fixed size and can grow dynamically, but accessing elements in the middle of the list can be slower than in array-based queues.
Both array-based and list-based queues have their advantages and disadvantages, and their choice depends on the specific needs of the application.
In array-based queues are implemented using the arrays. In list-based queues are implemented using a linked list.
Array-Based vs List-Based Queues:
| Sno. |
Array-Based Queues |
List-Based Queues |
|---|---|---|
| 1. | The size of the queue should be known in advance. | It’s not necessary to know the size of the queue in advance. |
| 2. | Insertion at the end is easier but insertion at the beginning is difficult. | Insertion at both end and beginning is easy. |
| 3. | Elements can be accessed randomly. | Elements can be accessed sequentially only. |
| 4. | Resizing array-based queues is complex. | Resizing list-based queues is simple. |
| 5. | Requires less memory. | Requires more memory. |
| 6. | It is faster compared to list-based queues. | It is slower compared to array-based queues. |
| Property | Array-Based Queues | List-Based Queues |
| Underlying Data Structure | Array | Linked List |
| Access Time | Constant Time | O(n) Time |
| Memory Management | Fixed Size, May Require Resizing | Dynamic Size |
| Insertion/Deletion | Rear: O(1) Time, Front: O(n) Time | Rear: O(1) Time, Front: O(1) Time |
| Implementation | Easier to Implement | More Complex to Implement |
| Advantages | Constant Access Time, Efficient for Small Queues | Dynamic Size, Efficient for Large Queues |
| Disadvantages | Fixed Size, May Require Resizing, Inefficient for Large Queues | Slower Access Time, More Complex to Implement |
Advantages of array-based queues:
- It is faster compared to a list-based queue.
- Elements can be accessed randomly.
- It requires less memory.
Disadvantages of array-based queues:
- The size of the queue should be known in advance.
- Resizing array-based queues is complex.
- Insertion at the beginning is difficult.
Advantages of list-based queues:
- Insertion at both end and beginning is easy.
- It’s not necessary to know the size of the queue in advance.
- Resizing is simple.
Disadvantages of list-based queues:
- It requires more memory.
- It is slower as compared to array-based queues.
- Elements can be accessed sequentially only.
Conditions when to use each of these:
Array-based queues are used when we have to access elements randomly and with less memory. List-based queues are used when there are a greater number of enqueue and dequeue operations and the size of the queue is not known in advance.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
