Stacks and Queues: LIFO and FIFO

Structures that deliberately do less

Arrays and linked lists let you touch anything. Stacks and queues do the opposite: they restrict you to adding and removing at specific ends only.

That sounds like a downside. It is actually the point. When a structure allows fewer operations, its behaviour becomes predictable, the operations become O(1), and your code becomes easier to reason about. A great deal of good engineering is choosing the least powerful tool that solves the problem.

Stack: last in, first out

Think of a stack of plates in a canteen. You put a clean plate on top. The next person takes from the top. The plate at the bottom has been there since morning.

That is LIFO — Last In, First Out.

A stack supports exactly:

• push(x) — add to the top
• pop() — remove and return the top
• peek() — look at the top without removing
• is_empty() — check whether anything is there

All O(1). Nothing in a stack requires searching or shifting.

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

    def push(self, x):
        self.items.append(x)          # O(1) - add at the end

    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop()       # O(1) - remove from the end

    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]

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

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

s = Stack()
for page in ["home", "courses", "dsa", "arrays"]:
    s.push(page)
    print("Visited:", page, "| stack:", s.items)

print()
print("Back button pressed ->", s.pop())
print("Back button pressed ->", s.pop())
print("Currently on:", s.peek())
print("Pages still in history:", s.size())

Notice the array is used only at its end, where append and pop are O(1). That is why a Python list makes a perfectly good stack.

Real uses of stacks

Undo in an editor. Every action is pushed. Ctrl+Z pops the most recent one. You undo in exactly the reverse order you acted — that is LIFO.

Browser back button. Each page you visit is pushed; back pops.

Function calls. When your program calls a function, the computer pushes a frame with local variables and the return address onto the call stack. When the function returns, the frame is popped. Infinite recursion fills this up and gives you a stack overflow.

Expression evaluation and bracket matching. Compilers use stacks to check that every opening bracket has a matching closing one.

def brackets_balanced(expr):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for ch in expr:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()

    return len(stack) == 0

tests = ["(a + b) * [c - d]", "{[()]}", "(a + b", "([)]", "]("]
for t in tests:
    print(t.ljust(20), "->", brackets_balanced(t))

Trace ([)]. The ( and [ are pushed. Then ) arrives and the top of the stack is [, which does not match — so it is rejected. A simple counter of open and closed brackets would wrongly accept this. The stack remembers order, which is exactly what the problem needs.

Queue: first in, first out

A queue is the line outside an examination hall. The first person to join is the first served. Joining at the front is not allowed.

That is FIFO — First In, First Out.

A queue supports:

• enqueue(x) — add at the rear
• dequeue() — remove from the front
• front() — look at the front element
• is_empty()

from collections import deque

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

    def enqueue(self, x):
        self.items.append(x)          # O(1) at the rear

    def dequeue(self):
        if self.is_empty():
            return None
        return self.items.popleft()   # O(1) at the front

    def front(self):
        if self.is_empty():
            return None
        return self.items[0]

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

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

q = Queue()
for job in ["print_report", "send_email", "backup_db"]:
    q.enqueue(job)
    print("Queued:", job, "| waiting:", list(q.items))

print()
while not q.is_empty():
    print("Processing:", q.dequeue(), "| remaining:", q.size())

The queue problem with plain arrays

If you build a queue on a plain Python list, enqueue is append() — O(1), fine. But dequeue is pop(0), which removes from the front and shifts every remaining element left. That is O(n) per removal, so processing n items costs O(n^2).

Two standard fixes:

Use a deque. collections.deque is a doubly linked structure that gives O(1) at both ends. That is why the code above uses it.

Use a circular queue. Keep the array fixed in size with front and rear indices that wrap around using the modulo operator. Nothing shifts; the indices move instead.

class CircularQueue:
    def __init__(self, capacity):
        self.data = [None] * capacity
        self.capacity = capacity
        self.front = 0
        self.count = 0

    def enqueue(self, x):
        if self.count == self.capacity:
            return False                      # queue is full
        rear = (self.front + self.count) % self.capacity
        self.data[rear] = x
        self.count += 1
        return True

    def dequeue(self):
        if self.count == 0:
            return None
        x = self.data[self.front]
        self.data[self.front] = None
        self.front = (self.front + 1) % self.capacity
        self.count -= 1
        return x

cq = CircularQueue(4)
for token in [101, 102, 103, 104]:
    cq.enqueue(token)
print("Buffer after filling:", cq.data, "| full?", cq.enqueue(105) is False)

print("Served:", cq.dequeue())
print("Served:", cq.dequeue())
cq.enqueue(105)
cq.enqueue(106)
print("Buffer after wrap-around:", cq.data)
print("Front index is now:", cq.front, "with", cq.count, "items")

Look at the final buffer. The new tokens 105 and 106 landed in the slots freed at the start of the array. Nothing was copied or shifted — the indices wrapped instead. That is the whole idea of a circular queue.

Real uses of queues

CPU and print scheduling. Jobs are served in arrival order so nothing waits forever.

Buffers. Keyboard input, network packets and streaming data are held in queues between a fast producer and a slower consumer.

Breadth-first search. Exploring a graph or grid level by level uses a queue to hold the frontier. Shortest-path-in-a-maze problems are built on this.

Request handling. Web servers queue incoming requests when all workers are busy.

Common mistakes

Popping from an empty structure. [].pop() raises IndexError. Always check is_empty() first, or handle the exception.

Using list.pop(0) for a queue. It works but is O(n) per call, turning a linear job into a quadratic one. Use deque or a circular queue.

Mixing up which end is which. A stack pushes and pops at the same end. A queue adds at one end and removes at the other. Getting this backwards produces plausible-looking but wrong output.

Forgetting that pop() removes. peek() looks, pop() takes. Calling pop() when you only wanted to inspect silently loses data.

Off-by-one in a circular queue. Tracking a count, as above, is easier to get right than comparing front and rear indices, where a full queue and an empty queue can look identical.

Practice

Try the stack and queue exercises on the practice page — bracket matching is a good place to start.