C++ Stack

Key Stack Operations

myStack.push(42);

myStack.pop();

int topElement = myStack.top();

bool isEmpty = myStack.empty();
int size = myStack.size();

🔹 Basic Stack Operations

Stacks are LIFO (Last-In, First-Out) data structures providing push, pop, and top operations for managing elements in reverse order. The C++ std::stack adapter typically uses a deque or vector as its underlying container. Key operations include push to add, pop to remove the top, and top to inspect without removal. Stacks are fundamental for undo mechanisms, recursion simulation, expression evaluation, and depth-first search. Their simplicity and constrained interface make them reliable for controlling access order, ensuring elements are processed in the exact reverse sequence of their addition.

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<string> books;
    
    // Push books onto stack
    books.push("C++ Primer");
    books.push("Effective C++");
    books.push("Modern C++");
    
    cout << "Stack size: " << books.size() << endl;
    cout << "Top book: " << books.top() << endl;
    
    // Remove books from stack (LIFO order)
    cout << "\nRemoving books:" << endl;
    while(!books.empty()) {
        cout << books.top() << endl;
        books.pop();
    }
    
    cout << "Stack is now empty: " << (books.empty() ? "Yes" : "No") << endl;
    
    return 0;
}

🔹 Stack for Expression Evaluation

Stacks are algorithmically central to evaluating postfix expressions and checking syntax, like balanced parentheses in code. For expression evaluation, operands are pushed onto the stack, and operators pop the required operands, compute, and push the result. For balancing, an opening symbol is pushed, and a closing symbol must match the top before popping. This LIFO behavior perfectly matches nested structures. This makes stacks indispensable in compilers, calculators, and parsers, providing an efficient, intuitive mechanism for handling nested or hierarchical data and operations.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isBalanced(string expression) {
    stack<char> brackets;
    
    for(char ch : expression) {
        if(ch == '(' || ch == '[' || ch == '{') {
            brackets.push(ch);
        }
        else if(ch == ')' || ch == ']' || ch == '}') {
            if(brackets.empty()) return false;
            
            char top = brackets.top();
            brackets.pop();
            
            if((ch == ')' && top != '(') ||
               (ch == ']' && top != '[') ||
               (ch == '}' && top != '{')) {
                return false;
            }
        }
    }
    
    return brackets.empty();
}

int main() {
    string expr1 = "{[()]}";
    string expr2 = "{[(])}";
    
    cout << expr1 << " is " << (isBalanced(expr1) ? "balanced" : "not balanced") << endl;
    cout << expr2 << " is " << (isBalanced(expr2) ? "balanced" : "not balanced") << endl;
    
    return 0;
}

🔹 Stack for Undo Operations

Implementing undo functionality naturally aligns with the stack’s LIFO principle, where each action is pushed and undone by popping. Each user action (like text insertion) is recorded as a state or command object on the stack. An undo operation pops the most recent action, reverting to the previous state. This provides a clean, bounded history. Stacks ensure undo operations occur in the exact reverse order of execution, a requirement for coherent user experience in editors, graphics software, and transactional systems. This pattern is a classic and effective use of the stack data structure.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

class TextEditor {
private:
    string text;
    stack<string> history;
    
public:
    void write(string newText) {
        history.push(text);  // Save current state
        text += newText;
        cout << "Added: " << newText << endl;
        cout << "Current text: " << text << endl;
    }
    
    void undo() {
        if(!history.empty()) {
            text = history.top();
            history.pop();
            cout << "Undo successful" << endl;
            cout << "Current text: " << text << endl;
        } else {
            cout << "Nothing to undo" << endl;
        }
    }
};

int main() {
    TextEditor editor;
    
    editor.write("Hello ");
    editor.write("World!");
    editor.undo();
    editor.undo();
    editor.undo();  // Nothing to undo
    
    return 0;
}