Stack

Solutions that utilize stack data structure

A stack is a Last-In-First-Out (LIFO) data structure that supports two main operations: push (insertion) and pop (deletion). In C++, you can use the built-in stack container from the Standard Template Library (STL).

Basic Stack Operations in C++

#include <stack>

// Declaration
stack<long long> mystack;  // Create an empty stack of long long integers

// Basic Operations
// 1. push(value) - Add element to top of stack - O(1)
mystack.push(6);  // mystack = [6]
mystack.push(3);  // mystack = [6, 3]
mystack.push(9);  // mystack = [6, 3, 9]

// 2. pop() - Remove element from top of stack - O(1)
mystack.pop();    // Removes 9, mystack = [6, 3]

// 3. top() - Get value of top element - O(1)
int topValue = mystack.top();  // Returns 3

// 4. size() - Get number of elements in stack - O(1)
int stackSize = mystack.size();  // Returns 2

// 5. empty() - Check if stack is empty - O(1)
bool isEmpty = mystack.empty();  // Returns false

Important Notes:

  • Always check if stack is not empty before calling pop() or top()
  • Stack has constant time O(1) complexity for all basic operations
  • Stack is particularly useful for:
    • Function call management
    • Expression evaluation
    • Backtracking algorithms
    • Undo operations
    • Parentheses matching

Common Mistakes to Avoid:

  1. Calling pop() or top() on empty stack
  2. Not including <stack> header
  3. Forgetting that pop() doesn’t return the removed value

Example Usage:

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

int main() {
    stack<int> st;
    
    // Push elements
    st.push(1);
    st.push(2);
    st.push(3);
    
    // Safe way to process stack
    while (!st.empty()) {
        cout << st.top() << " ";  // Print top element
        st.pop();                 // Remove top element
    }
    // Output: 3 2 1
    
    return 0;
}

Problems that demonstrate the effective use of stack data structure to solve algorithmic challenges.