What are Stacks and Queues?
Stacks and queues, told as a story about the right way to stack parts boxes and line up cars.
You need to grab just box B from the pile.A messy pile means you can't grab the box you need right away.
Pile and grab without a rule, and the order changes every time.There has to be a rule linking the order in to the order out.
Linear data structures = fixed rules for stacking or lining things up.Stacks and queues differ in where you take from — the top, or the front.
Each put-in and take-out operation has its own name.An array — finding things directly by index — is worth knowing too.
Stack boxes too high and the pile overflows; let a queue grow unchecked and it never stops.The rule is simple — but push a stack or queue past its size limit, and trouble follows.
Stack = stack boxes up and take from the top (LIFO). Queue = line cars up and send them off from the front (FIFO).
A stack is Last-In-First-Out (LIFO): push (insert) and pop (remove) both happen at one end, and it underlies function calls and undo history. A queue is First-In-First-Out (FIFO): enqueue (insert) happens at the back, dequeue (remove) at the front, and it underlies task waiting lines. An array gives direct O(1) index access but is costly to resize; a linked list makes insertion and removal easy but only allows sequential access.
When grown-ups say it
- Stack (LIFO)
- The last box in comes out first. push and pop happen only at the top.
- Queue (FIFO)
- The first car in line leaves first. Enqueue at the back, dequeue at the front.
- Array
- A numbered shelf of boxes. Direct lookup by number — fast, but resizing is costly.
- CPU Scheduling (uses a queue)
- The job board itself is a queue. See how that board gets used. → who gets the lift first
- Starvation (a queue that lets cutting)
- A line where urgent cars keep cutting in. Break the ordering rule, and the queue turns unfair. → the garage frozen waiting on each other's keys
- Binary Tree
- A shelf map where every fork picks left or right. A branching structure, instead of a single line. → the shelf map that halves the search at every fork
- Time Complexity
- The ruler for how time grows as data grows. push/pop are O(1); inserting in the middle is slower. → how much slower as cars pile up
- Message Queue (another field)
- A similar "lining up" idea in the SRE field. Services pass work to each other through queues too. → the message queue in the SRE field