Stacks and Queues
In the Class Templates lesson, you built your own Stack. The standard library has a ready-made stack, and it works the same way as a pile of plates: the last value you put on top is the first one you take off. This rule is called last in, first out, or LIFO. To use stacks, add #include <stack> at the top.
A web browser's Back button is a stack. Each page you visit is pushed on top, and Back takes you to the page on top:
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
stack<string> pages;
pages.push("home");
pages.push("search");
pages.push("results");
cout << pages.top() << "\n";
pages.pop();
cout << pages.top() << "\n";
cout << pages.size() << "\n";
return 0;
}
Output:
results
search
2
A stack has only a few operations:
| Operation | What it does |
|---|---|
push(x) | puts x on top |
top() | returns the value on top |
pop() | removes the value on top |
empty() | true if the stack has no values |
size() | the number of values |
You cannot read the middle of a stack, and you cannot loop over it with a range-based for loop. To go through every value, read the top and pop it, until the stack is empty:
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << "\n";
Output:
3 2 1
The values came out in the opposite order to the order they went in.
Always check empty() before you call top() or pop(). Calling them on an empty stack is a bug. When we tried top() on an empty stack here, the program crashed with a "Segmentation fault".
pop returns nothing
In C++, pop() only removes the value. It does not give it back to you. This program tries to save the popped value:
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
s.push(10);
int x = s.pop();
cout << x << "\n";
return 0;
}
Output:
main.cpp: In function ‘int main()’:
main.cpp:8:18: error: void value not ignored as it ought to be
pop() returns void, which means nothing, so there is no value to put in x. Read the value with top() first, then call pop().
Queues
A queue is like a line at a shop. People join at the back, and the person at the front is served first. This is first in, first out, or FIFO. Queues need #include <queue>.
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {
queue<string> line;
line.push("Alice");
line.push("Bob");
line.push("Emma");
cout << line.front() << "\n";
line.pop();
cout << line.front() << "\n";
cout << line.back() << "\n";
return 0;
}
Output:
Alice
Bob
Emma
A queue uses push, pop, empty and size like a stack. The difference is where values leave. push adds at the back, and pop removes from the front. There is no top(). You read the front with front() and the back with back().
You could do all of this with a vector. A stack or queue is still the better choice, because it allows only the operations that make sense, and anyone reading your code sees the rule right away. Both show up often in coding interviews. A stack is the usual tool for checking brackets: push each opening bracket, and when a closing bracket comes, the bracket on top must be its partner.
In the exercise, use a stack to check if a line of brackets is balanced.