C++ Stacks

Welcome to The Coding College! In this tutorial, we’ll explore stacks in C++, a fundamental data structure provided by the Standard Template Library (STL). Stacks are widely used in applications such as parsing, backtracking, and expression evaluation.

What Is a Stack?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed.

Key Characteristics of Stacks:

  • Push: Add an element to the top of the stack.
  • Pop: Remove the top element from the stack.
  • Top/Peek: View the top element without removing it.

Declaring a Stack

To use stacks in C++, include the <stack> header.

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

int main() {
    stack<int> myStack; // Declare a stack of integers

    return 0;
}

Common Operations

1. Push Elements

The push function adds an element to the top of the stack.

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

int main() {
    stack<int> myStack;

    myStack.push(10); // Add 10
    myStack.push(20); // Add 20
    myStack.push(30); // Add 30

    cout << "Top element: " << myStack.top() << endl; // View top element

    return 0;
}

Output:

Top element: 30

2. Pop Elements

The pop function removes the top element from the stack.

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

int main() {
    stack<int> myStack = {};  

    myStack.push(10);
    myStack.push(20);

    myStack.pop(); // Remove the top element (20)

    cout << "Top element after pop: " << myStack.top() << endl;

    return 0;
}

Output:

Top element after pop: 10

3. Check Size

Use the size function to get the number of elements in the stack.

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

int main() {
    stack<int> myStack;

    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    cout << "Stack size: " << myStack.size() << endl;

    return 0;
}

Output:

Stack size: 3

4. Check if Stack Is Empty

The empty function checks whether the stack contains any elements.

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

int main() {
    stack<int> myStack;

    if (myStack.empty()) {
        cout << "The stack is empty!" << endl;
    }

    myStack.push(10);

    if (!myStack.empty()) {
        cout << "The stack is not empty!" << endl;
    }

    return 0;
}

Output:

The stack is empty!  
The stack is not empty!

Iterating Over a Stack

Since stacks do not provide direct iterators, you must manually pop elements if you want to iterate over them.

Example: Print All Elements

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

int main() {
    stack<int> myStack;

    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    while (!myStack.empty()) {
        cout << myStack.top() << " "; // Print top element
        myStack.pop();                // Remove top element
    }

    return 0;
}

Output:

30 20 10

Applications of Stacks

  1. Expression Evaluation and Parsing: Converting infix to postfix or evaluating postfix expressions.
  2. Backtracking: Solving problems like the maze or the N-Queens problem.
  3. Undo Mechanisms: Implementing undo/redo functionality in text editors.
  4. Function Call Management: Managing function calls using a call stack.

Real-World Example: Reverse a String Using a Stack

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

int main() {
    string str = "Hello";
    stack<char> charStack;

    // Push each character onto the stack
    for (char c : str) {
        charStack.push(c);
    }

    // Pop characters to reverse the string
    string reversedStr;
    while (!charStack.empty()) {
        reversedStr += charStack.top();
        charStack.pop();
    }

    cout << "Original String: " << str << endl;
    cout << "Reversed String: " << reversedStr << endl;

    return 0;
}

Output:

Original String: Hello  
Reversed String: olleH

Summary

  • Advantages: Simple and efficient for LIFO operations.
  • Common Methods: push, pop, top, size, and empty.
  • Use Cases: Expression parsing, backtracking, and undo mechanisms.

Learn More at The Coding College

For more tutorials on C++ and data structures, visit The Coding College.

Leave a Comment