Write code to implement a stack using arrays.

Implementing a Stack Using Arrays in Python

Stacks are a fundamental data structure in computer science. They follow the Last-In, First-Out (LIFO) principle, like a stack of plates: you can only add or remove plates from the top. Arrays provide a simple and efficient way to implement stacks. This blog post will show you how to create a stack using arrays in Python.

Core Concepts

Stack Operations

The essential operations for a stack are:

• Push: Adds an element to the top of the stack.
• Pop: Removes and returns the element at the top of the stack.
• Peek (or Top): Returns the element at the top without removing it.
• isEmpty: Checks if the stack is empty.
• isFull: Checks if the stack is full (relevant for fixed-size arrays).

Array Representation

We'll use a Python list as our array. A variable, top, will keep track of the index of the top element. When we push an item, we increment top; when we pop, we decrement it. We need to handle potential errors: stack overflow (trying to push onto a full stack) and stack underflow (trying to pop from an empty stack).

Code Implementation

Stack Class

class Stack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.arr = [None] * capacity  # Initialize array
        self.top = -1  # Initially empty

    def push(self, item):
        if self.isFull():
            raise Exception("Stack Overflow!")
        self.top += 1
        self.arr[self.top] = item

    def pop(self):
        if self.isEmpty():
            raise Exception("Stack Underflow!")
        item = self.arr[self.top]
        self.top -= 1
        return item

    def peek(self):
        if self.isEmpty():
            raise Exception("Stack is empty!")
        return self.arr[self.top]

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

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

Method Explanations

The push method adds an element, raising an exception if the stack is full. pop removes and returns the top element, raising an exception if the stack is empty. peek returns the top element without removing it, while isEmpty and isFull check the stack's state.

Example Usage

stack = Stack(5)  # Create a stack with capacity 5
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop())  # Output: 30
print(stack.peek()) # Output: 20
print(stack.isEmpty()) # Output: False

Handling Stack Overflow and Underflow

As shown above, we've handled stack overflow and underflow by raising exceptions. This is a common and clean way to signal errors in Python.

Advantages and Disadvantages

Advantages

Using arrays for stack implementation is simple and provides direct memory access, leading to efficient push and pop operations.

Disadvantages

The main disadvantage is the fixed size. A stack implemented with an array can overflow. Dynamic arrays (which resize automatically) or linked lists can address this limitation.

Conclusion

We successfully implemented a stack using arrays in Python. We covered the core operations, handled potential errors, and discussed the advantages and disadvantages of this approach. Further exploration could include implementing a stack with a dynamic array or comparing array-based stacks with linked-list-based stacks.