Lesson 1
Exploring Stacks in C++ with the Standard Template Library
Introduction

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?

Understanding Stack: A Data Structure on the Rise

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.

Utilizing Stack in C++

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++
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.

Advanced Stack Operations

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++
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}
Practical Stack Applications: Reversing a String

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++
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}
Practical Stack Applications: Checking Balance of Parentheses

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++
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}
Lesson Summary and Steps Ahead

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++!

Enjoy this lesson? Now it's time to practice with Cosmo!
Practice is how you turn knowledge into actual skills.