Stacks & Queues

Lesson 2 · OKSTEM College · AS Computer Science

Stack: LIFO

A stack is Last-In-First-Out. Think: a stack of plates. Operations: push, pop, peek, is_empty — all O(1).

class Stack: def __init__(self): self._data = [] def push(self, val): self._data.append(val) def pop(self): if self.is_empty(): raise IndexError("pop from empty stack") return self._data.pop() def peek(self): return self._data[-1] def is_empty(self): return len(self._data) == 0

Real uses: function call stack, undo history, balanced-bracket checking, expression evaluation.

Queue: FIFO

A queue is First-In-First-Out. Think: a line at a coffee shop. Use collections.deque in Python for O(1) enqueue and dequeue.

from collections import deque class Queue: def __init__(self): self._q = deque() def enqueue(self, val): self._q.append(val) # O(1) def dequeue(self): return self._q.popleft() # O(1) def peek(self): return self._q[0] def is_empty(self): return len(self._q) == 0

Don't use a list as a queue — list.pop(0) is O(n) because it shifts every element. Always use deque.

Balanced Brackets — Classic Stack Problem

def is_balanced(s: str) -> bool: stack, pairs = [], {')':'(', ']':'[', '}':'{'} for ch in s: if ch in '([{': stack.append(ch) elif ch in pairs: if not stack or stack[-1] != pairs[ch]: return False stack.pop() return not stack print(is_balanced("({[]})")) # True print(is_balanced("({)}")) # False

Practice

1. Why does using a list for a queue give O(n) dequeue?

list.pop(0) removes the first element, then shifts every remaining element one position left — O(n) work. deque stores elements as a doubly-linked list of fixed-size blocks, so popleft() is O(1).

2. Implement a function using two stacks to simulate a queue.

class TwoStackQueue: def __init__(self): self.inbox, self.outbox = [], [] def enqueue(self, v): self.inbox.append(v) def dequeue(self): if not self.outbox: while self.inbox: self.outbox.append(self.inbox.pop()) return self.outbox.pop()

Knowledge Check

Stack operations push and pop are

Correct — append/pop from the end of a list are constant time.

Shifting is not needed; stack operates at one end only.

No searching or tree traversal involved.

That's a typical sorting bound.

Recap: stack push = list.append (O(1)). Stack pop = list.pop() from end (O(1)). No shifting needed.

Which Python collection provides O(1) popleft()?

list.pop(0) is O(n) — all elements shift.

Correct — deque is a double-ended queue; both ends are O(1).

Sets are unordered; no popleft concept.

Tuples are immutable.

Recap: always use collections.deque for queues. list is fine for stacks (operate only at one end).

The call stack in a program uses which data structure?

Queues are FIFO; function calls use LIFO (most-recent first).

Correct — each function call pushes a frame; returning pops it.

The heap is for dynamic memory allocation, not call tracking.

Conceptually it's a stack, not a linked list.

Recap: the 'call stack' is literally a stack. Each function invocation pushes an activation record; each return pops it.

is_balanced works by

Counting alone fails for interleaved types like ({)}.

Correct — the top of the stack must match the current closer.

Sorting destroys order information.

The iterative stack approach is standard.

Recap: push open brackets; when you see a close bracket, check if the top matches. At the end, the stack must be empty.

A queue is appropriate when

LIFO is a stack.

Correct — print queues, BFS, CPU scheduling all use FIFO.

Neither stack nor queue supports O(1) random access.

Sorted access needs a priority queue (heap), not a plain queue.

Recap: queue = FIFO. Stack = LIFO. Choose based on whether you need to process in arrival order or reverse order.

← Previous Next →