Stack Basics

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

int main() {
    // Create stack
    stack<int> st;
    
    // Push elements
    st.push(10);
    st.push(20);
    st.push(30);
    st.push(40);
    st.push(50);
    
    cout << "Stack size: " << st.size() << endl;
    cout << "Top element: " << st.top() << endl;
    
    // Display stack (by popping)
    cout << "\nStack elements (LIFO - Last In First Out):" << endl;
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
    
    // Stack for string reversal
    stack<char> charStack;
    string str = "Hello";
    
    cout << "\nOriginal string: " << str << endl;
    
    // Push all characters
    for (char c : str) {
        charStack.push(c);
    }
    
    // Pop to reverse
    string reversed = "";
    while (!charStack.empty()) {
        reversed += charStack.top();
        charStack.pop();
    }
    
    cout << "Reversed string: " << reversed << endl;
    
    // Check balanced parentheses
    stack<char> parenStack;
    string expression = "((()))";
    bool balanced = true;
    
    for (char c : expression) {
        if (c == '(') {
            parenStack.push(c);
        } else if (c == ')') {
            if (parenStack.empty()) {
                balanced = false;
                break;
            }
            parenStack.pop();
        }
    }
    
    if (parenStack.empty() && balanced) {
        cout << "\nExpression '" << expression << "' is balanced" << endl;
    } else {
        cout << "\nExpression '" << expression << "' is not balanced" << endl;
    }
    
    return 0;
}

Stack size: 5
Top element: 50

Stack elements (LIFO - Last In First Out):
50 40 30 20 10

Original string: Hello
Reversed string: olleH

Expression '((()))' is balanced

This program teaches you how to use Stack Basics in C++. Stack is a LIFO (Last In First Out) container where elements are added and removed from the top. It's perfect for problems requiring reverse order processing, expression evaluation, and maintaining state.

---

1. What This Program Does

The program demonstrates stack operations:

• Creating stack and pushing elements
• Accessing top element
• Popping elements (LIFO order)
• String reversal using stack
• Balanced parentheses checking

Stacks provide simple, efficient last-in-first-out data access.

---

2. Header Files Used

1. #include <iostream>

   • Provides cout and cin for input/output operations.

2. #include <stack>

   • Provides stack container class.

---

3. Understanding Stack

LIFO Concept:

• Last In First Out
• Last element added is first removed
• Like a stack of plates
• Only top element accessible

Key Features:

• Simple operations
• O(1) time complexity
• Last-in-first-out order
• Top element only accessible

---

4. Stack Operations

push():

st.push(10); // Add to top

pop():

st.pop(); // Remove from top

top():

int value = st.top(); // Access top element

How it works:

• push(): adds element to top
• pop(): removes top element
• top(): returns top element (doesn't remove)
• All O(1) operations

---

5. Stack Properties

Size and Empty:

st.size() // Number of elements st.empty() // True if empty

Access:

• Only top element accessible
• Cannot access middle elements
• Must pop to access lower elements
• LIFO order enforced

---

6. String Reversal

Using Stack:

1. Push all characters to stack
2. Pop characters to reverse string

How it works:

• Push: "Hello" → stack: o, l, l, e, H (top)
• Pop: "olleH" (reversed)
• LIFO naturally reverses order

---

7. Balanced Parentheses

Algorithm:

1. Push '(' onto stack
2. Pop when ')' encountered
3. Balanced if stack empty at end

How it works:

• '(' pushes, ')' pops
• Stack tracks nesting level
• Empty stack = balanced
• Non-empty = unbalanced

---

8. When to Use Stack

Best For:

• Expression evaluation
• Balanced parentheses/braces
• Function call simulation
• Undo operations
• Reverse order processing
• Depth-first search (DFS)

Example Scenarios:

• Calculator (postfix evaluation)
• Syntax checking
• Backtracking algorithms
• Recursion simulation
• Browser back button

---

9. Important Considerations

LIFO Order:

• Last added = first removed
• Cannot access arbitrary elements
• Must pop to access lower elements
• Natural for reverse processing

Performance:

• All operations: O(1)
• Very efficient
• Simple implementation
• Minimal overhead

Limitations:

• Only top element accessible
• Cannot search or access middle
• Must pop to access other elements
• Use other containers if random access needed

---

10. return 0;

This ends the program successfully.

---

Summary

• Stack: LIFO (Last In First Out) container, only top element accessible.
• Operations: push(), pop(), top(), empty(), size() - all O(1).
• Common uses: expression evaluation, balanced parentheses, undo operations.
• Understanding stacks enables reverse order processing and state management.
• Essential for algorithms requiring LIFO behavior.

This program is fundamental for learning stack data structure, understanding LIFO operations, and preparing for expression evaluation and algorithm implementation in C++ programs.