Algorithm
A deque, short for "double-ended queue," is a data structure that allows insertion and deletion of elements from both ends, front and rear. It combines the features of a stack and a queue, providing more flexibility in managing elements. Deques support the following basic operations:
-
Insertion at Front and Rear:
- Elements can be added or inserted at both the front and rear ends of the deque.
-
Deletion from Front and Rear:
- Elements can be removed or deleted from both the front and rear ends of the deque.
-
Access/Peek:
- You can access the elements at the front and rear of the deque without removing them.
The deque structure allows for efficient O(1) time complexity for these basic operations.
Here's a simple illustration of a deque:
mathematica
Front -> | 3 | 7 | 5 | 2 | <- Rear
In this example, elements can be inserted or deleted from both ends of the deque.
Code Examples
#1 Deque Implementation in Python
Code -
Python Programming
from collections import deque
# Creating an empty deque
my_deque = deque()
# Adding elements to the right end of the deque
my_deque.append(1)
my_deque.append(2)
my_deque.append(3)
# Adding elements to the left end of the deque
my_deque.appendleft(0)
# Displaying the deque
print("Deque:", my_deque)
# Removing elements from the right end of the deque
removed_element = my_deque.pop()
print("Removed element from the right end:", removed_element)
# Removing elements from the left end of the deque
removed_element_left = my_deque.popleft()
print("Removed element from the left end:", removed_element_left)
# Displaying the updated deque
print("Updated Deque:", my_deque)
#2 Deque Implementation in Java
Code -
Java Programming
import java.util.Deque;
import java.util.LinkedList;
public class DequeExample {
public static void main(String[] args) {
// Create a deque using LinkedList
Deque < String> deque = new LinkedList<>();
// Adding elements to the front of the deque
deque.addFirst("Element 1");
deque.addFirst("Element 2");
deque.addFirst("Element 3");
// Adding elements to the end of the deque
deque.addLast("Element 4");
deque.addLast("Element 5");
// Displaying the elements of the deque
System.out.println("Deque elements: " + deque);
// Removing elements from the front of the deque
String firstElement = deque.removeFirst();
System.out.println("Removed first element: " + firstElement);
// Removing elements from the end of the deque
String lastElement = deque.removeLast();
System.out.println("Removed last element: " + lastElement);
// Displaying the elements after removal
System.out.println("Updated deque elements: " + deque);
}
}
#3 Deque Implementation in C Program
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Node structure for a doubly linked list
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
// Deque structure
typedef struct Deque {
Node* front;
Node* rear;
} Deque;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to create an empty deque
Deque* createDeque() {
Deque* deque = (Deque*)malloc(sizeof(Deque));
if (deque == NULL) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE);
}
deque->front = NULL;
deque->rear = NULL;
return deque;
}
// Function to check if the deque is empty
int isEmpty(Deque* deque) {
return (deque->front == NULL);
}
// Function to add an element to the front of the deque
void addFront(Deque* deque, int data) {
Node* newNode = createNode(data);
if (isEmpty(deque)) {
deque->front = newNode;
deque->rear = newNode;
} else {
newNode->next = deque->front;
deque->front->prev = newNode;
deque->front = newNode;
}
}
// Function to add an element to the rear of the deque
void addRear(Deque* deque, int data) {
Node* newNode = createNode(data);
if (isEmpty(deque)) {
deque->front = newNode;
deque->rear = newNode;
} else {
newNode->prev = deque->rear;
deque->rear->next = newNode;
deque->rear = newNode;
}
}
// Function to remove an element from the front of the deque
void removeFront(Deque* deque) {
if (isEmpty(deque)) {
printf("Deque is empty\n");
return;
}
Node* temp = deque->front;
deque->front = deque->front->next;
free(temp);
if (deque->front == NULL) {
deque->rear = NULL;
} else {
deque->front->prev = NULL;
}
}
// Function to remove an element from the rear of the deque
void removeRear(Deque* deque) {
if (isEmpty(deque)) {
printf("Deque is empty\n");
return;
}
Node* temp = deque->rear;
deque->rear = deque->rear->prev;
free(temp);
if (deque->rear == NULL) {
deque->front = NULL;
} else {
deque->rear->next = NULL;
}
}
// Function to print the elements of the deque
void printDeque(Deque* deque) {
Node* current = deque->front;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// Function to free the memory allocated for the deque
void freeDeque(Deque* deque) {
while (!isEmpty(deque)) {
removeFront(deque);
}
free(deque);
}
int main() {
Deque* deque = createDeque();
addFront(deque, 1);
addFront(deque, 2);
addRear(deque, 3);
addRear(deque, 4);
printf("Deque: ");
printDeque(deque);
removeFront(deque);
removeRear(deque);
printf("Deque after removals: ");
printDeque(deque);
freeDeque(deque);
return 0;
}
#4 Deque Implementation in C++
Code -
C++ Programming
#include <iostream>
#include <deque>
int main() {
// Declare a deque of integers
std::deque < int> myDeque;
// Insert elements at the back
myDeque.push_back(10);
myDeque.push_back(20);
myDeque.push_back(30);
// Insert elements at the front
myDeque.push_front(5);
myDeque.push_front(15);
// Display elements
std::cout << "Deque elements: ";
for (const auto& element : myDeque) {
std::cout << element << " ";
}
std::cout << "\n";
// Access elements
std::cout << "Front element: " << myDeque.front() << "\n";
std::cout << "Back element: " << myDeque.back() << "\n";
// Remove elements from the front
myDeque.pop_front();
// Remove elements from the back
myDeque.pop_back();
// Display elements after removal
std::cout << "Deque elements after removal: ";
for (const auto& element : myDeque) {
std::cout << element << " ";
}
std::cout << "\n";
return 0;
}
Demonstration
Deque Data Structure-DevsEnv