Introduction to Deque

A Deque (Double-Ended Queue) is a linear data structure that allows insertion and deletion of elements from both ends. Unlike a stack or a queue, where operations are restricted to one end, a deque provides flexibility to add or remove elements at the front as well as the rear.

• Deque can act as both Stack and Queue
• It is useful in many problems where we need to have a subset of all operations also like insert/remove at front and insert/remove at the end.
• It is typically implemented either using a doubly linked list or circular array.

Common Operations of Deque:

In order to make manipulations in a deque, there are certain operations provided to us.

1. insertFront(x) → Insert an element at the front end.
2. insertRear(x) → Insert an element at the rear end.
3. deleteFront() → Delete an element from the front end.
4. deleteRear() → Delete an element from the rear end.
5. getFront() → Retrieve (but don’t remove) the front element.
6. getRear() → Retrieve (but don’t remove) the rear element.
7. isEmpty() → Check if the deque is empty.
8. size() → Return the number of elements currently in the deque.

Code Example

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> dq;

    dq.push_back(10);
    dq.push_back(20);
    dq.push_front(30);

    // Print deque elements
    for (int x : dq) cout << x << " ";
    cout << endl;

    // Pop from front and back
    dq.pop_front();
    dq.pop_back();

    // Print deque elements after pop
    for (int x : dq) cout << x << " ";
    
    return 0;
}

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> dq = new ArrayDeque<>();

        dq.addLast(10);
        dq.addLast(20);
        dq.addFirst(30);

        // Print deque elements
        for (int x : dq) System.out.print(x + " ");
        System.out.println();

        // Pop from front and back
        dq.removeFirst();
        dq.removeLast();

        // Print deque elements after pop
        for (int x : dq) System.out.print(x + " ");
    }
}

from collections import deque

dq = deque()

dq.append(10)
dq.append(20)
dq.appendleft(30)

# Print deque elements
print(' '.join(map(str, dq)))

# Pop from front and back
dq.popleft()
dq.pop()

# Print deque elements after pop
print(' '.join(map(str, dq)))

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        Deque<int> dq = new Deque<int>();

        dq.AddLast(10);
        dq.AddLast(20);
        dq.AddFirst(30);

        // Print deque elements
        foreach (int x in dq) Console.Write(x + " ");
        Console.WriteLine();

        // Pop from front and back
        dq.RemoveFirst();
        dq.RemoveLast();

        // Print deque elements after pop
        foreach (int x in dq) Console.Write(x + " ");
    }
}

public class Deque<T> {
    private LinkedList<T> list = new LinkedList<T>();

    public void AddFirst(T value) { list.AddFirst(value); }
    public void AddLast(T value) { list.AddLast(value); }
    public void RemoveFirst() { list.RemoveFirst(); }
    public void RemoveLast() { list.RemoveLast(); }
    public IEnumerator<T> GetEnumerator() { return list.GetEnumerator(); }
}

30 10 20 
10 

Implementation of Deque:

Deque can be implemented in Different Ways :-

• Implementation of Deque Using Array
• Implementation of Deque Using LinkedList

Advantage of Deque: