Queues and Deques: First In, First Out

A line at the counter

A queue adds at the back and removes from the front: FIFO.

Think of it like this: A ticket counter line, a printer printing documents in order.

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

int main() {
    queue<string> line;
    line.push("Asha");          // join the back
    line.push("Ravi");
    line.push("Meera");
    while (!line.empty()) {
        cout << "serving " << line.front() << endl;
        line.pop();             // leave from the front
    }
    return 0;
}

Output

serving Asha
serving Ravi
serving Meera

A simulation: pass the parcel

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

int main() {
    deque<string> circle = {"A", "B", "C", "D", "E"};
    int k = 3;
    while (circle.size() > 1) {
        for (int i = 0; i < k - 1; i++) {       // pass the parcel k - 1 times
            circle.push_back(circle.front());
            circle.pop_front();
        }
        cout << "out: " << circle.front() << endl;
        circle.pop_front();
    }
    cout << "winner: " << circle.front() << endl;
    return 0;
}

Output

out: C
out: A
out: E
out: B
winner: D

Tip: Queues power breadth-first search (BFS) on trees and graphs – coming up soon.