Learn Deque Double-ended Queue — Free DSA Tutorial

What is a Deque?

A deque (double-ended queue) generalizes both stacks and queues by allowing insertion and removal at both the front and the rear, not just one fixed end. This flexibility makes a deque useful for algorithms like sliding window maximum, where elements need to be added and removed from both ends efficiently.

Example: What is a Deque?

#include <iostream>
#include <deque>
using namespace std;
int main() {
	deque<int> dq;
	dq.push_back(2); dq.push_back(3);
	dq.push_front(1);
	for (int x : dq) cout << x << " ";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Deque<Integer> dq = new ArrayDeque<>();
		dq.addLast(2); dq.addLast(3);
		dq.addFirst(1);
		System.out.println(dq);
	}
}

from collections import deque
dq = deque()
dq.append(2)
dq.append(3)
dq.appendleft(1)
print(list(dq))

#include <stdio.h>
int main() {
	int dq[5] = {1, 2, 3};
	for (int i = 0; i < 3; i++) printf("%d ", dq[i]);
	return 0;
}

Insert at Front

Inserting at the front adds a new element ahead of everything currently in the deque, an operation a plain queue simply doesn't support since it can only add at the rear. Both insertion operations on a well-implemented deque (usually backed by a doubly linked list or circular buffer) run in constant O(1) time.

Example: Insert at Front

#include <iostream>
#include <deque>
using namespace std;
int main() {
	deque<int> dq = {2, 3};
	dq.push_front(1);
	dq.push_front(0);
	for (int x : dq) cout << x << " ";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Deque<Integer> dq = new ArrayDeque<>(Arrays.asList(2, 3));
		dq.addFirst(1);
		dq.addFirst(0);
		System.out.println(dq);
	}
}

from collections import deque
dq = deque([2, 3])
dq.appendleft(1)
dq.appendleft(0)
print(list(dq))

#include <stdio.h>
int main() {
	int dq[4] = {0, 1, 2, 3};
	for (int i = 0; i < 4; i++) printf("%d ", dq[i]);
	return 0;
}

Insert at Rear

Inserting at the rear works just like enqueue on a normal queue, appending the new element after everything already there. Because both ends support O(1) insertion, a deque can be used as a stack, a queue, or both at once depending on which end you use.

Example: Insert at Rear

#include <iostream>
#include <deque>
using namespace std;
int main() {
	deque<int> dq = {1, 2};
	dq.push_back(3);
	dq.push_back(4);
	for (int x : dq) cout << x << " ";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Deque<Integer> dq = new ArrayDeque<>(Arrays.asList(1, 2));
		dq.addLast(3);
		dq.addLast(4);
		System.out.println(dq);
	}
}

from collections import deque
dq = deque([1, 2])
dq.append(3)
dq.append(4)
print(list(dq))

#include <stdio.h>
int main() {
	int dq[4] = {1, 2, 3, 4};
	for (int i = 0; i < 4; i++) printf("%d ", dq[i]);
	return 0;
}

Deque as Stack

Because it supports both ends, a deque can behave exactly like a stack just by consistently using only one end for both insertions and removals, push and pop both happening at the same side.

Example: Deque as Stack

#include <iostream>
#include <deque>
using namespace std;
int main() {
	deque<int> dq;
	dq.push_back(1); dq.push_back(2); dq.push_back(3);
	cout << "Popped: " << dq.back();
	dq.pop_back();
	cout << ", New top: " << dq.back();
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Deque<Integer> dq = new ArrayDeque<>();
		dq.addLast(1); dq.addLast(2); dq.addLast(3);
		System.out.print("Popped: " + dq.peekLast());
		dq.removeLast();
		System.out.println(", New top: " + dq.peekLast());
	}
}

from collections import deque
dq = deque()
dq.append(1); dq.append(2); dq.append(3)
print("Popped:", dq[-1])
dq.pop()
print("New top:", dq[-1])

#include <stdio.h>
int main() {
	int dq[3] = {1, 2, 3};
	int top = 2;
	printf("Popped: %d\n", dq[top]);
	top--;
	printf("New top: %d", dq[top]);
	return 0;
}

Deque Applications

Deques are the standard tool for sliding-window problems (maintaining a monotonic window of candidates), undo/redo systems that need to add and remove from both ends, and any scenario needing efficient access at both boundaries.

Example: Deque Applications

#include <iostream>
#include <deque>
using namespace std;
int main() {
	int arr[] = {1, 3, -1, -3, 5};
	deque<int> dq;
	for (int i = 0; i < 5; i++) {
		while (!dq.empty() && arr[dq.back()] < arr[i]) dq.pop_back();
		dq.push_back(i);
		if (i >= 2) cout << arr[dq.front()] << " ";
	}
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {1, 3, -1, -3, 5};
		Deque<Integer> dq = new ArrayDeque<>();
		for (int i = 0; i < 5; i++) {
			while (!dq.isEmpty() && arr[dq.peekLast()] < arr[i]) dq.pollLast();
			dq.addLast(i);
			if (i >= 2) System.out.print(arr[dq.peekFirst()] + " ");
		}
	}
}

from collections import deque
arr = [1, 3, -1, -3, 5]
dq = deque()
for i in range(5):
    while dq and arr[dq[-1]] < arr[i]:
        dq.pop()
    dq.append(i)
    if i >= 2:
        print(arr[dq[0]], end=" ")

#include <stdio.h>
int main() {
	int arr[] = {1, 3, -1, -3, 5};
	int dq[5], front = 0, back = -1;
	for (int i = 0; i < 5; i++) {
		while (back >= front && arr[dq[back]] < arr[i]) back--;
		dq[++back] = i;
		if (i >= 2) printf("%d ", arr[dq[front]]);
	}
	return 0;
}

Deque Double-ended Queue

What is a Deque?

Insert at Front

Insert at Rear

Deque as Stack

Deque Applications

Chapter Quiz — Complete all 5 topics to unlock

Login to run this code