Stacks and Queues
Episode #6 of the course Kurt Anderson by Computer science fundamentals
Welcome back!
Computer science is all about layers building on other layers. We like to call this, abstraction. At first, we learned algorithm analysis and n-notation. From that, we could compare the array and linked list data structures. We are now going to add another layer to this by using those previous layers to build something new.
What Are Stacks and Queues?
Stacks and queues are special data structures that contain a specific set of rules. These rules are what define the data structure, giving them both pros and cons, and they are usually applied to either a linked list or array. It’s like a specialization. Through the rules, we are able to create a specialized structure with new pros and cons.
Queue. A queue is the more intuitive of the two. It works much like waiting in line to buy a ticket. The first element to get to the data structure is the first one to be served. So, say 100 pieces of data come in to a single processor. Number 1 will be served, then 2, then 3, and so on.
Stack. A stack, however, works like a stack of trays in a cafeteria. You always grab from the top, not the bottom. This means you will have a relationship where the most recent element will be the first serviced. Let’s go back to the example of 100 pieces of data coming in. In this case, 100 would be served first, then 99, then 98, then 97, and so on. This is helpful for something like an undo system on an application. Every step you make is inserted onto the stack. Then whenever you want to undo, you just “pop” off the top of the stack to go back in time.
There is specific terminology for stacks and queues, which are important to understand:
• Pop – to remove an element from a stack (can sometimes be used for queues)
• Push – to insert an element onto a stack (can sometimes be used for queues)
• Enqueue – to insert an element onto a queue
• Dequeue – to remove an element from a queue
• FIFO – means “first in, first out” (the technical term for a queue-like data structure)
• LIFO – means “last in, first out” (the technical term for a stack-like data structure)
Stack and Queue Run Benefits
Why use a stack or queue? What makes them special? In computer science, modeling is very important. Through modeling and abstraction, we can take a machine that only does 1s and 0s and turn it into anything we want. Stacks and queues are just another example of this abstraction. Basically, it’s just another layer of rules to add onto a pre-existing structure so we can control the data in a slightly different manner.
Stacks are widely used in almost every aspect of computer design. Just through reading your email, hundreds of stacks are probably being implemented. Same with queues. Processors love queues, as they give it a linear set of instructions to execute.
Stack and Queue Run Times
Now, let’s take a look at run times associated with these data structures.
As these data structures are so specialized, we can actually get O(1) run time on all operations of both stacks and queues. This is because we are only accessing the “ends” of the data structures. So, we don’t have to worry about trying to get to the middle. Linked lists are usually best for these structures, as they can expand indefinitely.
With a stack, we just keep inserting and removing from the front of the data structure. We learned in previous lessons that both of these operations are O(1).
With a queue, we insert to the front and remove from the back. We can do this in O(1) time as well. (We would need to implement a tail pointer for this to work. It’s simply a piece of data that always points to the end of the linked list.)
Stacks and queues are great data structures and really show off the power of computer science. They build off previous advancements to create new structures for problem solving.
Key takeaways:
• Stacks and queues build off previous implementations of data structures.
• Stacks are LIFO, while Queues are FIFO.
• They are both used widely throughout computer science.
• All operations of stacks and queues are O(1) time.
Tomorrow, we will begin looking at sorting algorithms!
Cheers,
Kurt
Recommended resources
Stack Data Structure: Code examples of how a stack might be implemented.
Queue Data Structure: Code examples of how a queue might be implemented.
Share with friends