- In this article, we will discuss the double-ended queue or deque. We should first see a brief description of the queue.
What is Deque
- A deque, which stands for “double-ended queue,” is a data structure that allows insertion and deletion at both ends. In other words, elements can be added or removed from the front or the back of the deque.
- This structure provides more flexibility than a regular queue or stack, as it enables operations at both ends, hence the name “double-ended queue.”
The main characteristics and operations of a deque include:
- Insertion at the front and back: Elements can be added at either the front or the back of the deque.
- Deletion from the front and back: Elements can be removed from either the front or the back of the deque.
- Accessing elements at the front and back: It is possible to access elements at both the front and the back without removing them.
- Checking if the deque is empty or full: Operations to determine whether the deque is empty or has reached its maximum capacity.
Deques find applications in scenarios where efficient insertion and deletion are required at both ends of the data structure. They can be implemented using arrays or linked lists, each with its own set of advantages and considerations.
Types of Deque
Deques, or double-ended queues, come in different variations to suit various programming needs and scenarios. Some of the common types of deques include:
- Array-based Deque: This implementation uses an array to store the elements of the deque. It allows for efficient random access to elements but may require resizing the array if it becomes full.
- Linked List-based Deque: Using a linked list structure, this type of deque provides efficient insertion and deletion at both ends, without the need for resizing. It is suitable when the size of the deque is not fixed.
- Circular Deque: Also known as a circular buffer, this type of deque is implemented using a fixed-size array or circular linked list. It efficiently reuses the available space, allowing for continuous insertion and deletion operations without the need for shifting elements.
- Deque with Dynamic Arrays: This type of deque is implemented using dynamic arrays that automatically resize themselves to accommodate more elements. It combines the benefits of array-based deques with dynamic memory allocation.
Operations Performed On Deque
There are the following operations that can be applied on a deque –
- Insertion at front
- Insertion at rear
- Deletion at front
- Deletion at rear
Insertion at the front end
- Insertion at the front end of a deque, or double-ended queue, is a fundamental operation that allows for adding elements at the beginning of the data structure. This operation is particularly useful when the sequence of elements needs to be extended or modified at the front end.
- If the deque is empty, create a new node containing the new element and set it as both the front and rear of the deque.
- If the deque is not empty, create a new node containing the new element.
- Update the next pointer of the new node to point to the current front node.
- Update the front pointer to point to the new node, making it the new front node.
Front -> 5 -> 10 -> 15 -> Rear
After inserting 3 at the front:
Front -> 3 -> 5 -> 10 -> 15 -> Rear
Insertion At the rear end
- Insertion at the rear end of a deque (double-ended queue) is a fundamental operation that allows for adding elements at the end of the data structure. This operation is particularly useful when extending the sequence of elements or when appending elements to the end of the existing data structure.
The steps for inserting an element at the rear end of a deque are typically as follows:
- If the deque is empty, create a new node containing the new element and set it as both the front and the rear of the deque.
- If the deque is not empty, create a new node containing the new element.
- Update the next pointer of the current rear node to point to the new node.
- Update the rear pointer to point to the new node, making it the new rear node.
Before insertion:
Front -> 5 -> 10 -> 15 -> Rear
After inserting 20 at the rear:
Front -> 5 -> 10 -> 15 -> 20 -> Rear
Deletion At The Front End
- Deletion at the front end of a deque (double-ended queue) is a fundamental operation that involves removing an element from the beginning of the data structure. This operation is crucial for maintaining the structure’s integrity and adjusting the elements’ positions as required.
The steps for deleting an element at the front end of a deque are typically as follows:
- Check if the deque is empty. If it is, then no deletion can be performed.
- If the deque is not empty, proceed with the deletion operation.
- Update the front pointer to point to the next element in the deque, effectively removing the current front element.
- If the front element was the only element in the deque, make sure to update the rear pointer accordingly.
Before deletion:
Front -> 5 -> 10 -> 15 -> Rear
After deleting the front element:
Front -> 10 -> 15 -> Rear
Deletion At The Rear End
- Deletion at the rear end of a deque (double-ended queue) involves removing an element from the end of the data structure. This operation is important for maintaining the structure’s integrity and adjusting the elements’ positions as needed.
The steps for deleting an element at the rear end of a deque are generally as follows:
- Check if the deque is empty. If it is, then no deletion can be performed.
- If the deque is not empty, proceed with the deletion operation.
- Update the rear pointer to point to the previous element in the deque, effectively removing the current rear element.
- If the rear element was the only element in the deque, make sure to update the front pointer accordingly.
Before deletion:
Front -> 5 -> 10 -> 15 -> Rear
After deleting the rear element:
Front -> 5 -> 10 -> Rear
