A deque (double-ended queue) is a versatile data structure that allows insertion and deletion of elements from both ends. Deques are commonly used in scenarios where elements need to be added or removed from both ends efficiently. This article will guide you through implementing a deque in C++ using three different methods, providing multiple solutions and example outputs for each approach. By the end of this article, you’ll have a strong understanding of how deques work and how to implement them in various ways.
Prerequisites
Before diving into the implementation of a deque, you should have:
- Basic understanding of the C++ programming language.
- Familiarity with standard libraries in C++.
- Knowledge of data structures, especially queues and linked lists.
Introduction
In this article, we will write a C++ Program to Implement a Deque. We will cover three different methods: using arrays, using linked lists, and using the STL deque container. Each method will be explained with a code example and output to illustrate the concept. Let’s get started on this journey to mastering deques in C++.
1. Method 1: Implementing Deque Using Arrays
1.1 Explanation
A deque can be implemented using a circular array. The circular array approach involves maintaining two indices, front and rear, to keep track of the positions where elements can be inserted or removed.
1.2 Code Implementation
#include <iostream>
using namespace std;
class Deque {
int* arr;
int front, rear, size, capacity;
public:
Deque(int capacity) {
this->capacity = capacity;
arr = new int[capacity];
front = -1;
rear = -1;
size = 0;
}
bool isFull() {
return size == capacity;
}
bool isEmpty() {
return size == 0;
}
void insertFront(int element) {
if (isFull()) {
cout << "Deque is full\n";
return;
}
if (isEmpty()) {
front = 0;
rear = 0;
} else {
front = (front - 1 + capacity) % capacity;
}
arr[front] = element;
size++;
}
void insertRear(int element) {
if (isFull()) {
cout << "Deque is full\n";
return;
}
if (isEmpty()) {
front = 0;
rear = 0;
} else {
rear = (rear + 1) % capacity;
}
arr[rear] = element;
size++;
}
void deleteFront() {
if (isEmpty()) {
cout << "Deque is empty\n";
return;
}
front = (front + 1) % capacity;
size--;
}
void deleteRear() {
if (isEmpty()) {
cout << "Deque is empty\n";
return;
}
rear = (rear - 1 + capacity) % capacity;
size--;
}
int getFront() {
if (isEmpty()) {
cout << "Deque is empty\n";
return -1;
}
return arr[front];
}
int getRear() {
if (isEmpty()) {
cout << "Deque is empty\n";
return -1;
}
return arr[rear];
}
};
int main() {
Deque dq(5);
dq.insertRear(5);
dq.insertRear(10);
dq.insertFront(15);
dq.insertFront(20);
cout << "Front element: " << dq.getFront() << endl;
cout << "Rear element: " << dq.getRear() << endl;
dq.deleteFront();
cout << "After deleting front element, front: " << dq.getFront() << endl;
dq.deleteRear();
cout << "After deleting rear element, rear: " << dq.getRear() << endl;
return 0;
}
1.3 Output
Front element: 20
Rear element: 10
After deleting front element, front: 15
After deleting rear element, rear: 5
2. Method 2: Implementing Deque Using Linked List
2.1 Explanation
A deque can also be implemented using a doubly linked list. In this approach, each node contains pointers to the next and previous nodes, allowing insertion and deletion from both ends.
2.2 Code Implementation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
class Deque {
Node* front;
Node* rear;
int size;
public:
Deque() {
front = nullptr;
rear = nullptr;
size = 0;
}
bool isEmpty() {
return size == 0;
}
void insertFront(int element) {
Node* newNode = new Node();
newNode->data = element;
newNode->next = front;
newNode->prev = nullptr;
if (isEmpty()) {
rear = newNode;
} else {
front->prev = newNode;
}
front = newNode;
size++;
}
void insertRear(int element) {
Node* newNode = new Node();
newNode->data = element;
newNode->prev = rear;
newNode->next = nullptr;
if (isEmpty()) {
front = newNode;
} else {
rear->next = newNode;
}
rear = newNode;
size++;
}
void deleteFront() {
if (isEmpty()) {
cout << "Deque is empty\n";
return;
}
Node* temp = front;
front = front->next;
if (front != nullptr) {
front->prev = nullptr;
} else {
rear = nullptr;
}
delete temp;
size--;
}
void deleteRear() {
if (isEmpty()) {
cout << "Deque is empty\n";
return;
}
Node* temp = rear;
rear = rear->prev;
if (rear != nullptr) {
rear->next = nullptr;
} else {
front = nullptr;
}
delete temp;
size--;
}
int getFront() {
if (isEmpty()) {
cout << "Deque is empty\n";
return -1;
}
return front->data;
}
int getRear() {
if (isEmpty()) {
cout << "Deque is empty\n";
return -1;
}
return rear->data;
}
};
int main() {
Deque dq;
dq.insertRear(5);
dq.insertRear(10);
dq.insertFront(15);
dq.insertFront(20);
cout << "Front element: " << dq.getFront() << endl;
cout << "Rear element: " << dq.getRear() << endl;
dq.deleteFront();
cout << "After deleting front element, front: " << dq.getFront() << endl;
dq.deleteRear();
cout << "After deleting rear element, rear: " << dq.getRear() << endl;
return 0;
}
2.3 Output
Front element: 20
Rear element: 10
After deleting front element, front: 15
After deleting rear element, rear: 5
3. Method 3: Using STL Deque
3.1 Explanation
The STL provides a ready-made deque container that efficiently supports insertion and deletion from both ends. This method leverages the power of STL for simplicity and performance.
3.2 Code Implementation
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq;
dq.push_back(5);
dq.push_back(10);
dq.push_front(15);
dq.push_front(20);
cout << "Front element: " << dq.front() << endl;
cout << "Rear element: " << dq.back() << endl;
dq.pop_front();
cout << "After deleting front element, front: " << dq.front() << endl;
dq.pop_back();
cout << "After deleting rear element, rear: " << dq.back() << endl;
return 0;
}
3.3 Output
Front element: 20
Rear element: 10
After deleting front element, front: 15
After deleting rear element, rear: 5
Conclusion
In this article, we explored different methods to implement a deque in C++. We started with the array-based approach, moved on to the linked list implementation, and finally utilized the STL deque container. Each method has its own advantages and trade-offs, from simplicity and direct control over memory to the convenience and efficiency provided by the STL. Understanding these techniques will enhance your ability to choose the best method for your specific needs and improve your overall programming skills. Deques are essential in various applications, and mastering their implementation is crucial for any programmer.