Chapter 11: Deques (Double-Ended Queues)
Welcome to Chapter 11! In this chapter, we’ll explore Deques, or Double-Ended Queues, an interesting and versatile data structure that extends the concept of a standard queue by allowing insertion and deletion at both ends.
This concept will help you understand more advanced applications of queues and solve real-life problems like managing text editors, undo operations, or simulations.
Let’s begin!
What is a Deque?
A Deque (pronounced “deck”) stands for Double-Ended Queue, and it is a generalized form of the standard queue. Unlike a regular queue, where insertion is done at the back and deletion is done at the front, a deque allows insertion and deletion from both ends of the structure.
In simple terms:
- You can add an element at either the front or the back.
- You can remove an element from either the front or the back.
This makes the deque a very flexible data structure. Imagine you’re standing in a line (queue) but now, you have the option to add someone to the front of the line, or let them sneak in at the back. That’s how a deque works!
Types of Deques
Deques can be classified into two types:
-
Input-Restricted Deque: In this type of deque, insertion is restricted to one end (say, the rear), but deletion can occur at both ends.
-
Output-Restricted Deque: In this type, deletion is restricted to one end (say, the front), but insertion can happen at both ends.
Both types allow different levels of control depending on your use case.
Applications of Deques
Before we get into the operations, let’s explore some real-world applications of deques:
-
Undo/Redo Operations: In text editors or drawing tools, deques can be used to manage undo and redo functionality. You can easily move forward and backward in the history of actions.
-
Palindrome Checking: Deques are perfect for checking palindromes (words or phrases that read the same forward and backward) because they allow access from both ends.
-
Sliding Window Problems: In algorithms, deques are often used to maintain a sliding window of data, useful in problems like finding the maximum or minimum of all subarrays of a given size.
-
Task Scheduling: In simulations or real-time systems like the ones developed by Emancipation Edutech Private Limited, deques can manage tasks with both high and low priorities, offering flexibility in choosing which task to execute next.
You can read more about these applications and other use cases for free on digilearn.cloud!
Basic Operations of Deques
Now, let’s break down the core operations that can be performed on a deque:
- Insertion at Front: Insert an element at the front of the deque.
- Insertion at Rear: Insert an element at the rear of the deque.
- Deletion from Front: Remove an element from the front of the deque.
- Deletion from Rear: Remove an element from the rear of the deque.
- Get Front: Retrieve the front element without removing it.
- Get Rear: Retrieve the rear element without removing it.
- Check if Empty: Check if the deque is empty.
- Check if Full: Check if the deque is full (in a limited-size implementation).
These operations make deques highly versatile, with various possibilities for manipulating the data structure.
Deque Representation and Implementation
Let’s implement a deque using an array in C to better understand how it works.
Define the Deque Structure
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
struct Deque {
int arr[MAX]; // Array to store elements
int front; // Points to the front end
int rear; // Points to the rear end
int size; // Current number of elements
};
arr: This array will store our elements.front: This pointer will indicate the front of the deque.rear: This pointer will indicate the rear of the deque.size: This will track the number of elements in the deque.
Initialize the Deque
void initialize(struct Deque* dq) {
dq->front = -1; // Initially, front is -1 (empty state)
dq->rear = -1; // Initially, rear is -1 (empty state)
dq->size = 0; // No elements in the deque
}
Insertion at Front
void insertFront(struct Deque* dq, int value) {
if (dq->size == MAX) { // Check if deque is full
printf("Deque Overflow\n");
return;
}
if (dq->front == -1) { // First element insertion
dq->front = 0;
dq->rear = 0;
} else if (dq->front == 0) { // Circular condition
dq->front = MAX - 1;
} else {
dq->front--;
}
dq->arr[dq->front] = value;
dq->size++;
}
Insertion at Rear
void insertRear(struct Deque* dq, int value) {
if (dq->size == MAX) { // Check if deque is full
printf("Deque Overflow\n");
return;
}
if (dq->rear == -1) { // First element insertion
dq->rear = 0;
dq->front = 0;
} else if (dq->rear == MAX - 1) { // Circular condition
dq->rear = 0;
} else {
dq->rear++;
}
dq->arr[dq->rear] = value;
dq->size++;
}
Deletion from Front
void deleteFront(struct Deque* dq) {
if (dq->size == 0) { // Check if deque is empty
printf("Deque Underflow\n");
return;
}
if (dq->front == dq->rear) { // Only one element in deque
dq->front = -1;
dq->rear = -1;
} else if (dq->front == MAX - 1) { // Circular condition
dq->front = 0;
} else {
dq->front++;
}
dq->size--;
}
Deletion from Rear
void deleteRear(struct Deque* dq) {
if (dq->size == 0) { // Check if deque is empty
printf("Deque Underflow\n");
return;
}
if (dq->front == dq->rear) { // Only one element in deque
dq->front = -1;
dq->rear = -1;
} else if (dq->rear == 0) { // Circular condition
dq->rear = MAX - 1;
} else {
dq->rear--;
}
dq->size--;
}
Checking if the Deque is Empty or Full
int isEmpty(struct Deque* dq) {
return dq->size == 0;
}
int isFull(struct Deque* dq) {
return dq->size == MAX;
}
Real-World Example
Imagine you’re developing a browser. The deque can be used to implement forward and backward navigation:
- You can insert URLs into the deque as the user browses different websites.
- When the user clicks the "back" button, you remove the URL from the rear (current page) and go back to the front (previous page).
- The user can also move forward by using the deque from both ends.
Deques make implementing such navigation systems efficient and simple!
Deque Using Linked Lists
While implementing deques with arrays works, using linked lists offers more flexibility since deques can dynamically grow and shrink without the constraint of a fixed size.
Node Structure
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
Each node in a deque will contain data and pointers to both the next and previous nodes, making insertion and deletion at both ends efficient.
Deque Structure
struct DequeLL {
struct Node* front;
struct Node* rear;
};
Advantages of Deques
- Flexible: Elements can be added and removed from both ends, making them more versatile than regular queues.
- Efficient for Both Ends: Deques allow efficient insertion and deletion from both the front and rear.
- Useful in Sliding Window Algorithms: Deques are ideal for managing data in sliding windows and double-ended processes.
Disadvantages of Deques
- Complexity: Deques add some complexity compared to regular queues, especially when dealing with circular conditions.
- Memory Consumption: If implemented with arrays, memory usage might be inefficient, as arrays can take up more space than linked lists for dynamic usage.
Conclusion
Deques are a powerful and versatile data structure that extend the capabilities of regular queues by allowing double-ended operations. Whether you’re managing navigation in a browser, implementing undo operations, or solving complex algorithmic problems, deques provide the flexibility and
efficiency required.
In the next chapter, we’ll explore Priority Queues, which are essential when the order of elements is not just about "first-in, first-out" but also about their priority.
Stay tuned and keep practicing!
