Deque

A deque is a queue open at both ends: items can be added and removed at the front and at the back, each in $O(1)$ time, and any item can be read by its position. The name is short for double-ended queue and is said "deck".

Use it when items are added and removed at both ends of a row. If they are added only at the back and removed only from the front, a queue is enough; if they are added and removed at the same end, a stack. A vector is fast only at its back: adding or removing an item at its front moves every other item.

How it works

The queue kept its items in an array with two indices: head is the cell of the front item, and tail is the first free cell after the back item. A deque can use the same array, but push_front needs the free cell just left of head, and in the queue head starts at cell 0.

So start in the middle. For $q$ commands, take an array of $2q$ cells and set head = tail = q, leaving $q$ free cells on each side. The deque is the cells from head to tail - 1:

• push_front subtracts 1 from head and writes x into cell head;

• push_back writes x into cell tail and adds 1 to tail;

• pop_front adds 1 to head;

• pop_back subtracts 1 from tail;

• front reads cell head, and back reads cell tail - 1;

• d[i] reads cell head + i;

• the size is tail - head, and the deque is empty when head == tail.

Each of these touches one cell, so each takes $O(1)$ time, and $q$ commands take $O(q)$.

Let's run a few commands on an empty deque to see how it works.

The array has 20 cells, and head and tail both start at cell 10: the deque is empty.

push_back(5) writes 5 into cell 10, and tail moves right to 11.

push_back(8) writes 8 into cell 11, and tail moves right to 12.

push_front(2) moves head left to 9 and writes 2 there.

push_front(6) moves head left to 8 and writes 6 there.

pop_back() moves tail back to 11 and prints and removes 8, the item in cell 11.

push_back(1) writes 1 into cell 11, and tail moves right to 12.

pop_front() prints and removes 6, the item in cell 8, and head moves right to 9.

push_front(4) moves head left to 8 and writes 4 there.

front() prints 4, the item in cell head = 8.

back() prints 1, the item in cell tail - 1 = 11.

1/11

Fig. 1. Ten commands on an array of 20 cells. head and tail move in both directions, and a popped item leaves from its own end.

Unlike the queue, freed cells are used again at both ends. The deque ends as 4 2 5 1, in cells 8 to 11.

The program below reads the number of commands q (1 \le q \le 10^5), then q lines, each push_front x, push_back x (|x| \le 10^9), pop_front, pop_back, front, back or size. Pops, front and back come only when the deque is not empty. It prints the item for a pop, front or back, and the count for size.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int q;
    cin >> q;
    vector<int> a(2 * q);
    int head = q, tail = q;   // the deque is cells head .. tail - 1

    for (int i = 0; i < q; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "push_front") {
            int x;
            cin >> x;
            head--;
            a[head] = x;
        } else if (cmd == "push_back") {
            int x;
            cin >> x;
            a[tail] = x;
            tail++;
        } else if (cmd == "pop_front") {
            cout << a[head] << '\n';
            head++;
        } else if (cmd == "pop_back") {
            tail--;
            cout << a[tail] << '\n';
        } else if (cmd == "front") {
            cout << a[head] << '\n';
        } else if (cmd == "back") {
            cout << a[tail - 1] << '\n';
        } else if (cmd == "size") {
            cout << tail - head << '\n';
        }
    }
}

In C++

Contests rarely need your own deque. The C++ deque is in the header <deque>, and deque<int> d; declares an empty deque of integers with every operation from the table. The same program needs no array size and no indices:

#include <deque>
#include <iostream>
#include <string>
using namespace std;

int main() {
    int q;
    cin >> q;
    deque<int> d;

    for (int i = 0; i < q; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "push_front") {
            int x;
            cin >> x;
            d.push_front(x);
        } else if (cmd == "push_back") {
            int x;
            cin >> x;
            d.push_back(x);
        } else if (cmd == "pop_front") {
            cout << d.front() << '\n';
            d.pop_front();
        } else if (cmd == "pop_back") {
            cout << d.back() << '\n';
            d.pop_back();
        } else if (cmd == "front") {
            cout << d.front() << '\n';
        } else if (cmd == "back") {
            cout << d.back() << '\n';
        } else if (cmd == "size") {
            cout << d.size() << '\n';
        }
    }
}

std::deque keeps the items in blocks of a fixed size (512 bytes with GCC, 128 ints) and a small array of pointers to the blocks. When an end runs out of room, it adds a new block there. The first block is often only partly used, so to find item i the deque adds i to the place of the front item in the first block and divides the sum by the block size: the quotient says how many blocks to skip, and the remainder is the place in that block. So d[i] takes $O(1)$ time.

Examples of use

In 0-1 BFS every edge weighs 0 or 1. A vertex reached over a 0-edge goes to the front of the deque, one reached over a 1-edge to the back, so a vertex at the same distance as the current one is taken before every vertex one step farther.

The monotonic queue finds the minimum of every window of $k$ consecutive numbers in $O(n)$ time. It keeps in a deque the indices of the window's numbers that can still become its minimum, with their values increasing from front to back. A new number pops larger values from the back, and an index that leaves the window is popped from the front, so the minimum is at the front. Each index is pushed once and popped at most once.

Common mistakes

• Using a vector and adding at its front with v.insert(v.begin(), x), or removing with v.erase(v.begin()), which moves every other item on each call. Use std::deque.

Similar structures

A queue and a stack use only some of the deque's operations. In C++, std::queue and std::stack are built on std::deque by default.

If you need the smallest item wherever it is, not one at an end, use a priority queue; if you need both the smallest and the largest, use a set, which gives both ends of the sorted order.

Two pointers solve "remove items from both ends" when nothing is added: the items left form one segment, so two indices are enough.

Practice