Stacks, queues and pairs

Introduction

Many problems are really about the order in which waiting items are handled. The standard library has a ready-made container for each common order, and using the right one often makes a hard problem easy.

How it works

Notice that pop removes an item but does not return it, so read it with top or front first. Calling those on an empty container is undefined behaviour, so check empty().

Priority queues keep their largest item ready. They are built on a heap, so each push and pop is cheap even with many items:

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

int main() {
    priority_queue<int> tasks;
    tasks.push(3);
    tasks.push(9);
    tasks.push(5);
    while (!tasks.empty()) {
        cout << tasks.top() << " ";
        tasks.pop();
    }
    cout << endl;
    return 0;
}

pair holds two values, reached as .first and .second. Pairs compare by their first value and then by their second, which makes them convenient to sort.

pair<int, string> p = make_pair(3, string("Mitu"));

Syntax

stack<int> s;
s.push(1);
if (!s.empty()) {
    int top = s.top();
    s.pop();
}

Example

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

int main() {
    stack<string> pages;
    pages.push("home");
    pages.push("news");
    cout << pages.top() << endl;
    pages.pop();
    cout << pages.top() << endl;

    queue<string> line;
    line.push("Mitu");
    line.push("Rafi");
    cout << line.front() << " " << line.size() << endl;
    return 0;
}

Line by line

1. pages is a stack, like the Back button of a browser.
2. After two pushes, top shows the newest, news.
3. pop removes it, so top then shows home.
4. line is a queue, and people join at the back.
5. front shows the person who joined first.

Expected result

news
home
Mitu 2

In the real world

Stacks handle Undo and expression evaluation. Queues hold print jobs and messages between programs. Priority queues decide which task an operating system runs next, and they power the shortest-path algorithms in map apps.

Common mistakes

• Expecting pop to return the value.
• Calling top or front on an empty container.
• Expecting a priority_queue to give the smallest first. By default it gives the largest.
• Using a vector as a queue, which moves every element each time you remove the first.

Best practices

• Pick the container that matches the order you need.
• Always check empty() before you remove.
• Use deque when you need to work at both ends.

Summary

stack is last in, first out, and queue is first in, first out. priority_queue gives the largest first. pop does not return a value, so read first, and check for empty.

Mark lesson complete