DSA Stacks and Queues

Stacks and queues are simple lists with strict rules about where items go in and come out.

What is a Stack?

A stack is like a pile of plates at a wedding buffet. You put a new plate on top, and you also take a plate from the top. The last plate placed is the first one taken.

This rule is called LIFO: Last In, First Out.

Operation	Meaning	Big O
push	Put an item on top	O(1)
pop	Remove the top item	O(1)
peek	Look at the top item without removing it	O(1)
is empty	Check if the stack has no items	O(1)

A Stack in Python

A Python list works well as a stack. append pushes onto the end (the top), and pop removes from the end.

Example

python

stack = []
stack.append("Page 1")
stack.append("Page 2")
stack.append("Page 3")
print(stack[-1])

print(stack.pop())
print(stack.pop())
print(stack)

Output

Page 3
Page 3
Page 2
['Page 1']

This is how the Back button of a browser works: each new page is pushed, and Back pops the latest one.

Stack Example: Checking Brackets

Code editors use a stack to check that every bracket is closed in the right order.

Example

python

def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0

print(balanced("(a + b) * [c - d]"))
print(balanced("{[(])}"))
print(balanced("((x)"))

Output

True
False
False

Each opening bracket is pushed. Each closing bracket must match the bracket on top of the stack.

What is a Queue?

A queue is like a line at a bank counter. People join at the back and are served from the front. The first person to arrive is the first to be served.

This rule is called FIFO: First In, First Out.

Operation	Meaning	Big O
enqueue	Add an item at the back	O(1)
dequeue	Remove the item at the front	O(1)
front	Look at the first item	O(1)

A Queue in Python

Do not use list.pop(0) for a queue: it is O(n) because every item shifts. Use collections.deque, which adds and removes at both ends in O(1).

Example

python

from collections import deque

counter = deque()
counter.append("Ali")
counter.append("Sara")
counter.append("Hamza")

print("Serving:", counter.popleft())
print("Serving:", counter.popleft())
counter.append("Ayesha")
print("Waiting:", list(counter))

Output

Serving: Ali
Serving: Sara
Waiting: ['Hamza', 'Ayesha']

Queues are everywhere: printer jobs, messages waiting to be sent, and orders in a food delivery app are all handled in the order they arrived.

Stack vs Queue

	Stack	Queue
Rule	LIFO	FIFO
Add	push (top)	enqueue (back)
Remove	pop (top)	dequeue (front)
Real uses	Undo, browser back, function calls	Printing, task scheduling, BFS in graphs

A priority queue is a special queue where the most important item leaves first, for example patients in an emergency room. Python's heapq module provides one.

Exercise

You push 1, then 2, then 3 onto an empty stack, then pop once. Which item is removed?

123Nothing, stacks cannot pop