Stacks - Забони барномасозии C++ барои барномасозии рақобатӣ

Week 10Stacks, Queues, Deques and Simulation Problems

Stacks

A pile you can only touch at the top: push, top and pop, a vector or a string used as a stack, matching brackets, a postfix calculator, and a stack that knows its minimum.

Назария
Дарси 1 аз 7
Хониш: 21 дақиқа
Саволҳо: 5

In Week 9 you met the call stack: every new call goes on top, only the top call runs, and the last call made is the first to return. That way of keeping things — a pile you can only touch at the top — is useful far beyond function calls, and C++ has it ready-made.

Think of a pile of plates. A clean plate goes on top, and you take the next one from the top. The plate at the bottom waits until every plate above it has gone. Last in, first out — programmers write it LIFO — and a pile that works this way is called a stack.

stack: push, top, pop

Operation	What it does
`st.push(x)`	puts `x` on top
`st.top()`	the top element — it stays on the stack
`st.pop()`	removes the top element and gives back nothing
`st.empty()`	`true` if there is nothing on the stack
`st.size()`	how many elements are on it

Each of these takes a single step, however big the stack is. Two rules save a lot of grief:

pop() returns nothing. To use the top element, read it with top() first, then pop().
Never call top() or pop() on an empty stack. C++ doesn't stop you: the program crashes or quietly reads garbage. Check !st.empty() first, unless you are sure.

навбатӣ

Practice: Stacks

Four problems for the stack: brackets, letters that cancel, a postfix calculator and a stack with its minimum.

Дарси навбатӣ

Дарси пешина Ба харитаи курс

cay#t

cat

([]{()})

YES

9
5 1 2 + 4 * + -3 -

11
push 6
push 9
push 2
min
pop
min
pop
pop
min
push 7
min

2
6
empty
7

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    stack<int> st;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        st.push(x);                // the newest number goes on top
    }
    while (!st.empty()) {
        cout << st.top() << " ";   // look at the top...
        st.pop();                  // ...then take it off
    }
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string keys;
    cin >> keys;
    stack<char> text;              // the letters typed so far, the last one on top
    for (char c : keys) {
        if (c == '#') {
            if (!text.empty()) {
                text.pop();        // backspace: take the top letter off
            }
        } else {
            text.push(c);          // a letter goes on top
        }
    }
    stack<char> poured;            // pouring reverses the order once more
    while (!text.empty()) {
        poured.push(text.top());
        text.pop();
    }
    while (!poured.empty()) {
        cout << poured.top();      // the first letter typed is on top now
        poured.pop();
    }
    cout << "\n";
    return 0;
}

stack<char> st;                   // the letters still standing
for (char c : s) {
    if (!st.empty() && st.top() == c) {
        st.pop();                 // c and the top vanish together
    } else {
        st.push(c);
    }
}

#include <bits/stdc++.h>
using namespace std;

bool matches(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    stack<char> st;
    bool ok = true;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);                       // an opening bracket waits on the stack
        } else if (st.empty() || !matches(st.top(), c)) {
            ok = false;                       // nothing to close, or the wrong type
            break;
        } else {
            st.pop();                         // the pair is complete
        }
    }
    if (!st.empty()) {
        ok = false;                           // some brackets were never closed
    }
    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

int open = 0, broken = 0;
for (char c : s) {
    if (c == '(') {
        open++;               // one more ( is waiting
    } else if (open > 0) {
        open--;               // this ) closes a waiting (
    } else {
        broken++;             // this ) has nothing to close
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m;
    cin >> m;
    stack<long long> st;
    for (int i = 0; i < m; i++) {
        string tok;
        cin >> tok;
        if (tok == "+" || tok == "-" || tok == "*") {
            long long y = st.top();           // the later value
            st.pop();
            long long x = st.top();           // the earlier value
            st.pop();
            if (tok == "+") {
                st.push(x + y);
            } else if (tok == "-") {
                st.push(x - y);
            } else {
                st.push(x * y);
            }
        } else {
            st.push(stoll(tok));              // a number: text -> long long
        }
    }
    cout << st.top() << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    cin >> q;
    stack<pair<int, int>> st;                 // (value, smallest value from here down)
    for (int i = 0; i < q; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int x;
            cin >> x;
            int low = x;
            if (!st.empty()) {
                low = min(x, st.top().second);
            }
            st.push({x, low});
        } else if (cmd == "pop") {
            if (!st.empty()) {
                st.pop();                     // the ones below still know their minimum
            }
        } else {
            if (st.empty()) {
                cout << "empty\n";
            } else {
                cout << st.top().second << "\n";
            }
        }
    }
    return 0;
}