Deque in Data Structures

A deque (pronounced “deck”) is a double-ended queue, a type of linear data structure that supports insertion and deletion operations at both the front and rear. Unlike a traditional queue, which restricts operations to rear insertions and front deletions following the FIFO principle, a deque offers greater flexibility by functioning as both a queue and a stack.

In this Data Structure tutorial, you will able to learn about what is deque in data structure, key characteristics of deque, basic operations performed by deque, Implementation of deque with array and linked list and more. Boost your tech career, Solve DSA problems, earn a certificate, and get job-ready for top companies, Join our Free DSA Course now.

What is Deque in Data Structures?

Deque is a linear data structure that supports element insertion and removal from both ends. Unlike a standard queue (FIFO) or stack(LIFO), a Deque offers flexibility by allowing operations on both ends. Deques are widely used in scheduling, caching, sliding window problems, and real-time systems.

Deque Representation

• You can add elements at the front.
• You can remove elements from the front.

• You can add elements at the rear.
• You can remove elements from the rear.

Key Points from the Diagram

• Insert at front → New element will be added before 10.
• Delete at front → 10 will be removed.
• Insert at rear → New element will be added after 70.
• Delete at rear → 70 will be removed.

Characteristics of Deque (Double-Ended Queue)

1. Insertion and Deletion at Both Ends

• A deque allows O(1) time complexity for insertion and deletion at both the front and rear ends.
• This dual-end operation makes it more efficient than a simple queue or stack in scenarios where both ends need to be accessed frequently.

2. Linear Data Structure

• A deque maintains elements in a linear order, just like arrays, stacks, and queues.
• Elements are stored sequentially, but access is restricted to the ends for insertion/deletion operations.

3. Works as Both Queue and Stack

• Queue (FIFO): By inserting at the rear and deleting from the front.
• Stack (LIFO): By inserting and deleting elements at the same end (front or rear).

4. Bounded or Unbounded

• Bounded Deque: It has a fixed size, often implemented using arrays. Once full, no more insertions are allowed until elements are removed.
• Unbounded Deque: It can grow dynamically without a fixed size, often implemented using linked lists.

5. Implementation Options

• Array Implementation: Faster access but requires shifting in some cases. It may cause overflow if full.
• Linked List Implementation: More memory flexible and supports dynamic resizing without shifting elements.

Basic Operations on Deque

1. Insertion at the Front (enqueueFront / pushFront)

• In this operation, a new element is added at the front end of the deque.
• If the deque is implemented using an array and the front pointer is at index 0, then we need to circularly shift or use modulo arithmetic for efficiency.
• In linked list implementation, insertion at the front is straightforward by creating a new node and linking it before the current front node.

Example: 

2. Insertion at the Rear (enqueueRear / pushRear)

• Adds a new element at the rear end.
• In array implementation, this means increasing the rear pointer.
• In linked list implementation, the new node is linked at the end.

Example:

3. Deletion from the Front (dequeueFront / popFront)

• Removes an element from the front end.
• In array-based implementation, it involves moving the front pointer forward.
• In linked list implementation, simply remove the front node and adjust the pointer.

Example:

4. Deletion from the Rear (dequeueRear / popRear)

• Removes an element from the rear end.
• In array-based deque, move the rear pointer backward.
• In linked list implementation, traverse to the second-last node and remove the last.

Example:

5. Peek / Get Front Element

• It returns the element at the front without removing it.
• It is useful to check the first element in the deque.

Example:

6. Peek / Get Rear Element

• It returns the element at the rear without removing it.
• It is useful to check the last element in the deque.

Example:

7. isEmpty()

• It returns true if the deque has no elements.
• In array implementation, it means front == -1.
• In linked list, it means head pointer is NULL.

Example:

8. isFull() (for bounded deque)

• It checks if the deque is full (in case of a fixed-size array).
• It happens when (rear + 1) % size == front.

Example:

Implementation of Deque: Using Array and Linked List

• Using Arrays (Static implementation)
• Using Linked List (Dynamic implementation)

Implementation of Deque using Arrays

• front → tracks the index of the front element.
• rear → tracks the index of the rear element.

Conditions to check:

• Deque Full: (front == 0 && rear == size - 1) || (front == rear + 1)
• Deque Empty: front == -1

#include 
using namespace std;

class Deque {
    int *arr;
    int front, rear, size;

public:
    Deque(int n) {
        size = n;
        arr = new int[size];
        front = -1;
        rear = -1;
    }

    // Check if deque is full
    bool isFull() {
        return (front == 0 && rear == size - 1) || (front == rear + 1);
    }

    // Check if deque is empty
    bool isEmpty() {
        return (front == -1);
    }

    // Insert at front
    void insertFront(int key) {
        if (isFull()) {
            cout << "Deque is full\n";
            return;
        }
        if (front == -1) { // first element
            front = rear = 0;
        } else if (front == 0) {
            front = size - 1; // wrap around
        } else {
            front = front - 1;
        }
        arr[front] = key;
    }

    // Insert at rear
    void insertRear(int key) {
        if (isFull()) {
            cout << "Deque is full\n";
            return;
        }
        if (front == -1) { // first element
            front = rear = 0;
        } else if (rear == size - 1) {
            rear = 0; // wrap around
        } else {
            rear = rear + 1;
        }
        arr[rear] = key;
    }

    // Delete front
    void deleteFront() {
        if (isEmpty()) {
            cout << "Deque is empty\n";
            return;
        }
        if (front == rear) { // single element
            front = rear = -1;
        } else if (front == size - 1) {
            front = 0; // wrap around
        } else {
            front = front + 1;
        }
    }

    // Delete rear
    void deleteRear() {
        if (isEmpty()) {
            cout << "Deque is empty\n";
            return;
        }
        if (front == rear) { // single element
            front = rear = -1;
        } else if (rear == 0) {
            rear = size - 1; // wrap around
        } else {
            rear = rear - 1;
        }
    }

    // Get front
    int getFront() {
        if (isEmpty()) {
            cout << "Deque is empty\n";
            return -1;
        }
        return arr[front];
    }

    // Get rear
    int getRear() {
        if (isEmpty()) {
            cout << "Deque is empty\n";
            return -1;
        }
        return arr[rear];
    }
};

int main() {
    Deque dq(5);

    dq.insertRear(10);
    dq.insertRear(20);
    dq.insertFront(5);
    dq.insertFront(1);

    cout << "Front element: " << dq.getFront() << endl;
    cout << "Rear element: " << dq.getRear() << endl;

    dq.deleteFront();
    dq.deleteRear();

    cout << "Front after deletion: " << dq.getFront() << endl;
    cout << "Rear after deletion: " << dq.getRear() << endl;

    return 0;
}

Explanation:

• Insert Front: Adjust front pointer circularly and add element.
• Insert Rear: Adjust rear pointer circularly and add element.
• Delete Front: Move front forward circularly.
• Delete Rear: Move rear backward circularly.

• Insertion & Deletion → O(1)
• Space Complexity → O(n) (fixed size)

Implementation of Deque using Linked List

In this Implementation, Each node contains: data which stores valuse , prev which is the pointer to the previous node next:pointer to next node

• front → points to first node.
• rear → points to last node.

#include 
using namespace std;
class Node {
public:
    int data;
    Node* prev;
    Node* next;
    Node(int val) {
        data = val;
        prev = NULL;
        next = NULL;
    }
};
class Deque {
    Node* front;
    Node* rear;
public:
    Deque() {
        front = rear = NULL;
    }

    bool isEmpty() {
        return (front == NULL);
    }

    // Insert at front
    void insertFront(int key) {
        Node* newNode = new Node(key);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            newNode->next = front;
            front->prev = newNode;
            front = newNode;
        }
    }
    // Insert at rear
    void insertRear(int key) {
        Node* newNode = new Node(key);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            newNode->prev = rear;
            rear = newNode;
        }
    }

    // Delete front
    void deleteFront() {
        if (isEmpty()) {
            cout << "Deque is empty\n";
            return;
        }
        Node* temp = front;
        if (front == rear) {
            front = rear = NULL;
        } else {
            front = front->next;
            front->prev = NULL;
        }
        delete temp;
    }

    // Delete rear
    void deleteRear() {
        if (isEmpty()) {
            cout << "Deque is empty\n";
            return;
        }
        Node* temp = rear;
        if (front == rear) {
            front = rear = NULL;
        } else {
            rear = rear->prev;
            rear->next = NULL;
        }
        delete temp;
    }
    // Get front
    int getFront() {
        if (isEmpty()) {
            cout << "Deque is empty\n";
            return -1;
        }
        return front->data;
    }
    // Get rear
    int getRear() {
        if (isEmpty()) {
            cout << "Deque is empty\n";
            return -1;
        }
        return rear->data;
    }
};
int main() {
    Deque dq;

    dq.insertRear(10);
    dq.insertRear(20);
    dq.insertFront(5);
    dq.insertFront(1);

    cout << "Front element: " << dq.getFront() << endl;
    cout << "Rear element: " << dq.getRear() << endl;

    dq.deleteFront();
    dq.deleteRear();

    cout << "Front after deletion: " << dq.getFront() << endl;
    cout << "Rear after deletion: " << dq.getRear() << endl;

    return 0;
}

Explanation:

• Insert Front/Rear: Create new node, adjust prev/next links, and update front or rear.
• Delete Front/Rear: Remove node, update pointers accordingly.
• Dynamic Size: No size restriction → grows/shrinks dynamically.

• Insertion & Deletion → O(1)
• Space Complexity → O(n) (dynamic)

Advantages of Deque

1. Versatility

• A Deque can function as both a stack (addFirst/removeFirst) and a queue (addLast/removeFirst).
• This flexibility makes it a universal structure for multiple use cases.

2. Efficient End Operations

• Insertions and deletions at both ends take O(1) time.
• Unlike arrays or lists, no shifting of elements is required.

3. Dynamic Resizing (ArrayDeque)

• When implemented using arrays (ArrayDeque), resizing happens automatically.
• Unlike primitive arrays, it doesn’t need a predefined fixed size.

4. Memory Efficiency

• ArrayDeque uses less memory than LinkedList because it does not store extra node pointers (prev, next).
• Ideal when working with large datasets.

5. Iteration Flexibility

• Deques support bidirectional iteration (forward and backward).
• Useful for algorithms where traversal in both directions is needed.

Disadvantages of Deque

No Random Access

• Unlike arrays, you cannot directly access the middle element in O(1).
• Accessing elements in the middle takes O(n) time.

Not Thread-Safe

• Standard Deque implementations (ArrayDeque, LinkedList) are not synchronized.
• In multithreaded environments, explicit synchronization (e.g., ConcurrentLinkedDeque) is required.

Overhead in LinkedList Implementation

• Each node in a linked list stores extra references (prev and next).
• This increases memory overhead, especially for large data structures.

Resizing Costs (ArrayDeque)

• Although amortized O(1), resizing can cause O(n) time when capacity doubles.
• For very large data, this can impact performance.

Null Restrictions

• ArrayDeque does not allow null elements, as null is used internally to indicate empty slots.

Real-World Applications of Deque

1.Sliding Window Algorithms

• Used in problems like Maximum in Sliding Window.
• Maintains useful elements in a window of size k efficiently.

2. Undo-Redo Functionality

• Editors, IDEs, or browsers use Deques to store history.
• addFirst() for new actions, removeFirst() for undo, and addLast() for redo.

3. Task Scheduling in OS

• Deques are used in operating system job scheduling.
• Some scheduling algorithms require access to both ends of the queue.

4. Palindrome Checking

• Insert characters into a deque, then remove from both ends to compare.
• Efficiently checks if a string is a palindrome.

5. Browser History Navigation

• Forward and backward movement in browsers can be implemented using Deques.
• Move back → removeFirst(), Move forward → removeLast().

Conclusion

In conclusion, the deque is not just another data structure—it is a hybrid structure that combines the strengths of stacks and queues. With its ability to efficiently insert and remove elements from both ends, it becomes a natural fit for real-world applications. Whether implemented using arrays or linked lists, a deque remains a powerful and flexible data structure for solving a wide range of computational problems.

80% of tech hiring tests include DSA – Prepare with our DSA online training course, and earn your certificate.

Take our Datastructures skill challenge to evaluate yourself!

In less than 5 minutes, with our skill challenge, you can identify your knowledge gaps and strengths in a given skill.

GET FREE CHALLENGE