C++ Stacks

Stacks are a fundamental data structure in programming, and C++ makes working with them straightforward and efficient. Whether you're new to programming or just brushing up on your skills, stacks are a concept you’ll encounter in many applications. Let’s break it all down step by step.

What Is a Stack?

At its core, a stack is a collection of elements organized in a Last In, First Out (LIFO) order. This means the last item added to the stack is the first one to be removed. Think of a stack as a pile of plates—you add plates on top and take them off from the top. It’s that simple.

Stacks are used everywhere in computing, from managing function calls in recursion to evaluating mathematical expressions. In C++, stacks are available as part of the Standard Template Library (STL), making them versatile and easy to use.

Why Use Stacks?

Stacks are particularly handy when you need to manage tasks in a specific sequence. Here are some key use cases:

Undo functionality in text editors, where the most recent action is reversed first.
Backtracking algorithms, such as navigating a maze.
Expression evaluation, especially with postfix or prefix notations.
Function calls in programming, as they use the call stack to remember where each function should return.

By understanding stacks, you can solve a range of these problems efficiently.

How to Work With Stacks in C++

The STL in C++ provides a stack container. It’s built on top of other containers, usually deque or vector, which store the stack’s elements. Let’s look at how to use it.

Including the Required Library

To use a stack, include the header file:

#include <stack>

Creating a Stack

Creating a stack in C++ is simple. Just declare it with the type of data you want it to store:

std::stack<int> myStack; // Stack of integers
std::stack<std::string> myStringStack; // Stack of strings

Basic Operations

Stacks support a few key operations:

push(): Adds an element to the top of the stack.
pop(): Removes the top element.
top(): Returns the top element.
empty(): Checks if the stack is empty.
size(): Returns the number of elements in the stack.

Here’s a simple example:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> myStack;

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

    std::cout << "Top element: " << myStack.top() << std::endl; // Outputs 30

    myStack.pop(); // Remove the top element
    std::cout << "Top element after pop: " << myStack.top() << std::endl; // Outputs 20

    return 0;
}

Checking If a Stack Is Empty

Before calling pop() or top(), it’s good practice to check if the stack is empty using empty().

if (!myStack.empty()) {
    std::cout << "Top element: " << myStack.top() << std::endl;
}

Real-World Example: Reversing a String

Here’s how you can use a stack to reverse a string:

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::string input = "hello";
    std::stack<char> charStack;

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

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

    std::cout << "Reversed string: " << reversed << std::endl; // Outputs "olleh"

    return 0;
}

Common Mistakes and Tips

Here are a few things to keep in mind when working with stacks:

Avoid popping from an empty stack: This leads to undefined behavior. Always check with empty().
Remember, stacks don’t have random access. You can only access the top element.
Use the right data structure. While stacks are great for LIFO tasks, they’re not the best choice when you need to access elements in the middle.

A Practical Example: Checking Balanced Parentheses

Stacks are often used to validate strings, like checking if parentheses are balanced.

#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string& s) {
    std::stack<char> parentheses;

    for (char c : s) {
        if (c == '(') {
            parentheses.push(c); // Push opening parentheses
        } else if (c == ')') {
            if (parentheses.empty() || parentheses.top() != '(') {
                return false; // Unbalanced
            }
            parentheses.pop(); // Remove matching opening parenthesis
        }
    }

    return parentheses.empty(); // If empty, parentheses are balanced
}

int main() {
    std::string test = "(())";
    if (isBalanced(test)) {
        std::cout << "Parentheses are balanced." << std::endl;
    } else {
        std::cout << "Parentheses are not balanced." << std::endl;
    }

    return 0;
}

Advanced: Customizing Stacks

Although the default stack container uses deque under the hood, you can specify a different container if needed. For example, you can use a vector:

#include <stack>
#include <vector>

std::stack<int, std::vector<int>> customStack;
customStack.push(5);

This level of flexibility lets you optimize performance for your specific use case.

Conclusion

Stacks are a powerful and simple tool that every C++ programmer should know. They’re ideal for tasks where you need to process data in reverse order or follow a specific sequence. With STL, using stacks in C++ is both intuitive and efficient.

Start experimenting with different scenarios, like solving puzzles or implementing undo functionality. By practicing, you’ll gain a deeper understanding of how stacks can make your programs more effective.