Deques

A deque is a double-ended queue, pronounced “deck.” It stores an ordered sequence while allowing insertion and removal at both the front and the back. A queue hides this flexibility to enforce FIFO order; a deque exposes it directly. This makes deques useful for sequences that grow at both ends, maintaining sliding windows, and 0–1 BFS. This lesson first builds a command interpreter so every operation has a visible effect, then uses a monotonic deque to find the minimum of each fixed-length window in linear total time. A deque is a container, not an algorithm: correctness comes from the invariant we maintain on its contents.

Prerequisites: Arrays and Vectors, Queues, loops, and 0-based versus 1-based indexing.

Build the idea

1. 1. Insert and remove at either end. Include <deque> and declare deque<long long> d;. push_front(x) places x before the current first element; push_back(x) places x after the last. pop_front() removes the first element and pop_back() removes the last. Both pop operations return nothing. To report a removed item, copy front or back before removal. Check empty() first, because removing from an empty deque or reading its endpoints is invalid. Duplicate values remain separate elements.
2. 2. Inspect values without changing order. front() and back() inspect the endpoints; size() reports the number of elements. A deque also supports O(1) indexed access, such as d[2] for its third element. Indices start at zero and must be less than size. Unlike a vector, a deque is not guaranteed contiguous storage, so it has no general-purpose contiguous data() array. Do not keep iterators across arbitrary modifications without checking the standard’s invalidation rules; adding at an end invalidates deque iterators even when references to existing elements remain valid.
3. 3. Trace the command example. From empty, push_back 4, push_front 2, then push_back 9. The order is [2,4,9], so front=2, back=9, size=3. pop_front removes 2 and leaves [4,9]. push_front -3 gives [-3,4,9]; pop_back removes 9, leaving [-3,4]. Removing both remaining elements leaves the deque empty. The interpreter prints removed values to make pop behavior explicit. In C++ it still obtains each value using front/back before calling the corresponding void-returning pop operation.
4. 4. Choose between queue, deque, and vector. A queue offers push at the back and pop at the front, enforcing FIFO. A deque can act as that queue, a stack using one end, or a sequence edited at both ends. A vector gives contiguous storage and efficient appends, but inserting or removing at its front shifts existing elements and costs O(n). Deque operations at either end are O(1), as is indexing; insertion or erasure at an arbitrary middle position is O(n) in the worst case. Neither container makes middle edits free. Prefer the simplest interface expressing the required behavior.
5. 5. Turn a deque into a sliding-window minimum. For array [4,2,2,5,1] and window length 3, the windows have minima [2,2,1]. A brute-force scan uses O(nk) time. Instead store candidate indices in increasing order while their values strictly increase. Before processing index i, remove front indices ≤ i−k: they lie before the current window. Remove back indices whose values are ≥ a[i], because i is no larger and expires later. Append i; once i≥k, the front names the minimum of the complete current window. Store indices, not just values, so equal candidates have distinguishable expiration times.
6. 6. Prove why discarded candidates stay useless. Suppose an older index j has a[j]≥a[i]. Any future window whose right endpoint is at least i and still contains j also contains i. The newer value is at least as good for a minimum and remains valid longer, so j can never be uniquely necessary again. Removing it preserves every future answer. Each index is inserted once and removed at most once, from either end; therefore all while-loop removals together are O(n). This is amortized analysis, not a claim that each individual input step does constant worst-case work. The separate Monotonic Queues lesson develops this pattern and its DP applications further.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<deque>
#include<string>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    if(!(cin>>q)||q<0){
        return 0;
    }
    deque<long long>d;
    while(q--){
        string op;
        cin>>op;
        if(op=="PUSH_FRONT"||op=="PUSH_BACK"){
            long long x;
            cin>>x;
            // Choose the insertion end; existing elements keep their order.
            if(op=="PUSH_FRONT"){
                d.push_front(x);
            }
            else{
                d.push_back(x);
            }
        }
        else if(op=="POP_FRONT"||op=="POP_BACK"){
            if(d.empty()){ // Never inspect or pop an empty deque.
                cout<<"EMPTY\n";
            }
            else if(op=="POP_FRONT"){
                cout<<d.front()<<'\n'; // Read before the void-returning pop.
                d.pop_front();
            }
            else{
                cout<<d.back()<<'\n';
                d.pop_back();
            }
        }
        else if(op=="FRONT"||op=="BACK"){
            if(d.empty()){
                cout<<"EMPTY\n";
            }
            else{
                cout<<(op=="FRONT"?d.front():d.back())<<'\n';
            }
        }
        else if(op=="SIZE"){
            cout<<d.size()<<'\n'; // Counts both duplicate and distinct values.
        }
        else if(op=="EMPTY"){
            cout<<(d.empty()?"YES":"NO")<<'\n';
        }
    }
}

Complexity analysis

For a deque of s elements, push_front, push_back, pop_front, pop_back, front, back, empty, size, and indexed access are O(1). General middle insertion/erasure is O(s) worst case. The command program executes q commands in O(q) time, excluding numeric text parsing/printing, and stores O(s_max) elements, where s_max is its maximum simultaneous size. The sliding-window example processes n values in O(n) total time and maintains at most k candidate indices. Its stored input vector takes O(n) space; a fully streaming implementation can retain only O(k) candidate indices and values.

Example input and output

Read q ≥ 0, followed by q commands. PUSH_FRONT x and PUSH_BACK x insert signed-64-bit x and print nothing. POP_FRONT and POP_BACK print and remove an endpoint, or print EMPTY without changing an empty deque. FRONT and BACK print an endpoint or EMPTY. SIZE prints the element count. EMPTY prints YES or NO. All commands are uppercase.

Input

17
EMPTY
PUSH_BACK 4
PUSH_FRONT 2
PUSH_BACK 9
FRONT
BACK
SIZE
POP_FRONT
PUSH_FRONT -3
POP_BACK
FRONT
BACK
POP_BACK
POP_FRONT
POP_FRONT
SIZE
EMPTY

Output

YES
2
9
3
2
9
-3
4
4
-3
EMPTY
0
YES

Pushing 4, then 2 at the front, then 9 at the back creates [2,4,9]. Removing the front prints 2. After inserting -3 at the front, removing the back prints 9. The remaining order is [-3,4]. Removing 4 and -3 empties the deque, so another removal prints EMPTY, size is 0, and EMPTY prints YES.

Read n k with 1 ≤ k ≤ n, then n signed-64-bit values. Print the minimum of each length-k window in left-to-right order. Sequence positions are 1-based internally. Invalid n or k prints INVALID.

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    if(!(cin>>n>>k)||n<1||k<1||k>n){
        cout<<"INVALID\n";
        return 0;
    }
    vector<long long>a(n+1);
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    deque<int>candidates; // Increasing indices with strictly increasing values.
    bool first=true;
    for(int i=1;i<=n;++i){
        // Remove candidates lying before this window's left boundary i-k+1.
        while(!candidates.empty()&&candidates.front()<=i-k){
            candidates.pop_front();
        }
        // The newer, no-larger value dominates each removed older candidate.
        while(!candidates.empty()&&a[candidates.back()]>=a[i]){
            candidates.pop_back();
        }
        candidates.push_back(i);
        if(i>=k){ // Output only complete windows; the front is their minimum.
            if(!first){
                cout<<' ';
            }
            first=false;
            cout<<a[candidates.front()];
        }
    }
    cout<<'\n';
}

Input

5 3
4 2 2 5 1

Output

2 2 1

The windows [4,2,2], [2,2,5], and [2,5,1] have minima 2, 2, and 1. Equal 2s are handled by keeping the newer candidate, which expires later.

Complexity: O(n) total time: each index is inserted once and removed at most once. Candidate storage is O(k), and the stored input vector makes total storage O(n). No arithmetic on values is required, so all signed-64-bit input values are supported.

Practical applications

Use a deque for both-end sequence editing, implementing a queue or stack, maintaining sliding-window minima/maxima, and 0–1 BFS. In 0–1 BFS, an improved zero-cost neighbor enters the front and an improved unit-cost neighbor enters the back; this rule does not extend to arbitrary weights. Static arbitrary range queries suggest sparse tables, while interleaved updates and arbitrary interval queries suggest segment trees.

Check your understanding

Which operation is efficient on deque but requires shifting existing elements on vector?

Put it into practice

Extend the interpreter with AT i, which prints the 0-based indexed value or INVALID for an out-of-range index.