Lists: Using Stacks as Queues
Lists: Using Stacks as Queues
Stacks and queues might sound about as different as Hamilton and Burr, and…they are. Stacks are last in, first out (LIFO) structures, and queues are first in, first out (FIFO). Stacks insert and delete from the top, while queues insert in the back and delete from the front. If you replace one with the other, you'll get mass chaos—and probably a 19th Century duel or two.
At the same time, sometimes a stack has to talk less, smile more act like a queue to get things done.
You can totally make them act like each other if you set up a pair of stacks to mimic a queue. Sound bizarre and pointless? It is, but so is the idea of a hip-hop musical set during American Revolution. If it worked for Lin-Manuel Miranda, it can work for us, too.
At least for educational reasons, anyway.
To illustrate how this works, we'll compare a queue to the two stacks. Let's set everything up.
In this queue, we'll work with letters instead of numbers just to shake things up. H is the first letter we'll enqueue, because it has some rocking symmetry. To mimic this enqueuing process with stacks, we'll push H onto Stack 1, too.
Since we threw a darts at an eye chart to get our letters, we'll enqueue (and push) the letters E and Q next. Now Stack 1 looks like that queue, except reversed.
Whenever you want to dequeue a value, you're going to pretend like you're removing something from the bottom of the stack. To get rid of H, you'll need to pop both E and Q and move them to Stack 2 first, then pop the H that would be at the front of a queue.
Then we'll pop H off of Stack 1.
Once that H is done for, you can pop everything back from Stack 2 and push it back to Stack 1.
Adding on is essentially the same when adding onto a queue as a stack. You don't need to do any fancy maneuvers to make them work. Dequeueing is the only place you need to change things up for stacks to work as queues.
Using two stacks takes a bit longer and involves more steps than just using a queue, but they can both get you to the same place.
It's kind-of a big deal.