Queues and Stacks

[Cervantes]

This animated tutorial will attempt to explain what queues and stacks are, and how to use them in Ruby.

General Overview
Queues and Stacks are nothing more than arrays with a special definition of how values are added and removed from them. This is commonly referred to as "pushing" and "popping". You may "push" a value into your array, which adds a new element and places the value at the end of the array. You may also "pop" an element off your array. Where the element is popped, or removed, from depends on whether you are dealing with a queue or with a stack.

Stack
We're washing dishes. Bits of dried lasagna are stuck to them, so this may take a while. We wash the first plate and put it on the counter.

Ruby:

# Create an empty stack of dishes. dishes = [] # Push a plate onto the stack.  You could argue we're dropping the plate, not really pushing it.  Think of it like that if you must, but use this syntax. dishes.push("plate")

We wash the second plate and put it on top of the first plate.

Ruby:

dishes.push("plate")

Now our stack of dishes looks like this:

irb wrote:

irb(main):004:0> puts dishes
plate
plate
=> nil

We wash a glass (which contained your alcoholic uncle's vodka) and put on top of the second plate.

Ruby:

dishes.push("vodka glass")

Your uncle waddles into the kitchen with the vodka bottle in hand. Fortunately, he's a polite drunk, so he refrains from drinking out of the bottle. You hand him the cup.

Ruby:

# The pop method will return the top element of the array, and also remove it from the array. your_uncles_hand = dishes.pop

Suddenly, your conscience begins screaming.
Your conscience: What are you doing?! You left a spot of cheese on the first plate!
You: I'd love to fix it, but that would mean I have to remove the glass and the second plate just to get at the first.
(In case you're wondering, you only have one arm and can't simply slip the first plate out.)
Your conscience: Do it!

Ruby:

# Take off the second plate and put it by the frige by_the_frige = dishes.pop # Take the first plate out of the stack and wash it. dishes.pop.wash_the_plate # Put the clean plate back on the stack dishes.push("super clean plate") # Put the second plate back on the stack dishes.push("plate")

The lesson here is that a stack is an array that only allows you to add items to the top of it and only allows you to remove items from the top of it. The last plate on the stack is the first plate off the stack, when you go to put them away. The first plate on the stack is the last plate off the stack. First in, last out. FILO.

Queue
We're in a bank. The line is empty. Seeing this, a customer rushes inside knowing he won't have to wait. As he is being served, another customer enters the bank. Sadly, there is only one teller, so the second customer must wait behind the first customer. The teller finishes with the first customer and he eagerly runs to buy an iced cappuccino. Now it is the second customers turn to be served. Then a third customer enters the bank and waits behind the second customer. When the teller finishes with the second customer, it will be the third and last customer's turn.

The first customer to enter the line is the first one out of the line. First in, first out. FIFO. This is the basis of the queue.

We push a customer into the line, which will add a new element to the array and set the value of this new element (which is the uppermost element of the array) to be the customer's name:

Ruby:

bank_line = []                         # declare the array and make it empty bank_line.push("Happy Jack")   # push "Happy Jack" into the line.  Forcefully, if possible. currentCustomer = "Happy Jack"

Now the second customer strolls in and waits in line:

Ruby:

bank_line.push("Impatient Irene")

Impatient Irene is getting edgey. She doesn't want to wait in line. Finally, just before she would snap, Happy Jack finishes his transaction.

Ruby:

# Happy Jack is now gone.  the current customer is now Impatient Irene. currentCustomer = bank_line.shift # Note that you don't have to use the value returned by the shift method. # If you don't want to store the current customer (you could always just do bank_line [0] ), you can just call bank_line.shift

You: Wait a minute. I thought we were supposed to pop Happy Jack out of the line. What's this "shift" business?
We can't use the pop method because that is built to take the element from the top, or from the uppermost element. Instead, we use the shift method, which will take the element from the bottom. It stores the first element, shifts every other element down one place, then returns what is stored as the previous first element.
Now Crunchy Chris enters the line.

Ruby:

bank_line.push("Crunchy Chris")

Now Impatient Irene finishes her transaction, and Crunchy Chris is first in line.

Ruby:

currentCustomer = bank_line.shift

Crunchy Chris was the last one to enter the line. Crunchy Chris was also the last one out of the line. Happy Jack, on the other hand, was the first one in the line and also the first one out of the line. FIFO.

Conclusion
Stacks are FILO. Use the methods "pop" and "push".
Queues are FIFO. Use the methods "shift" and "push".

I don't think such a long tutorial was necessary for this topic. In fact, I'm sure it wasn't. In any case, I hope you've enjoyed this content-light and description-heavy tutorial/story.

Have a good day, or what's left of it.

-Cervantes

[Tony]

Amazingly put *takes notes on presentation of content*

[Hikaru79]

Woah! Worthy of the Poignant Guide itself!! Very interesting way to explain it, Cervantes! Do more ^_^