Stacks and Queues

Importance of Stacks and Queues

Stacks and Queues are important and useful when you want to be able to get things in an order of your choosing. If you wanted to be able to retrieve data in the order that you put them in, then you would want to use a queue. If you would want to be able to retrieve data in the opposite or reverse order that they were put in, then you would use stacks. In this blog, I will be going more in-depth about these two data structures.

Intro to Stacks

A stack is stack of data, where you can only add to the top of the structure. When it comes to stacks you aren’t able to retrieve data anywhere within the stack as you please, instead you will have to retrieve the last data first and then go in that order. This process is also known as “last in, first out”. An easier way to think about this is, let’s say that we are at a family thanksgiving and the sliced hams are all stacked on top of each other on a plate, you would have to remove the ham slices that are on the top of the stack since they are on top and just easier to remove versus grabbing them from the bottom or middle. If you are still struggling to picture or imagine the stack, I have few illustrations below to help you out!

As you see in the picture above, we have our plate with our stack of ham slices and let’s say we wanted to get the ham slice that has the 11 on it because it looks the best! In order to do this, we would have to start by removing the ones on top of it.

This would mean we would have to take off the one that is on top, which is number 9 and then we would be able to have access to the slice that we want which would be the ham slice that is numbered as 11.

We now can remove the one we desired, and this makes sense because ham number 11 was near top of the stack meaning it would be easier to access and grab from the top versus going from the bottom to top.

Stacks as an array

Let’s continue with our example from above and pretend that we have an empty plate(array) and a pointer for the elements set to “-1” so that it will always point to the top of the stack (last element of an array)

empty array
------------
| | | | | |
------------
^ pointer set to be -1 (currently pointing at nothing)

So, if we add our ham that has the number of “1” onto the empty plate(array) then it would be the only thing on the plate and the pointer would point to that ham.

array of our hams
------------
|1| | | | |
------------
 ^ pointer now points at the last element or the top of our stack

Now if we add our ham that has the number of “4” to the plate(array) then that means that this ham will be the top of our ham stack. Then the pointer will move and point to that since it’s the top of the stack.

array of our hams
------------
|1|4| | | |
------------
   ^ pointer now points at the last element or the top of our stack

This will continue to happen as we add onto the ham stack/ham array and will always point to the last element in the array.

Intro to Queue

A queue is something I’m sure most of us know already, if not do not worry, as I will break it down for you! Imagine that you are at an amusement park of your choosing and you are waiting in line to go on the newest ride! Well, the line is a queue where whomever was first to get in line will also be the first to get out of line. and also get out first, also known as “first in, first out”.

Queue as an array

Let’s take a look at a queue as an array! For this example we will go with people waiting in line and each person would be numbered differently.

queue array
------------
| | | | | |
------------
^^ two pointers

If the two pointers are pointing at the same spot within an array that means the array would be empty.

queue array
------------
|1| | | | |
------------
 ^ ^ 2nd pointer moves.

In the array the first pointer will point at the front of the queue or the first person in line. While the second pointer moves over and will point at the space after the last person in the queue.

queue array
------------
|1|23| | | |
------------
 ^    ^ 2nd pointer moves again.

If we were to have another person come join the line then the pointer will once again move to the space after the last person.

queue array
------------
|1|23|5| | |
------------
 ^      ^ 2nd pointer again moves again to the space after the last              person

There’s nothing new going on here again but what if the person in the front heads onto the ride and is out of queue? What happens next? Well let’s take a look!

queue array
------------
| |23|5| | |
------------
   ^    ^

Then we would have the first pointer move onto the next person who is now in front of the line and stays there until that person gets onto the line! What about the second pointer? What if we had an array that looks like the following below.

queue array
------------
| | |5|7|44|
------------
     ^ first pointer. But what about the 2nd pointer?

In the case where we hit the end of the array then we would have to have the second pointer move into the front where there is empty space! This would look like the following!

queue array
------------
| | |5|7|44|
------------
 ^   ^
2nd & 1st pointer

Conclusion

Well that is all I have so far! But I am going to comeback with better explanations and examples once I play around and get a better understanding of stacks and queues!