Введение в стеки в C ++

Как использовать стек

Объявление стека

stack<int> A; // declares an empty stack.

Толкать

A.push(newElement); // Pushes a new element. O(1)

Поп

A.pop(); // O(1) pop

пустой

A.empty() // O(1)

Размер

A.size(); // O(1)

верхний

A.top(); // O(1). Gives the top element.

Пример:

Проверить наличие сбалансированной круглой скобки

            stack<char> st;
            map<char, char> matchingBracket; 
            matchingBracket['{'] = '}';
            matchingBracket['['] = ']';
            matchingBracket['('] = ')';
            for (int i = 0; i < s.length(); i++) {
                if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
                    st.push(s[i]);
                } else if (st.empty() || 
                        matchingBracket[st.top()] != s[i]) {
                    return false;
                } else {
                    st.pop();
                }
            }
            return st.empty();

Сложность времени: O (len (A))
Вспомогательное пространство: O (len (A)) для стека.