All lessons
LESSON 39/53Ready-made Containers
Stack and Queue
GOALTake the newest first, or take the oldest first.
A stack is a pile of plates — you take from the top, so the last one on is the first one off. A queue is a shop line — first in, first out. Which you need is usually obvious from the problem.
ON THIS PAGE
SHOW EXAMPLE IN
//THE EXAMPLE
main.cpp
#include <iostream>
#include <stack>
#include <queue>
#include <string>
using namespace std;
bool balanced(const string& s) {
stack<char> st;
for (char c : s) {
if (c == '(') st.push(c);
else if (c == ')') {
if (st.empty()) return false;
st.pop();
}
}
return st.empty();
}
int main() {
cout << (balanced("(()())") ? "yes" : "no") << endl;
cout << (balanced("(()") ? "yes" : "no") << endl;
queue<string> line;
line.push("Bat");
line.push("Suvd");
cout << line.front() << endl;
line.pop();
cout << line.front() << endl;
return 0;
}> what you see
yes no Bat Suvd
//LINE BY LINE
Watch it run
Reading "(()())" from the left. The stack is empty.
Telling which one you need
The wording usually tells you. "Most recent", "undo", "go back" means a stack. "Queue", "in turn", "oldest first" means a queue.
- Checking that brackets match — a stack.
- The undo history of a button — a stack.
- A printer's job list — a queue.
- Breadth-first search on a grid — a queue.
pop does not mean the same thing
This is the most common stumble for a student switching languages: pop returns nothing in C++, and returns the value in Python.
int x = st.top(); // read it
st.pop(); // then remove itIn C++, calling top() or pop() on an empty stack crashes at run time with no compiler warning. Always test empty() first.