Double Ended Queue(Deque) – DSA

What is Deque(Double Ended Queue)?

A deque is a dynamic data structure that allows insertions and deletions at both its front (head) and rear (tail) ends. This bidirectional flexibility sets it apart from traditional queues and stacks.

Double-Ended Queue:

It is also known as a head-tail linked list because the elements can be inserted and deleted from both ends. However, no elements can be added or deleted from the middle of the queue.

There are two variants of a double-ended queue.

1. Input restricted deque: Form of deque insertions will be done at the rear end while the deletions can be performed at the front or rear end.
2. Output restricted deque: In this form, insertions can be done at either the rear or front end while the deletions can be performed only at the front end.

Why Use an Array for Implementation?

Arrays, with their contiguous memory allocation, offer a straightforward approach to implementing deques. 

We can efficiently manage the front and rear positions using array indices.

Implementation Steps:

1. Initialization:
   • Declare an array of a fixed size to represent the deque.
   • Initialize two pointers, front, and rear, both typically to -1. These will track the front and rear elements of the deque.
2. Insertion Operations:
   • Insert at Front:
     • Check if the deque is full. If so, indicate overflow and exit.
     • If the deque is empty (front == -1), set both front and rear to 0.
     • Otherwise, if the front is at the beginning of the array (front == 0), move the front to the last index circularly: front = array_size – 1.
     • Otherwise, simply decrement front: front–.
     • Insert the new element at the front index.
   • Insert at Rear:
     • Check if the deque is full. If so, indicate overflow and exit.
     • If the deque is empty (front == -1), set both front and rear to 0.
     • Otherwise, move the rear one position forward circularly: rear = (rear + 1) % array_size.
     • Insert the new element at the rear index.
3. Deletion Operations:
   • Delete from Front:
     • Check if the deque is empty. If so, indicate underflow and exit.
     • Retrieve the element at the front index.
     • If only one element was present (front == rear), reset both front and rear to -1.
     • Otherwise, if the front is at the last index (front == array_size – 1), move the front to the beginning circularly: front = 0.
     • Otherwise, simply increment front: front++.
     • Return the retrieved element.
   • Delete from Rear:
     • Check if the deque is empty. If so, indicate underflow and exit.
     • Retrieve the element at the rear index.
     • If only one element was present (front == rear), reset both front and rear to -1.
     • Otherwise, if the rear is at the beginning (rear == 0), move the rear to the last index circularly: rear = array_size – 1.
     • Otherwise, simply decrement rear: rear–.
     • Return the retrieved element.
4. Checking if the Deque is Full:
   • The deque is full if the next position after the rear (considering circular wrapping)  equals the front: (rear + 1) % array_size == front.
5. Checking if the Deque is Empty:
   • The deque is empty if the front is still -1.

Program Implementation of Deque Using Array

class Deque:
    def __init__(self, size):
        self.size = size
        self.deque = [None] * size  # Initialize deque as an array with None values
        self.front = -1
        self.rear = -1
    def is_empty(self):
        # Deque is empty if front is still -1
        return self.front == -1
    def is_full(self):
        # Deque is full if the next position after rear (circularly) is front
        return ((self.rear + 1) % self.size == self.front)
    def insert_front(self, value):
        if self.is_full():
            print("Deque Overflow!")
            return
        if self.is_empty():
            # If deque is empty, initialize both front and rear to 0
            self.front = self.rear = 0
        elif self.front == 0:
            # If front is at the beginning, move it to the last index circularly
            self.front = self.size - 1
        else:
            # Otherwise, simply decrement front
            self.front -= 1
        self.deque[self.front] = value
    def insert_rear(self, value):
        if self.is_full():
            print("Deque Overflow!")
            return
        if self.is_empty():
            # If deque is empty, initialize both front and rear to 0
            self.front = self.rear = 0
        else:
            # Otherwise, move rear one position forward circularly
            self.rear = (self.rear + 1) % self.size
        self.deque[self.rear] = value
    def delete_front(self):
        if self.is_empty():
            print("Deque Underflow!")
            return None
        value = self.deque[self.front]
        if self.front == self.rear:
            # If only one element was present, reset both front and rear
            self.front = self.rear = -1
        elif self.front == self.size - 1:
            # If front is at the last index, move it to the beginning circularly
            self.front = 0
        else:
            # Otherwise, simply increment front
            self.front += 1
        return value
    def delete_rear(self):
        if self.is_empty():
            print("Deque Underflow!")
            return None
        value = self.deque[self.rear]
        if self.front == self.rear:
            # If only one element was present, reset both front and rear
            self.front = self.rear = -1
        elif self.rear == 0:
            # If rear is at the beginning, move it to the last index circularly
            self.rear = self.size - 1
        else:
            # Otherwise, simply decrement rear
            self.rear -= 1
        return value
    def display(self):
        if self.is_empty():
            print("Deque is empty.")
            return
        print("Deque elements are:", end=" ")
        if self.rear >= self.front:
            for i in range(self.front, self.rear + 1):
                print(self.deque[i], end=" ")
        else:
            for i in range(self.front, self.size):
                print(self.deque[i], end=" ")
            for i in range(0, self.rear + 1):
                print(self.deque[i], end=" ")
        print()
# Example usage:
my_deque = Deque(5)
my_deque.insert_rear(1)
my_deque.insert_rear(2)
my_deque.insert_front(3)
my_deque.insert_front(4)
my_deque.display()  # Output: Deque elements are: 4 3 1 2 
print("Deleted from front:", my_deque.delete_front())  # Output: Deleted from front: 4
my_deque.display()  # Output: Deque elements are: 3 1 2 
my_deque.insert_rear(5)
my_deque.display()  # Output: Deque elements are: 3 1 2 5
print("Deleted from rear:", my_deque.delete_rear())  # Output: Deleted from rear: 5
my_deque.display()  # Output: Deque elements are: 3 1 2 

#include <iostream>
using namespace std;
class Deque {
private:
    int size;
    int *arr; // Array to store deque elements
    int front;
    int rear;
public:
    Deque(int size) {
        this->size = size;
        arr = new int[size];
        front = -1;
        rear = -1;
    }
    bool isEmpty() {
        // Deque is empty if front is still -1
        return (front == -1);
    }
    bool isFull() {
        // Deque is full if the next position after rear (circularly) is front
        return ((rear + 1) % size == front);
    }
    void insertFront(int value) {
        if (isFull()) {
            cout << "Deque Overflow!" << endl;
            return;
        }
        if (isEmpty()) {
            // If deque is empty, initialize both front and rear to 0
            front = rear = 0;
        } else if (front == 0) {
            // If front is at the beginning, move it to the last index circularly
            front = size - 1;
        } else {
            // Otherwise, simply decrement front
            front--;
        }
        arr[front] = value;
    }
    void insertRear(int value) {
        if (isFull()) {
            cout << "Deque Overflow!" << endl;
            return;
        }
        if (isEmpty()) {
            // If deque is empty, initialize both front and rear to 0
            front = rear = 0;
        } else {
            // Otherwise, move rear one position forward circularly
            rear = (rear + 1) % size;
        }
        arr[rear] = value;
    }
    int deleteFront() {
        if (isEmpty()) {
            cout << "Deque Underflow!" << endl;
            return -1; // Return -1 to indicate underflow
        }
        int value = arr[front];
        if (front == rear) {
            // If only one element was present, reset both front and rear
            front = rear = -1;
        } else if (front == size - 1) {
            // If front is at the last index, move it to the beginning circularly
            front = 0;
        } else {
            // Otherwise, simply increment front
            front++;
        }
        return value;
    }
    int deleteRear() {
        if (isEmpty()) {
            cout << "Deque Underflow!" << endl;
            return -1; // Return -1 to indicate underflow
        }
        int value = arr[rear];
        if (front == rear) {
            // If only one element was present, reset both front and rear
            front = rear = -1;
        } else if (rear == 0) {
            // If rear is at the beginning, move it to the last index circularly
            rear = size - 1;
        } else {
            // Otherwise, simply decrement rear
            rear--;
        }
        return value;
    }
    void display() {
        if (isEmpty()) {
            cout << "Deque is empty." << endl;
            return;
        }
        cout << "Deque elements are: ";
        if (rear >= front) {
            for (int i = front; i <= rear; i++) {
                cout << arr[i] << " ";
            }
        } else {
            for (int i = front; i < size; i++) {
                cout << arr[i] << " ";
            }
            for (int i = 0; i <= rear; i++) {
                cout << arr[i] << " ";
            }
        }
        cout << endl;
    }
};
int main() {
    Deque dq(5);
    dq.insertRear(1);
    dq.insertRear(2);
    dq.insertFront(3);
    dq.insertFront(4);
    dq.display(); // Output: 4 3 1 2
    cout << "Deleted from front: " << dq.deleteFront() << endl; // Output: 4
    dq.display(); // Output: 3 1 2 
    dq.insertRear(5);
    dq.display(); // Output: 3 1 2 5 
    cout << "Deleted from rear: " << dq.deleteRear() << endl; // Output: 5
    dq.display(); // Output: 3 1 2 
    return 0;
}

class Deque {
    private int[] arr; // Array to store deque elements
    private int front;
    private int rear;
    private int size;
    public Deque(int size) {
        this.size = size;
        arr = new int[size];
        front = -1;
        rear = -1;
    }
    public boolean isEmpty() {
        // Deque is empty if front is still -1
        return (front == -1);
    }
    public boolean isFull() {
        // Deque is full if the next position after rear (circularly) is front
        return ((rear + 1) % size == front);
    }
    public void insertFront(int value) {
        if (isFull()) {
            System.out.println("Deque Overflow!");
            return;
        }
        if (isEmpty()) {
            // If deque is empty, initialize both front and rear to 0
            front = rear = 0;
        } else if (front == 0) {
            // If front is at the beginning, move it to the last index circularly
            front = size - 1;
        } else {
            // Otherwise, simply decrement front
            front--;
        }
        arr[front] = value;
    }
    public void insertRear(int value) {
        if (isFull()) {
            System.out.println("Deque Overflow!");
            return;
        }
        if (isEmpty()) {
            // If deque is empty, initialize both front and rear to 0
            front = rear = 0;
        } else {
            // Otherwise, move rear one position forward circularly
            rear = (rear + 1) % size;
        }
        arr[rear] = value;
    }
    public int deleteFront() {
        if (isEmpty()) {
            System.out.println("Deque Underflow!");
            return -1; // Return -1 to indicate underflow
        }
        int value = arr[front];
        if (front == rear) {
            // If only one element was present, reset both front and rear
            front = rear = -1;
        } else if (front == size - 1) {
            // If front is at the last index, move it to the beginning circularly
            front = 0;
        } else {
            // Otherwise, simply increment front
            front++;
        }
        return value;
    }
    public int deleteRear() {
        if (isEmpty()) {
            System.out.println("Deque Underflow!");
            return -1; // Return -1 to indicate underflow
        }
        int value = arr[rear];
        if (front == rear) {
            // If only one element was present, reset both front and rear
            front = rear = -1;
        } else if (rear == 0) {
            // If rear is at the beginning, move it to the last index circularly
            rear = size - 1;
        } else {
            // Otherwise, simply decrement rear
            rear--;
        }
        return value;
    }
    public void display() {
        if (isEmpty()) {
            System.out.println("Deque is empty.");
            return;
        }
        System.out.print("Deque elements are: ");
        if (rear >= front) {
            for (int i = front; i <= rear; i++) {
                System.out.print(arr[i] + " ");
            }
        } else {
            for (int i = front; i < size; i++) {
                System.out.print(arr[i] + " ");
            }
            for (int i = 0; i <= rear; i++) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Deque dq = new Deque(5);
        dq.insertRear(1);
        dq.insertRear(2);
        dq.insertFront(3);
        dq.insertFront(4);
        dq.display(); // Output: 4 3 1 2
        System.out.println("Deleted from front: " + dq.deleteFront()); // Output: 4
        dq.display(); // Output: 3 1 2 
        dq.insertRear(5);
        dq.display(); // Output: 3 1 2 5 
        System.out.println("Deleted from rear: " + dq.deleteRear()); // Output: 5
        dq.display(); // Output: 3 1 2 
    }
}

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5 // Define the maximum size of the deque
// Structure to represent a deque
typedef struct {
    int arr[SIZE]; // Array to store deque elements
    int front;
    int rear;
    int size;
} Deque;
// Function to initialize the deque
void initializeDeque(Deque *dq) {
    dq->size = SIZE;
    dq->front = -1;
    dq->rear = -1;
}
// Function to check if the deque is empty
int isEmpty(Deque *dq) {
    return (dq->front == -1); 
}
// Function to check if the deque is full
int isFull(Deque *dq) {
    return ((dq->rear + 1) % dq->size == dq->front);
}
// Function to insert an element at the front of the deque
void insertFront(Deque *dq, int value) {
    if (isFull(dq)) {
        printf("Deque Overflow!\n");
        return;
    }
    if (isEmpty(dq)) {
        dq->front = dq->rear = 0;
    } else if (dq->front == 0) {
        dq->front = dq->size - 1;
    } else {
        dq->front--;
    }
    dq->arr[dq->front] = value;
}
// Function to insert an element at the rear of the deque
void insertRear(Deque *dq, int value) {
    if (isFull(dq)) {
        printf("Deque Overflow!\n");
        return;
    }
    if (isEmpty(dq)) {
        dq->front = dq->rear = 0;
    } else {
        dq->rear = (dq->rear + 1) % dq->size; 
    }
    dq->arr[dq->rear] = value;
}
// Function to delete an element from the front of the deque
int deleteFront(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque Underflow!\n");
        return -1; 
    }
    int value = dq->arr[dq->front]; 
    if (dq->front == dq->rear) { 
        dq->front = dq->rear = -1; 
    } else if (dq->front == dq->size - 1) { 
        dq->front = 0; 
    } else {
        dq->front++; 
    }
    return value; 
}
// Function to delete an element from the rear of the deque
int deleteRear(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque Underflow!\n");
        return -1; 
    }
    int value = dq->arr[dq->rear];
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else if (dq->rear == 0) {
        dq->rear = dq->size - 1;
    } else {
        dq->rear--;
    }
    return value;
}
// Function to display the elements of the deque
void display(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty.\n");
        return;
    }
    printf("Deque elements are: ");
    if (dq->rear >= dq->front) {
        for (int i = dq->front; i <= dq->rear; i++) {
            printf("%d ", dq->arr[i]); 
        }
    } else {
        for (int i = dq->front; i < dq->size; i++) {
            printf("%d ", dq->arr[i]); 
        }
        for (int i = 0; i <= dq->rear; i++) {
            printf("%d ", dq->arr[i]); 
        }
    }
    printf("\n");
}
int main() {
    Deque dq;
    initializeDeque(&dq);
    insertRear(&dq, 1); 
    insertRear(&dq, 2); 
    insertFront(&dq, 3); 
    insertFront(&dq, 4); 
    display(&dq);  // Output: 4 3 1 2 
    printf("Deleted from front: %d\n", deleteFront(&dq)); // Output: 4
    display(&dq);  // Output: 3 1 2
    insertRear(&dq, 5); 
    display(&dq);  // Output: 3 1 2 5
    printf("Deleted from rear: %d\n", deleteRear(&dq));  // Output: 5
    display(&dq);  // Output: 3 1 2
    return 0;
}

Output:

Deque elements are: 4 3 1 2 
Deleted from front: 4
Deque elements are: 3 1 2 
Deque elements are: 3 1 2 5 
Deleted from rear: 5
Deque elements are: 3 1 2

Complexity Analysis of Deque:

Benefits of Deques:

• Enhanced Flexibility: Supports insertion and deletion from both ends.
• Efficient for Certain Operations: Provides constant-time complexity (O(1)) for adding or removing elements from the front or rear.

Applications:

• Browser History: Maintaining a list of recently visited web pages.
• Undo/Redo Functionality: Storing a sequence of user actions.
• Job Scheduling: Implementing specialized job queues with priority-based processing.

Related FAQs: