Data structures and patterns · Question 37 of 50
Stack or queue? Where are they used?
What they're checking
The basics, and seeing them in real systems.
The answer
A stack is last in, first out: push and pop at the same end, both O(1). It is the call stack, undo, the browser's back button, matching brackets and depth-first search.
A queue is first in, first out: add at the back, take from the front. It is job queues, the event loop's task queue, printing, breadth-first search and paced sending. A deque allows both ends; a priority queue (a heap) serves the most urgent first instead of the oldest.
function balanced(s) {
const pairs = { ')': '(', ']': '[', '}': '{' }
const stack = []
for (const ch of s) {
if ('([{'.includes(ch)) stack.push(ch)
else if (pairs[ch] && stack.pop() !== pairs[ch]) return false
}
return stack.length === 0
}The picture
stack (LIFO): push 1, 2, 3 → [1 2 3] → pop → 3 queue (FIFO): add 1, 2, 3 → [1 2 3] → take → 1
The follow-up they'll ask
How do you build a queue from two stacks?
Show the answer
Push onto stack A. To take one, if B is empty move everything from A to B, then pop B. Each item moves once, so it is O(1) on average.
Your progress stays on this device.