Stack and Queue: Implementation and Interview Problems in Python

Stack and Queue

Stacks and queues are fundamental data structures used everywhere — function call stacks, browser history, BFS/DFS algorithms, undo systems, and print queues. Both are tested in nearly every entry-level interview.

Stack — LIFO (Last In, First Out)

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

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

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items.pop()    # O(1)

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items[-1]      # top item without removing

    def is_empty(self): return len(self.items) == 0
    def size(self):     return len(self.items)
    def __repr__(self): return f"Stack({self.items})"

s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek())  # 3
print(s.pop())   # 3
print(s)         # Stack([1, 2])

Real Stack Use: Balanced Parentheses

def is_balanced(s: str) -> bool:
    stack   = []
    mapping = {')':'(', ']':'[', '}':'{'}

    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()

    return len(stack) == 0  # empty = all matched

print(is_balanced("({[]})"))  # True
print(is_balanced("({[})"))   # False
print(is_balanced("()[]{}"))  # True

Queue — FIFO (First In, First Out)

from collections import deque  # O(1) append and popleft

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)      # add to back O(1)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items.popleft()  # remove from front O(1)

    def front(self):      return self.items[0]
    def is_empty(self):   return len(self.items) == 0
    def size(self):       return len(self.items)

q = Queue()
q.enqueue('Rahul'); q.enqueue('Priya'); q.enqueue('Amit')
print(q.dequeue())  # Rahul (first in, first out)
print(q.front())    # Priya

Stack with Min — Classic Interview Question

class MinStack:
    def __init__(self):
        self.stack     = []
        self.min_stack = []  # tracks minimum at each level

    def push(self, val):
        self.stack.append(val)
        # Track running minimum
        curr_min = min(val, self.min_stack[-1]) if self.min_stack else val
        self.min_stack.append(curr_min)

    def pop(self):
        self.min_stack.pop()
        return self.stack.pop()

    def top(self):     return self.stack[-1]
    def getMin(self):  return self.min_stack[-1]  # O(1)!

ms = MinStack()
ms.push(5); ms.push(3); ms.push(7); ms.push(2)
print(ms.getMin())  # 2
ms.pop()
print(ms.getMin())  # 3