Implement Stack Using Array | GFG Practice | Complete Guide in Python

You need to implement a stack using an array (Python list works as an array here). The stack should support two main operations:

• Push(x): Insert element x on top of the stack.
• Pop(): Remove and return the top element of the stack. If the stack is empty, return -1.

Here’s the [Problem Link] to begin with.

What is a Stack?

• A stack is a simple data structure that works on LIFO (Last In, First Out) principle.
• That means: the last item that was added (pushed) is the first item to be removed (popped).

Think of a stack like a pile of books: you add (push) books on top and remove (pop) books from the top only.

Approach and Intuition

• We’ll use a Python list (self.arr) as the internal storage for the stack.
• push(data):
  • Add the given data at the end of the list (top of the stack).
• pop():
  • Remove and return the last element from the list (top of the stack).
  • If the list (our stack) is empty, return -1 (as per the problem!).

Why use list’s .append() and .pop()?

• append() adds element at the end → top of stack.
• pop() removes and returns the last element → top of stack.

Step-By-Step Explanation with Code

class MyStack:
    def __init__(self):
        # Create an empty list to represent the stack
        self.arr = []
    
    # Function to push an integer into the stack.
    def push(self, data):
        # Add (append) data to the end of the list
        self.arr.append(data)
    
    # Function to remove an item from top of the stack.
    def pop(self):
        # Check if the stack is empty
        if not self.arr:
            return -1  # If empty, return -1
        return self.arr.pop()  # Remove and return the last element

Dry Run Example

Scenario:
Let’s say we do the following operations:

stack = MyStack()
stack.push(2)
stack.push(3)
stack.push(5)
print(stack.pop())  # Output? 5
print(stack.pop())  # Output? 3
print(stack.pop())  # Output? 2
print(stack.pop())  # Output? -1 (since stack is now empty)

Time and Space Complexity

• push(): O(1) per operation
• pop(): O(1) per operation
• Space: O(n) where n is the number of elements in the stack

Key Takeaways

• Python list is a perfect fit for stack because append() and pop() at end are both O(1).
• Always check for empty stack before popping, as popping from an empty stack is an error (here, we return -1).
• This is the basic way to build a stack in Python and under-the-hood in many programming languages!

If you understand this, you understand the fundamentals of stack implementation. Practice these operations and try to extend to other stack problems!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.