Mind Your Stacks and Queues

Two of the most basic abstract data structures are stacks and queues. They help answer the question, “what’s next?” They are considered abstract because they can be implemented in a variety of ways, such as with an array or a linked list. Like most things both simple and ubiquitous, it is easy to forget how vital they are.

Material world examples of queues are abundant. We expect the the first person in line to be served before those who arrived later. We remember to place the new, full carton of eggs behind the half empty one to make sure those closer to expiration get eaten first.

Physical examples of stacks are often implemented as stacks for ease or conservation of space, not because the last one added needs to be prioritized over those further down. The spring loaded stack of plates at the front of a buffet line does not have the cleanest or best plates at the top, they just fit better that way.

In programming, the difference between using a stack or a queue is stark because they solve very different problems. Like when traversing a tree, changing a depth first search to breadth first is accomplished by substituting a queue for the stack that held the child nodes yet to be searched.

In the DFS above, all of A’s children are placed into a stack to be searched. B is 2nd to be search and all of B’s children are added to the stack, pushing C further down in priority. In the BFS the same searching is conducted, but each child is placed into a queue resulting in a very different ordering and help to answer different questions.

If you feel busy but unacomplished or find yourself at the end of the day with a lot of open browser tabs, you might need to consider when you should be using a queue and when you should use a stack and how you are implementing both.

In time management the stack vs queue question bears similarities to the question of important vs urgent. A ringing phone is said to be urgent. The caller, the message, and what is interrupting might all factor into whether or not it is important. If any ringing phone at any time of day must be answered, it might be said that it is pushed to the top of your attention stack.

A computer’s processor uses a queue and a stack. New incoming tasks get placed in line to be processed in order. But when the next in line is ready to be processed it is placed a the top of the a stack. If while executing that action, the action itself calls another subaction that must be completed before the original action can continue, the new action is placed at the top of the stack ahead of the original. The top of the stack is always what is being worked upon and once the stack is empty, then the next item in the queue can be added to the stack.

When learning to program, frequently you will encounter links to other content or need to Google something you don’t yet know. Determining whether something requires a full and immediate reading and understanding (adding to the stack) or is something that would be useful to delve into at a later time (adding to the queue) takes practice and discipline. Having good mentor or teacher also helps keep you on track.