Stack Implementation using Array

Welcome to this comprehensive guide on implementing a Stack using an Array! By the end of this lesson, you'll have a solid understanding of stacks, their importance, and how to build one using an array. Let's dive right in!

🎯 Introduction

A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Think of it as a stack of plates in a cafeteria - the last plate added to the top is the first one to be removed. This property makes stacks useful for managing function calls, evaluating postfix expressions, and more!

📝 Understanding the Array

An Array is a collection of elements, each identified by an index. In our case, we'll use an Array to create a Stack.

💡 Pro Tip:

Arrays are dynamic and can grow or shrink in size as needed. However, for a Stack, we'll focus on a fixed-size Array to keep things simple.

🎯 Implementing a Basic Stack

Here's a simple implementation of a Stack using an Array:

python

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

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

    def push(self, item):
        if self.top < len(self.stack) - 1:
            self.top += 1
            self.stack[self.top] = item
        else:
            print("Stack Overflow!")

    def pop(self):
        if not self.is_empty():
            return self.stack[self.top]
        else:
            print("Stack Underflow!")

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

    def size(self):
        return len(self.stack)

# Creating a Stack with a size of 5
my_stack = Stack(5)

# Testing the Stack
my_stack.push(1)
my_stack.push(2)
my_stack.push(3)
my_stack.push(4)

print(my_stack.peek())  # Output: 4
print(my_stack.pop())    # Output: 4
print(my_stack.peek())   # Output: 3

📝 Note:

In the code above, we've defined a Stack class with methods like push, pop, peek, and is_empty. We've also created a stack object and tested its functionality.

🎯 Advanced Example

Let's use our Stack to implement a simple postfix calculator:

python

def evaluate_postfix(postfix_expression):
    operators = {'+': lambda x, y: x + y,
                  '-': lambda x, y: x - y,
                  '*': lambda x, y: x * y,
                  '/': lambda x, y: x / y}

    stack = Stack(len(postfix_expression))

    for token in postfix_expression:
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            result = operators[token](a, b)
            stack.push(result)
        else:
            stack.push(int(token))

    return stack.pop()

# Testing the postfix calculator
print(evaluate_postfix("2 3 +"))  # Output: 5
print(evaluate_postfix("7 6 * 4 +"))  # Output: 44
print(evaluate_postfix("10 5 / 3 * +"))  # Output: 20

That's it for this lesson! You've learned how to implement a Stack using an Array. In future lessons, we'll explore other data structures and algorithms. Keep up the great learning! 🚀🌟

Next Lesson: Queue Implementation using Array

Previously: Introduction to Data Structures and Algorithms