Stack operation

A stack is a fundamental data structure that follows the Last In, First Out (LIFO) principle, meaning the most recently added item is the first one to be removed. It can be visualized as a stack of plates, where you can only add or remove the top plate. Stacks typically support two main operations:

• Push: This operation adds an element to the top of the stack.
• Pop: This operation removes the top element from the stack.

Additionally, some implementations may support other operations like peek (viewing the top element without removing it) and isEmpty (checking if the stack is empty).

Here's how a stack behaves:

• Push: Adds an item to the top of the stack. If the stack is empty, the new element becomes the top.
• Pop: Removes and returns the top item from the stack. If the stack is empty, an error may occur (underflow).
• Peek: Returns the top item from the stack without removing it.
• isEmpty: Checks if the stack is empty.

Real-world use cases for stacks include:

• Function Call Stack: In programming, when a function is called, its parameters and local variables are pushed onto the stack. When the function completes execution, the stack frame is popped, and control returns to the calling function.
• Undo Mechanism in Text Editors: Text editors often implement undo functionality using a stack. Each action (e.g., typing, deleting) is pushed onto the stack, allowing users to undo their actions by popping them off the stack in reverse order.
• Backtracking Algorithms: Algorithms like depth-first search (DFS) and backtracking use stacks to keep track of visited nodes or states. When exploring a path, the current state is pushed onto the stack, and if it doesn't lead to a solution, it pops off, and another path is explored.
• Expression Evaluation: In compilers and interpreters, stacks are used to evaluate expressions, especially infix expressions converted to postfix or prefix notation. Operators and operands are pushed and popped from the stack based on precedence and associativity rules.
• Browser History: The back and forward buttons in web browsers use stacks to keep track of the pages visited. Each time a user navigates to a new page, the URL is pushed onto the stack, allowing them to navigate back through their history by popping URLs off the stack.
• Parenthesis Matching: Stacks are used to check the validity of expressions containing parentheses, braces, and brackets. As opening and closing symbols are encountered, they are pushed onto the stack, and if a closing symbol matches the top of the stack, it is popped off.

Working of stack data structure

Initialization:

• When initializing the stack, a pointer called TOP is used to keep track of the top element in the stack.
• The initial value of TOP is set to -1 so that we can check if the stack is empty by comparing TOP == -1.
• Define Array of given SIZE

Push Operation:

• When pushing an element onto the stack:
• The value of TOP is increased by 1 to indicate the new top position.
• The new element is placed in the position pointed to by TOP.

Pop Operation:

• When popping an element from the stack:
• The element pointed to by TOP is returned.
• The value of TOP is decreased by 1 to indicate the new top position.

Overflow and Underflow:

• Before pushing an element, we check if the stack is already full to avoid overflow.
• Before popping an element, we check if the stack is already empty to avoid underflow.

The following diagram illustrate the working structure of STACK:

As in the above stack operation, Elements are popped in the reversed order of their insertion, hence called Last In First Out (LIFO) or First In Last Out (FILO) data structure.

Algorithm for Array Implementation of Stack

Algorithm: Array Stack Implementation

Data:
- stack: Array to store elements of the stack
- MAX_SIZE: Maximum capacity of the stack
- TOP: Pointer to keep track of the top element in the stack

Operations:
1. InitializeStack()
2. Push(element)
3. Pop()
4. Peek()
5. IsEmpty()
6. IsFull()

Algorithm:

1. InitializeStack():
    Set TOP = -1

2. Push(element):
    if IsFull():
        Print "Stack Overflow"
    else:
        Increment TOP
        stack[TOP] = element

3. Pop():
    if IsEmpty():
        Print "Stack Underflow"
    else:
        element = stack[TOP]
        Decrement TOP
        return element

4. Peek():
    if IsEmpty():
        Print "Stack is empty"
    else:
        return stack[TOP]

5. IsEmpty():
    return (TOP == -1)

6. IsFull():
    return (TOP == MAX_SIZE - 1)

Write C++ program to implement stack and its operations

#include <iostream>

#define MAX_SIZE 100 // Maximum capacity of the stack

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

public:
    Stack() {
        top = -1; // Initialize top to -1
    }

    void push(int element) {
        if (isFull()) {
            std::cout << "Stack Overflow\n";
        } else {
            top++;
            stack[top] = element;
        }
    }

    int pop() {
        if (isEmpty()) {
            std::cout << "Stack Underflow\n";
            return -1; // Return some default value or throw an exception
        } else {
            int element = stack[top];
            top--;
            return element;
        }
    }

    int peek() {
        if (isEmpty()) {
            std::cout << "Stack is empty\n";
            return -1; // Return some default value or throw an exception
        } else {
            return stack[top];
        }
    }

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

    bool isFull() {
        return (top == MAX_SIZE - 1);
    }
};

int main() {
    Stack stack;

    // Pushing elements onto the stack
    stack.push(10);
    stack.push(20);
    stack.push(30);

    // Popping elements from the stack
    std::cout << "Popped: " << stack.pop() << std::endl;
    std::cout << "Popped: " << stack.pop() << std::endl;

    // Peeking the top element
    std::cout << "Top element: " << stack.peek() << std::endl;

    return 0;
}