Intro to Stacks in C++

How to use a Stack

Stack declaration

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

Push

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

Pop

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

isEmpty

A.empty() // O(1)

Size

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

Top

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

Example:

Check for balanced parenthesis

            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();

Time Complexity: O(len(A))
Auxiliary Space: O(len(A)) for stack.