Greetings! Today, we'll unveil the Stack data structure in C++, an essential part of your programming toolkit. A stack operates much like a stack of dishes: you place a new dish on top (Last In) and you remove the top dish (First Out). This Last-In, First-Out (LIFO) method illustrates the stack. In C++, we utilize the Standard Template Library (STL) stack to manage these operations with ease. This lesson will enlighten you about the stack data structure, various operations, and their practical applications in C++. Are you ready to dive in?

A stack is a structured storehouse that enables push (to add items) and pop (to remove items) operations. It's similar to a stack of plates in a cafeteria where plates are added (pushed) and removed (popped) only from the top, demonstrating a Last-In, First-Out (LIFO) operation.

To implement a stack, C++ offers a dedicated container known as stack in the STL. To add an element to the top of the stack, we employ the push() method. The pop() method, on the other hand, removes the top element, carrying out the removal process. Here’s a look at this operations in code:

C++
Copy to clipboard
1#include <iostream>
2#include <stack>
3
4int main() {
5    std::stack<std::string> stack; // A new empty stack
6
7    // Push operations
8    stack.push("John");
9    stack.push("Mary");
10    stack.push("Steve");
11
12    // Pop operation removes 'Steve'
13    stack.pop();
14    // The stack now contains 'John' and 'Mary'
15
16    return 0;
17}

In the example, 'John', 'Mary', and 'Steve' are pushed onto the stack, and 'Steve' is popped from the stack.

Stack operations extend beyond merely push and pop. To check if a stack is empty, you can use the empty() method. If it returns true, the stack is empty; otherwise, it contains elements. To view the top element without removing it, the top() method is handy.

Here's an example:

C++
Copy to clipboard
1#include <iostream>
2#include <stack>
3
4int main() {
5    std::stack<std::string> stack; // A new empty stack
6
7    // Push operations
8    stack.push("John");
9    stack.push("Mary");
10    stack.push("Steve");
11    stack.push("Sam");
12    std::cout << "Top element: " << stack.top() << std::endl; // Outputs: "Top element: Sam"
13    std::cout << "Is stack empty? " << stack.empty() << std::endl; // Outputs: "Is stack empty? false"
14
15    return 0;
16}

Stacks have numerous practical applications. One such application is reversing a string.

We will push all the characters into a stack and then pop them out to obtain a reversed string. Here’s how:

C++
Copy to clipboard
1#include <iostream>
2#include <stack>
3#include <string>
4
5std::string reverseString(const std::string& inputString) {
6    std::stack<char> stack;
7    for (char ch : inputString) {
8        stack.push(ch);
9    }
10
11    std::string reversedString;
12    while (!stack.empty()) {
13        reversedString += stack.top();
14        stack.pop();
15    }
16    return reversedString;
17}
18
19int main() {
20    std::cout << reverseString("HELLO") << std::endl; // Outputs: OLLEH
21    return 0;
22}

A stack is useful for verifying if parentheses in an expression are well-matched. For instance, parentheses in the string "()[{}]" are well-matched, while those in "([]()", ")()[]{}", "([)]", and "[{})" are not.

Let’s break down the solution:

Create a map to associate each closing bracket with its corresponding opening bracket, and initialize an empty stack. As you iterate through each character paren in parenString:

• If paren is an opening bracket, push it onto the stack.
• If paren is a closing bracket, check if the stack is empty or if the top element of the stack is not the corresponding opening bracket. If either condition is true, return false. Otherwise, pop the stack to remove the matched opening bracket.

After processing all characters, return true if the stack is empty, indicating all opening brackets were matched correctly. If the stack is not empty, return false, as unmatched brackets remain.

C++
Copy to clipboard
1#include <iostream>
2#include <stack>
3#include <unordered_map>
4
5bool isParenBalanced(const std::string& parenString) {
6    std::stack<char> stack;
7    std::unordered_map<char, char> openingParen = {{')', '('}, {']', '['}, {'}', '{'}};
8    
9    for (char paren : parenString) {
10        if (openingParen.find(paren) == openingParen.end()) {
11            // opening parenthesis
12            stack.push(paren);
13        } else {
14            // closing parenthesis
15            if (stack.empty() || stack.top() != openingParen[paren]) {
16                return false;
17            }
18            stack.pop();
19        }
20    }
21    return stack.empty();
22}
23
24int main() {
25    std::cout << std::boolalpha;
26    std::cout << isParenBalanced("(())") << std::endl; // Outputs: true
27    std::cout << isParenBalanced("({[)}") << std::endl; // Outputs: false
28    return 0;
29}

Congratulations! You've explored the stack data structure, operations, and their applications using C++. Your next challenge is to engage with practice exercises that will help solidify your newly acquired knowledge. Delve into these exercises and master stacks in C++!