Stacks (Linked Lists and Array Implementations)

Stacks (Linked Lists and Array Implementations)

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means that the last element added to the stack is the first one to be removed. It’s like a stack of plates: you can only take the top plate off first before accessing the others underneath.

There are two common ways to implement a stack:

1. Using arrays.
2. Using linked lists.

Both implementations provide similar functionality but have different underlying structures and performance characteristics.

Basic Operations of a Stack

A stack supports the following fundamental operations:

• push(x): Add an element x to the top of the stack.
• pop(): Remove and return the element from the top of the stack.
• peek() or top(): Return the top element of the stack without removing it.
• isEmpty(): Check if the stack is empty.

1. Stack Implementation Using Arrays

In this implementation, an array is used to store the stack’s elements, and a variable (often called top) keeps track of the index of the last element added to the stack.

Array Stack Pros and Cons:

• Pros:
  • Simple and easy to implement.
  • Random access is fast (you can directly access elements by index).
• Cons:
  • Fixed size: You need to specify the size of the array beforehand. If you try to add more elements than the array can hold, it may result in a stack overflow.

C++ Array Stack Implementation:

#include <iostream>
using namespace std;

class Stack {
private:
    int top;
    int maxSize;
    int *arr;

public:
    // Constructor to initialize the stack with a fixed size
    Stack(int size) {
        maxSize = size;
        arr = new int[maxSize];
        top = -1;  // Stack is initially empty
    }

    // Push operation to add an element to the stack
    void push(int x) {
        if (top == maxSize - 1) {
            cout << "Stack Overflow\n";
            return;
        }
        arr[++top] = x;
    }

    // Pop operation to remove the top element from the stack
    int pop() {
        if (top == -1) {
            cout << "Stack Underflow\n";
            return -1;
        }
        return arr[top--];
    }

    // Peek operation to view the top element
    int peek() {
        if (top == -1) {
            cout << "Stack is empty\n";
            return -1;
        }
        return arr[top];
    }

    // Check if the stack is empty
    bool isEmpty() {
        return top == -1;
    }

    // Destructor to clean up dynamically allocated memory
    ~Stack() {
        delete[] arr;
    }
};

int main() {
    Stack stack(5);

    stack.push(10);
    stack.push(20);
    stack.push(30);

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

    cout << "Popped element: " << stack.pop() << endl; // Output: 30
    cout << "Popped element: " << stack.pop() << endl; // Output: 20

    cout << "Is stack empty? " << (stack.isEmpty() ? "Yes" : "No") << endl; // Output: No

    return 0;
}

Key Points:

• The push function increments the top index and places the new element there.
• The pop function decrements the top index to remove the top element.
• The array has a fixed size (maxSize), so we must handle overflow when the stack is full.

2. Stack Implementation Using Linked Lists

In this implementation, a stack is built using a linked list, where each node contains a value and a pointer to the next node. The top of the stack is represented by the head of the linked list.

Linked List Stack Pros and Cons:

• Pros:
  • Dynamic size: The stack can grow or shrink as needed without any fixed size limitation.
  • No overflow, as memory is allocated dynamically.
• Cons:
  • Slightly more complex to implement compared to arrays.
  • More memory overhead due to storing pointers along with the data.

C++ Linked List Stack Implementation:

#include <iostream>
using namespace std;

// Node structure to represent an element in the linked list
struct Node {
    int data;     // Stores the data of the stack element
    Node* next;   // Pointer to the next node in the stack
};

// Stack class definition
class Stack {
private:
    Node* top;  // Points to the top of the stack

public:
    // Constructor: Initializes the stack as empty
    Stack() {
        top = nullptr;
    }

    // Function to check if the stack is empty
    bool isEmpty() {
        return top == nullptr;
    }

    // Function to push an element onto the stack
    void push(int value) {
        Node* newNode = new Node();  // Create a new node
        newNode->data = value;       // Assign value to the node
        newNode->next = top;         // Link the new node to the current top
        top = newNode;               // Update the top to the new node
        cout << value << " pushed to stack\n";
    }

    // Function to pop an element from the stack
    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow: The stack is empty!\n";
            return -1;  // Return -1 if stack is empty
        }
        Node* temp = top;       // Temporarily store the top node
        int poppedValue = top->data;  // Store the value to be popped
        top = top->next;        // Update the top pointer to the next node
        delete temp;            // Delete the popped node
        cout << poppedValue << " popped from stack\n";
        return poppedValue;
    }

    // Function to peek the top element without removing it
    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty\n";
            return -1;  // Return -1 if stack is empty
        }
        return top->data;  // Return the data at the top
    }

    // Function to display the elements in the stack
    void display() {
        if (isEmpty()) {
            cout << "Stack is empty\n";
            return;
        }
        Node* temp = top;
        cout << "Stack elements: ";
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

    // Destructor: Clean up the memory
    ~Stack() {
        while (!isEmpty()) {
            pop();  // Pop all elements to delete them
        }
    }
};

int main() {
    Stack stack;

    stack.push(10);  // Push elements
    stack.push(20);
    stack.push(30);
    stack.push(40);

    stack.display();  // Display stack elements

    cout << "Top element is " << stack.peek() << endl;  // Peek the top element

    stack.pop();  // Pop an element
    stack.pop();  // Pop another element

    stack.display();  // Display stack after pops

    return 0;
}

Key Points:

• In the push function, a new node is created, and it becomes the new top of the stack.
• In the pop function, the current top node is removed, and the next node in the linked list becomes the new top.
• The stack can grow or shrink dynamically without worrying about overflow.

Array vs. Linked List Stack Comparison

When to Use Which Implementation?

• Array implementation: Use this when you know the maximum size of the stack in advance and want fast, constant-time access to elements.
• Linked list implementation: Use this when you don’t know the maximum size of the stack in advance and need a stack that grows dynamically without size limitations.

Conclusion

Both the array and linked list implementations of a stack have their own use cases and benefits. Arrays are simpler and more efficient for fixed-size stacks, while linked lists provide flexibility in size, making them ideal for scenarios where the stack size is unknown or fluctuates frequently.