How do you implement a stack using lists?

Python Data Structures - Interview Questions and Answers

Implementing a Stack Using Lists in Python

A stack is a data structure that follows the Last In, First Out (LIFO) principle. Python lists can be used to implement a stack because they support append() and pop(), which operate in O(1) time at the end of the list.

1. Using a List to Implement a Stack

Operations :

Push (add an element) → append()
Pop (remove top element) → pop()
Peek (view top element without removing) → [-1]
Check if Stack is Empty → len(stack) == 0

Example :

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        """Add an item to the top of the stack (O(1) operation)."""
        self.stack.append(item)

    def pop(self):
        """Remove and return the top item from the stack (O(1) operation)."""
        if not self.is_empty():
            return self.stack.pop()
        return "Stack is empty"

    def peek(self):
        """Return the top item without removing it."""
        if not self.is_empty():
            return self.stack[-1]
        return "Stack is empty"

    def is_empty(self):
        """Check if the stack is empty."""
        return len(self.stack) == 0

    def size(self):
        """Return the size of the stack."""
        return len(self.stack)

# Example usage
s = Stack()
s.push(10)
s.push(20)
s.push(30)

print(s.peek())   # Output: 30
print(s.pop())    # Output: 30
print(s.size())   # Output: 2

2. Why Use `append()` and `pop()`?

append(x) adds to the end → O(1)
pop() removes from the end → O(1)
If we inserted or removed from the beginning (insert(0, x) or pop(0)), it would be O(n) due to shifting elements.

3. Alternative: Using `collections.deque` (More Efficient)

Python’s collections.deque is optimized for fast insertions/removals at both ends.

from collections import deque

class Stack:
    def __init__(self):
        self.stack = deque()

    def push(self, item):
        self.stack.append(item)  # O(1)

    def pop(self):
        return self.stack.pop() if self.stack else "Stack is empty"

    def peek(self):
        return self.stack[-1] if self.stack else "Stack is empty"

    def is_empty(self):
        return len(self.stack) == 0

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

* deque is faster for large datasets because it avoids list resizing.