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:

  1. Insertion at Front and Rear:

    • Elements can be added or inserted at both the front and rear ends of the deque.
  2. Deletion from Front and Rear:

    • Elements can be removed or deleted from both the front and rear ends of the deque.
  3. 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)
Copy The Code & Try With Live Editor

#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);
    }
}
Copy The Code & Try With Live Editor

#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;
}
Copy The Code & Try With Live Editor

#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;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Deque Data Structure-DevsEnv