stack, queue and Iterators

stack: last in, first out

A stack is like a pile of plates: you can only add to the top (push), look at the top (top) and take from the top (pop):

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

int main() {
    stack<string> plates;
    plates.push("red");
    plates.push("green");
    plates.push("blue");
    while (!plates.empty()) {
        cout << "Taking " << plates.top() << "\n";
        plates.pop();
    }
    return 0;
}

Output

Taking blue
Taking green
Taking red

The last plate in is the first one out. Stacks are used for undo buttons, the “back” button in a browser, and checking brackets.

queue: first in, first out

A queue is like a line at a shop: people join at the back (push) and are served from the front (front, pop):

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

int main() {
    queue<string> line;
    line.push("Ana");
    line.push("Ben");
    line.push("Cy");
    while (!line.empty()) {
        cout << "Serving " << line.front() << "\n";
        line.pop();
    }
    return 0;
}

Output

Serving Ana
Serving Ben
Serving Cy

Iterators

An iterator is like a bookmark that points at one item in a container. begin() points at the first item and end() points just after the last. *it reads the item and ++it moves to the next one. It works the same for every container:

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

int main() {
    vector<int> v = {10, 20, 30};
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << "\n";

    set<char> letters = {'c', 'a', 'b'};
    for (auto it = letters.begin(); it != letters.end(); ++it) {
        cout << *it << " ";
    }
    cout << "\n";
    return 0;
}

Output

10 20 30 
a b c 

Remember: This is why algorithms like sort(v.begin(), v.end()) and find take iterators: they can then work with any container. The range-based for loop uses iterators behind the scenes too.