std::stack and std::queue

1#include <stack>
2#include <queue>
3
4// Stack - LIFO
5stack<int> stk;
6stk.push(1);
7stk.push(2);
8stk.push(3);
9cout << stk.top();  // 3
10stk.pop();          // Remove 3
11stk.empty();        // false
12stk.size();         // 2
13
14// Queue - FIFO
15queue<int> q;
16q.push(1);
17q.push(2);
18q.push(3);
19cout << q.front();  // 1
20cout << q.back();   // 3
21q.pop();            // Remove 1
22
23// Specify underlying container
24stack<int, vector<int>> stk2;
25queue<int, list<int>> q2;
26
27// Classic problems:
28// Stack: parentheses matching, expression evaluation
29// Queue: BFS, level order traversal
30
31// Monotonic stack example
32vector<int> nextGreater(vector<int>& nums) {
33    int n = nums.size();
34    vector<int> result(n, -1);
35    stack<int> stk;
36    for (int i = 0; i < n; i++) {
37        while (!stk.empty() && nums[stk.top()] < nums[i]) {
38            result[stk.top()] = nums[i];
39            stk.pop();
40        }
41        stk.push(i);
42    }
43    return result;
44}