DSA · Lesson 4 of 9

Stacks & queues

LIFO and FIFO structures and the problems they solve.

Stack — Last In, First Out. Push and pop at one end. In Python, a list's append/pop are O(1). Used for undo, matching brackets, depth-first search, evaluating expressions.
Queue — First In, First Out. Use collections.deque with append/popleft (O(1)); a list's pop(0) is O(n). Used for task processing and breadth-first search.
Monotonic stack — keeps items in increasing/decreasing order to answer “next greater element” in O(n).

Try it yourself

Code editor

Press Run to see the output.

Edit and press Run (or Ctrl/⌘ + Enter). Python runs in your browser — the first run downloads the Python engine and takes a few seconds.

Which structure processes items in the order they arrived?

Stack Queue Set Heap

Implement a queue using two stacks with enqueue and dequeue methods, and test it with 5 operations.

Why not use list.pop(0) for a queue?

It shifts every remaining element — O(n). deque.popleft() is O(1).

How would you design a min-stack with O(1) getMin?

Keep a second stack of current minimums; push the new min on every push and pop both together.