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;
}

Another One:

#include <bits/stdc++.h>
using namespace std;

class ArrayStack {
private:
    // Array to hold elements
    int* stackArray;
    // Maximum capacity
    int capacity; 
     // Index of top element  
    int topIndex;   

public:
    // Constructor
    ArrayStack(int size = 1000) {
        capacity = size;
        stackArray = new int[capacity];
        // Initialize stack as empty
        topIndex = -1; 
    }

    // Destructor
    ~ArrayStack() {
        delete[] stackArray;
    }

    // Pushes element x 
    void push(int x) {
        if (topIndex >= capacity - 1) {
            cout << "Stack overflow" << endl;
            return;
        }
        stackArray[++topIndex] = x;
    }

    // Removes and returns top element
    int pop() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            // Return invalid value
            return -1; 
        }
        return stackArray[topIndex--];
    }

    // Returns top element
    int top() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return -1; 
        }
        return stackArray[topIndex];
    }

   /* Returns true if the 
   stack is empty, false otherwise*/
    bool isEmpty() {
        return topIndex == -1;
    }
};

// Main Function
int main() {
    ArrayStack stack;
    vector<string> commands = {"ArrayStack", "push", "push", "top", "pop", "isEmpty"};
    vector<vector<int>> inputs = {{}, {5}, {10}, {}, {}, {}};

    for (size_t i = 0; i < commands.size(); ++i) {
        if (commands[i] == "push") {
            stack.push(inputs[i][0]);
            cout << "null ";
        } else if (commands[i] == "pop") {
            cout << stack.pop() << " ";
        } else if (commands[i] == "top") {
            cout << stack.top() << " ";
        } else if (commands[i] == "isEmpty") {
            cout << (stack.isEmpty() ? "true" : "false") << " ";
        } else if (commands[i] == "ArrayStack") {
            cout << "null ";
        }
    }

    return 0;
}

Complexity Analysis:

• Time Complexity:O(1) because the individual stack operations take O(1).
• Space Complexity:O(N) for using a stack which is equivalent to the size of the array.

2️⃣ Linked List-Based Implementation:

Intuition:

Implementing a stack using a linked list offers several advantages over using an array. Linked lists provide dynamic size flexibility, allowing the stack to grow and shrink as needed without worrying about predefined capacity or memory wastage. Each node in the linked list contains data and a reference to the next node, enabling efficient constant-time operations for both push and pop. This eliminates the risk of stack overflow and avoids the need for costly resizing operations, making linked lists an ideal choice for managing the dynamic nature of stack operations.

Approaching the problem of implementing a stack using a linked list can be likened to managing the stack of plates in the cafeteria example. Each plate represents a node in the linked list, and the top plate corresponds to the top node. To add a plate (push operation), a new node is created and placed on top of the stack, pointing to the previous top node. To remove a plate (pop operation), the top node is removed, and the next node in line becomes the new top. This dynamic linking and unlinking process allows the stack to grow and shrink efficiently, without any predefined capacity, just as the stack of plates can adjust to the number of plates being added or taken away.

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;
}

Other Way:

#include <bits/stdc++.h>
using namespace std;

// Node structure
struct Node {
    int val;
    Node *next;
    Node(int d) {
        val = d;
        next = NULL;
    }
};

// Structure to represent stack
class LinkedListStack {
private:
    Node *head; // Top of Stack
    int size; // Size

public:
    // Constructor
    LinkedListStack() {
        head = NULL;
        size = 0;
    }

    // Method to push an element onto the stack
    void push(int x) {
        // Creating a node 
        Node *element = new Node(x);
        
        element->next = head; // Updating the pointers
        head = element; // Updating the top
        
        // Increment size by 1
        size++;
    }

    // Method to pop an element from the stack
    int pop() {
        // If the stack is empty
        if (head == NULL) {
            return -1; // Pop operation cannot be performed
        }
        
        int value = head->val; // Get the top value
        Node *temp = head; // Store the top temporarily
        head = head->next; // Update top to next node
        delete temp; // Delete old top node
        size--; // Decrement size
        
        return value; // Return data
    }
    
    // Method to get the top element of the stack
    int top() {
        // If the stack is empty
        if (head == NULL) {
            return -1; // Top element cannot be accessed
        }
        
        return head->val; // Return the top
    }

    // Method to check if the stack is empty
    bool isEmpty() {
        return (size == 0);
    }
};

int main() {
    // Creating a stack
    LinkedListStack st;

    // List of commands
    vector<string> commands = {"LinkedListStack", "push", "push", 
                               "pop", "top", "isEmpty"};
    // List of inputs
    vector<vector<int>> inputs = {{}, {3}, {7}, {}, {}, {}};

    for (int i = 0; i < commands.size(); ++i) {
        if (commands[i] == "push") {
            st.push(inputs[i][0]);
            cout << "null ";
        } else if (commands[i] == "pop") {
            cout << st.pop() << " ";
        } else if (commands[i] == "top") {
            cout << st.top() << " ";
        } else if (commands[i] == "isEmpty") {
            cout << (st.isEmpty() ? "true" : "false") << " ";
        } else if (commands[i] == "LinkedListStack") {
            cout << "null ";
        }
    }

    return 0;
}

Complexity Analysis:

• Time Complexity:O(1) for push, pop, size, isEmpty, peek operations.
• Space Complexity:O(N) because the stack requires space proportional to the number of elements it stores.