Understanding Stacks

What is a Stack?

A stack is an abstract data type that serves as a collection of elements with two main operations: push and pop. It operates on the Last In, First Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed.

Visualizing a Stack

Imagine a stack of plates. You can only add or remove the top plate:

Top (Push/Pop)
-------------
| Plate 3   |
-------------
| Plate 2   |
-------------
| Plate 1   |
-------------
Bottom

You can see that when you add (push) the next plate, it goes on top of the last plate you stacked, and when you remove (pop) a plate, you can only take the one on top.

How Does an Array-Based Stack Work?

An array-based stack utilizes an array to store its elements. This implementation is straightforward, where the last index points to the top element of the stack.

Key Operations of Stacks

1. Push: Add an element to the top of the stack.
2. Pop: Remove the top element from the stack.
3. Peek: View the top element of the stack without removing it.
4. Is Empty: Check whether the stack is empty.
5. Size: Return the number of elements in the stack.

Example of Stack Operations

Let's implement a stack using an array in Python and demonstrate its operations:

class Stack:
    def __init__(self, capacity):
        self.stack = [None] * capacity
        self.top = -1
        self.capacity = capacity

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == self.capacity - 1

    def push(self, item):
        if self.is_full():
            print("Stack is full.")
            return
        self.top += 1
        self.stack[self.top] = item
        print(f"Pushed {item} to stack.")

    def pop(self):
        if self.is_empty():
            print("Stack is empty.")
            return None
        item = self.stack[self.top]
        self.stack[self.top] = None
        self.top -= 1
        print(f"Popped {item} from stack.")
        return item

    def peek(self):
        if self.is_empty():
            print("Stack is empty.")
            return None
        return self.stack[self.top]

    def size(self):
        return self.top + 1

# Example usage
stack = Stack(5)
stack.push(1)
stack.push(2)
stack.push(3)
print(f"Top item is: {stack.peek()}")
stack.pop()
print(f"Stack size is: {stack.size()}")

Explanation of the Code

• Initialization: The Stack class initializes with a fixed capacity and an array to hold elements. The top index starts at -1, indicating the stack is empty.

• Push Method: This method checks if the stack is full before adding a new item. If it’s full, an error message is printed; otherwise, the new item is placed at the top index, and the index is incremented.

• Pop Method: It checks whether the stack is empty before attempting to remove the top item. If the stack is empty, it returns an informative message; otherwise, it retrieves the top element, sets it to None, and decrements the top index.

• Peek Method: Similar to pop, but it only retrieves the top item without removing it from the stack, allowing you to check which item is currently on top.

• Size Method: Returns the current number of elements on the stack by simply returning the index of the top element plus one.

When to Use Stacks?

Stacks are incredibly useful in several scenarios, including:

• Function Calls: The call stack keeps track of function calls in programming languages.
• Expression Evaluation: They are used in parsing expressions, particularly in converting infix expressions to postfix.
• Backtracking Algorithms: Stacks are used in algorithms that backtrack, such as solving mazes or puzzles.

By employing the stack data structure correctly, you can solve complex problems efficiently and maintain optimal resource management in your applications.