My notes on Stacks vs Queues

Yes indeed, another article out here on the web talking about our favorite data structure cousins. Are they cousins? Maybe they’re more like siblings? You can decide.

When I first learned about stacks and queues I found myself easily getting confused between them. It seemed like they were more alike than different. Yes, I know I know…stacks are like pancakes and queues are like lines at the theater. This much I grasped. However, when it came to solving algorithms I couldn’t determine which one of the two data structures to use and why. A part of me was secretly convinced that they were the same. Spoiler alert — they’re not!

I eventually found a way to approach the information so that it made better sense to me. I would recommend the following three steps if you are also confused between stacks and queues:

1. Create a list of the similarities between stacks and queues
2. Create a table to compare the differences between stacks and queues
3. Solve an algorithm using a stack for one approach and queue for the other and compare how the solution differs (tree traversal is a classic example)

Here are my notes for each of the above steps:

1. The similarities between stacks and queues:

• Both are linear data structures where elements are connected in a sequence at the same level. For comparison think of nonlinear data structures as collections of elements organized as a hierarchy with multiple levels e.g. Graphs or Trees.
• Both stacks and queues can be implemented using arrays and array methods. Be very careful here, this does not mean that arrays are the same as stacks and queues! Just because we can use arrays to make stacks and queues doesn’t mean that arrays are stacks and queues. Operations like accessing elements from the middle, as you would do in an array, are NOT ALLOWED if you call something a stack or a queue. This is because stacks and queues do not have indices to access their elements from the middle of a collection.
• Both data structures can be implemented using linked lists. Again be careful here, stacks and queues can be created using linked lists but are not equal to linked lists.

stacks and queues are not arrays or linked lists but you will most likely see these words used together so pay attention to the differences.

2. Create a table to compare the differences between stacks and queues

A table I created to compare the differences between stacks and queues

3. Solve an algorithm using a stack for one approach and queue for the
other and compare how the solution differs.

Assuming that you are familiar with the concept of tree traversal I’m going to take the opportunity here to simply remind ourselves of the BFS solution and illustrate why that doesn’t work with a stack.

Remember that when we want to traverse a tree we can do so level by level aka BFS, or branch by branch aka DFS. If you note in my beautiful table above, I’ve listed BFS under the Queues column and DFS under the Stacks column. In the beginning this might be something that a lot of students just memorize and if you’re cramming for a test and would like a quick way to remember which one to use then check out this thread: https://stackoverflow.com/questions/3929079/how-can-i-remember-which-data-structures-are-used-by-dfs-and-bfs

However, memorizing is not ideal so I would highly suggest taking the time to review BFS and DFS and how they differ. I will get you started here with a general overview.

A tree diagram where the numbers represent nodes and NOT the actual values of those nodes

I have a simple tree diagram where the root node branches off into two branches. ( I could call this a BST but I don’t want to confuse you because the numbers don’t represent the actual values at those nodes). If I were to traverse this tree using a queue then the order that my nodes would get processed is: 1,2,3,4,5,6,7. This is because as a node is added to our queue its children are then added next in line to be processed. So after we visit the first node we add (enqueue) its children nodes 2 and 3 to the queue to be processed. Next we see that nodes 4 and 5 are the children of node 2 so those get added to the queue and then finally, nodes 6 and 7 as children of node 3 get added to the queue. The nodes that are going into the queue first are also being processed first aka First In First Out (FIFO).
Simple? I hope so because it certainly wasn’t for me the first time. This is where I got stuck and thought, “why can’t I use a stack to do the same exact thing?” The answer is that you “could” certainly use a stack to traverse this tree but there’s no way you could do a level by level search if you were to use a stack (if you don’t believe me, try it).
A stack is NOT First In First Out, it’s Last In First Out (LIFO) so you won’t be able to access the nodes you add into the stack the same way that you can access them in a queue. The nodes that we add into the stack get pushed to the bottom and it’s against the rules of a stack to try and grab nodes that are at the bottom when you still have nodes sitting on top. For example, given the same tree above, if we started the same order of processing with node 1 and then its children, look below at the difference we have. WARNING this is NOT the approach to solving a DFS with stacks. I’m simply illustrating what would happen if I tried using a stack the same way that I’m using my queue.

What my queue looks like if I process node 1 and enqueue children nodes 2 and 3 into the queue

What my stack looks like if I process node 1 and push children nodes 2 and 3 into the stack

I hope it is easy to see that if I pretended there was no difference between stacks and queues and started to push my children nodes into the stack I would not be allowed to process them in the same order. With the queue, I can process node 2 if I wanted to but with the stack I could not do that because node 3 is sitting right on top.

At this point you’re thinking one of three things: “wow this makes so much sense!” or “what is this lady talking about?” or “well, duh!”.

If you’re in the latter categories, think of this as a bad dream and continue forth in your browsing activities. If however, you found this to be helpful then great! I’m glad I could help and my suggestion for you would be to continue approaching abstract concepts with understanding them in diagrams and tables first before you jump to lines of code. :)

Thanks for reading and please do share your comments especially if there are any corrections to be made …maybe I think I understand but I really don’t ..dun..dun..dun