Stack C++

A stack is an abstract data type (ADT) that follows the Last In, First Out (LIFO) principle. It is a collection of elements with two primary operations: push and pop. Elements can only be inserted (pushed) and removed (popped) from the top of the stack. The element added last will be the first one to be removed.

A real-life analogy for a stack is a stack of plates, where you can only add or remove plates from the top of the stack.

Key Characteristics of a Stack

1. Push Operation: Adds an element to the top of the stack.
2. Pop Operation: Removes the top element from the stack.
3. Peek (or Top) Operation: Retrieves the top element without removing it.
4. IsEmpty Operation: Checks if the stack is empty or not.
5. Size Operation: Returns the number of elements in the stack.

Use of Stacks

• Function Call Management: Used for storing function call information (return addresses, local variables, etc.) in memory during program execution.
• Expression Evaluation: Used in programming languages to evaluate expressions, especially mathematical expressions, using postfix notation (Reverse Polish Notation, RPN).
• Backtracking Algorithms: Used in backtracking algorithms to store the states that need to be explored further.
• Memory Management: Used in memory management for storing temporary data, registers, and other information.

Implementation of Stack

Stacks can be implemented using arrays or linked lists. The choice of implementation depends on the requirements of the application.

Array-based Stack

• An array-based stack uses an array to store elements. The stack pointer points to the topmost element, and elements are added or removed by manipulating the stack pointer. The size of the array determines the maximum capacity of the stack.

Linked List-based Stack

• A linked list-based stack uses a linked list to store elements. Each node in the linked list contains the data and a reference/pointer to the next node.
• The top of the stack is represented by the head of the linked list.

Stack Using Array

#include <iostream>

const int MAX_SIZE = 100;

class Stack {
private:
    int arr[MAX_SIZE];
    int top;

public:
    Stack() {
        top = -1; // Initialize an empty stack
    }

    void push(int data) {
        if (top == MAX_SIZE - 1) {
            std::cout << "Stack overflow. Cannot push." << std::endl;
            return;
        }
        arr[++top] = data;
    }

    void pop() {
        if (isEmpty()) {
            std::cout << "Stack underflow. Cannot pop." << std::endl;
            return;
        }
        top--;
    }

    int peek() {
        if (isEmpty()) {
            std::cout << "Stack is empty. Cannot peek." << std::endl;
            return -1;
        }
        return arr[top];
    }

    bool isEmpty() {
        return top == -1;
    }
};

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);

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

    stack.pop();
    std::cout << "Top element after pop: " << stack.peek() << std::endl; // Output: 20

    return 0;
}

Stack Using Linked List

#include <iostream>

class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

class Stack {
private:
    Node* top;

public:
    Stack() {
        top = nullptr; // Initialize an empty stack
    }

    void push(int data) {
        Node* newNode = new Node(data);
        newNode->next = top;
        top = newNode;
    }

    void pop() {
        if (isEmpty()) {
            std::cout << "Stack underflow. Cannot pop." << std::endl;
            return;
        }
        Node* temp = top;
        top = top->next;
        delete temp;
    }

    int peek() {
        if (isEmpty()) {
            std::cout << "Stack is empty. Cannot peek." << std::endl;
            return -1;
        }
        return top->data;
    }

    bool isEmpty() {
        return top == nullptr;
    }
};

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);

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

    stack.pop();
    std::cout << "Top element after pop: " << stack.peek() << std::endl; // Output: 20

    return 0;
}

In both implementations, we have a Stack class with basic stack operations like push, pop, peek, and isEmpty. The array implementation has a fixed-size limitation, while the linked list implementation can dynamically grow as needed.

Stacks are widely used in computer science due to their simplicity, efficiency, and wide range of applications. Understanding stacks is crucial for various algorithms and data structure concepts.