Stacks | Data Structures | Cplusplus Tutorial

Introduction to Stacks

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means the last element added to the stack will be the first one to be removed. Stacks are used in various applications such as expression evaluation, backtracking algorithms, and memory management.

Basic Operations

The basic operations that can be performed on a stack are:

Push: Adding an element to the top of the stack.
Pop: Removing the top element of the stack.
Peek/Top: Viewing the top element without removing it.
isEmpty: Checking if the stack is empty.

Implementing a Stack in C++

We can implement a stack in C++ using arrays or linked lists. Below is an example of a stack implementation using an array.

#include <iostream>
#define MAX 1000

class Stack {
    int top;
public:
    int a[MAX];    // Maximum size of Stack

    Stack() { top = -1; }
    bool push(int x);
    int pop();
    int peek();
    bool isEmpty();
};

bool Stack::push(int x) {
    if (top >= (MAX - 1)) {
        std::cout << "Stack Overflow";
        return false;
    }
    else {
        a[++top] = x;
        std::cout << x << " pushed into stack\n";
        return true;
    }
}

int Stack::pop() {
    if (top < 0) {
        std::cout << "Stack Underflow";
        return 0;
    }
    else {
        int x = a[top--];
        return x;
    }
}

int Stack::peek() {
    if (top < 0) {
        std::cout << "Stack is Empty";
        return 0;
    }
    else {
        int x = a[top];
        return x;
    }
}

bool Stack::isEmpty() {
    return (top < 0);
}

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    std::cout << s.pop() << " Popped from stack\n";
    return 0;
}

In this example, we define a class Stack with a maximum size of 1000. We implement the basic stack operations: push, pop, peek, and isEmpty.

Push Operation

The push operation adds an element to the top of the stack. If the stack is full, it results in a stack overflow.

bool Stack::push(int x) {
    if (top >= (MAX - 1)) {
        std::cout << "Stack Overflow";
        return false;
    } else {
        a[++top] = x;
        std::cout << x << " pushed into stack\n";
        return true;
    }
}

Pop Operation

The pop operation removes and returns the top element from the stack. If the stack is empty, it results in a stack underflow.

int Stack::pop() {
    if (top < 0) {
        std::cout << "Stack Underflow";
        return 0;
    } else {
        int x = a[top--];
        return x;
    }
}

Peek Operation

The peek operation returns the top element without removing it from the stack.

int Stack::peek() {
    if (top < 0) {
        std::cout << "Stack is Empty";
        return 0;
    } else {
        int x = a[top];
        return x;
    }
}

isEmpty Operation

The isEmpty operation checks if the stack is empty or not.

bool Stack::isEmpty() {
    return (top < 0);
}

Example Usage

Here is an example of how to use the stack class:

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    std::cout << s.pop() << " Popped from stack\n";
    return 0;
}

This will output:

30 Popped from stack

Applications of Stacks

Stacks can be used in various applications, including:

Expression Evaluation: Stacks are used to evaluate postfix and prefix expressions.
Backtracking: Stacks are used in algorithms like maze solving, parsing, and searching.
Memory Management: Stacks are used to keep track of function calls and local variables in programming languages.
Undo Mechanisms: Many software applications use stacks to implement undo features.

Conclusion

Stacks are a fundamental data structure that is widely used in computer science and programming. Understanding how to implement and use stacks is essential for solving various computational problems efficiently.

Stacks in Data Structures - C++ Language