What is a Stack❓

A stack is a fundamental data structure used in computer science and programming. It follows the Last-In-First-Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. Stacks are widely used in various applications, including algorithms, parsing expressions, memory management, and more.

• It is Non-primitive Linear Data Structure.

It  has below common operations:

• Push: Adding an element to the top of the stack.
• Pop: Removing the top element from the stack.
• Peek/Top: Retrieving the top element without removing it.

Stack is used in various application such as reversing a word, backtracking algorithms and in the implementation of functions calls in recursion.

Implementation

It can be implemented with both arrays and linked list.

1️⃣ Array-Based Implementation:

In an array-based stack:

• A fixed-size array is used to store elements.
• A variable (top) tracks the index of the last added element.
• The stack has a maximum size, and we check for overflow when trying to push an element.

#include <iostream>
using namespace std;

#define MAX 1000

class Stack {
    int top;
    int arr[MAX]; // Maximum size of Stack

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

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

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

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

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

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

2️⃣ Linked List-Based Implementation:

In a linked list-based stack:

• A dynamic linked list is used where each node points to the next node.
• The top pointer points to the most recently added element (the head of the list).
• This allows the stack to grow and shrink dynamically without a predefined size.

#include <iostream>
using namespace std;

class StackNode {
public:
    int data;
    StackNode* next;
};

StackNode* newNode(int data) {
    StackNode* stackNode = new StackNode();
    stackNode->data = data;
    stackNode->next = nullptr;
    return stackNode;
}

bool isEmpty(StackNode* root) {
    return !root;
}

void push(StackNode** root, int data) {
    StackNode* stackNode = newNode(data);
    stackNode->next = *root;
    *root = stackNode;
    cout << data << " pushed to stack\n";
}

int pop(StackNode** root) {
    if (isEmpty(*root))
        return -1;
    StackNode* temp = *root;
    *root = (*root)->next;
    int popped = temp->data;
    delete temp;

    return popped;
}

int peek(StackNode* root) {
    if (isEmpty(root))
        return -1;
    return root->data;
}

int main() {
    StackNode* root = nullptr;
    push(&root, 10);
    push(&root, 20);
    push(&root, 30);
    cout << pop(&root) << " popped from stack\n";
    return 0;
}