C++ Stacks | DSA in C++ - Software Development PDF Download

Introduction

When it comes to organizing and manipulating data in computer programming, understanding data structures is essential. One commonly used data structure is the stack. In this article, we will explore the concept of stacks and their implementation in C++. We will cover the basic operations of a stack, provide code examples, explain their functionality, and conclude with some sample problems to reinforce your understanding.

What is a Stack?

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. In simple terms, it behaves like a stack of plates, where the last plate added is the first one to be removed. Stacks are used in a wide range of applications, such as expression evaluation, backtracking algorithms, and managing function calls in programming languages.

Basic Operations on a Stack

A stack typically supports the following fundamental operations:

• Push: Adds an element to the top of the stack.
• Pop: Removes the topmost element from the stack.
• Peek/Top: Retrieves the value of the top element without removing it.
• isEmpty: Checks if the stack is empty.
• Size: Returns the number of elements in the stack.

Implementing a Stack in C++

C++ provides several ways to implement a stack, such as using an array or linked list. In this article, we will focus on implementing a stack using an array, which is the most straightforward approach.

Code Examples and Explanation

Here's the implementation of a stack using an array in C++:

#include <iostream>

#define MAX_SIZE 100

class Stack {

private:

    int top;

    int data[MAX_SIZE];

public:

    Stack() {

        top = -1;

    }

    void push(int element) {

        if (top == MAX_SIZE - 1) {

            std::cout << "Stack Overflow! Cannot push element.\n";

            return;

        }

        data[++top] = element;

        std::cout << "Pushed element: " << element << std::endl;

    }

    void pop() {

        if (isEmpty()) {

            std::cout << "Stack Underflow! Cannot pop element.\n";

            return;

        }

        int element = data[top--];

        std::cout << "Popped element: " << element << std::endl;

    }

    int peek() {

        if (isEmpty()) {

            std::cout << "Stack is empty.\n";

            return -1;

        }

        return data[top];

    }

    bool isEmpty() {

        return (top == -1);

    }

    int size() {

        return (top + 1);

    }

};

int main() {

    Stack stack;

    stack.push(10);

    stack.push(20);

    stack.push(30);

    std::cout << "Size of the stack: " << stack.size() << std::endl;

    std::cout << "Top element: " << stack.peek() << std::endl;

    stack.pop();

    stack.pop();

    stack.pop();

    stack.pop();

    return 0;

}

Explanation:

• We define a 'Stack' class that encapsulates the stack data structure.
• The class has a private member 'data' of size 'MAX_SIZE' to store the stack elements and 'top' to keep track of the topmost element.
• The 'push' function checks for stack overflow and adds an element to the top of the stack.
• The 'pop' function checks for stack underflow and removes the topmost element from the stack.
• The 'peek' function returns the value of the top element without removing it.
• The 'isEmpty' function checks if the stack is empty.
• The 'size' function returns the number of elements in the stack.
• In the 'main' function, we create a 'Stack' object, push elements onto the stack, and perform other operations such as popping elements, checking the size, and peeking the top element.

Output:

Pushed element: 10

Pushed element: 20

Pushed element: 30

Size of the stack: 3

Top element: 30

Popped element: 30

Popped element: 20

Popped element: 10

Stack Underflow! Cannot pop element.

Sample Problems and Solutions

Here are some sample problems to practice working with stacks:
Problem 1: Reverse a string using a stack.

#include <iostream>

#include <stack>

#include <string>

std::string reverseString(const std::string& input) {

    std::stack<char> stack;

    for (char ch : input)

        stack.push(ch);

    

    std::string reversed;

    while (!stack.empty()) {

        reversed += stack.top();

        stack.pop();

    }

    return reversed;

}

int main() {

    std::string input = "Hello, World!";

    std::string reversed = reverseString(input);

    std::cout << "Reversed string: " << reversed << std::endl;

    return 0;

}

Output:

Reversed string: !dlroW ,olleH

Problem 2: Check if parentheses in a string are balanced.

#include <iostream>

#include <stack>

#include <string>

bool isBalanced(const std::string& input) {

    std::stack<char> stack;

    for (char ch : input) {

        if (ch == '(' || ch == '[' || ch == '{')

            stack.push(ch);

        else if (ch == ')' || ch == ']' || ch == '}') {

            if (stack.empty())

                return false;

            char top = stack.top();

            if ((ch == ')' && top == '(') ||

                (ch == ']' && top == '[') ||

                (ch == '}' && top == '{'))

                stack.pop();

            else

                return false;

        }

    }

    return stack.empty();

}

int main() {

    std::string input1 = "((2 + 3) * [5 - 1])";

    std::string input2 = "((2 + 3) * [5 - 1]";

    

    if (isBalanced(input1))

        std::cout << "Parentheses are balanced in input1.\n";

    else

        std::cout << "Parentheses are not balanced in input1.\n";

    

    if (isBalanced(input2))

        std::cout << "Parentheses are balanced in input2.\n";

    else

        std::cout << "Parentheses are not balanced in input2.\n";

    

    return 0;

}

Output:

Parentheses are balanced in input1.

Parentheses are not balanced in input2.

Conclusion

In this article, we covered the fundamentals of stacks, their basic operations, and their implementation in C++. We provided code examples with explanations and discussed the output for each example. Understanding stacks is crucial as they serve as a foundation for more complex data structures and algorithms. By practicing with sample problems, you can solidify your knowledge and gain confidence in working with stacks. Keep exploring and applying this knowledge to solve various programming challenges efficiently.