A quick cheat sheet / mini-quiz on Stacks & Queues to brush up on the fundamentals.
This blog post will be formatted with a question and then a corresponding answer. I find that having a question posed can help solidify my ability to recall information as well as force me to have a better understanding of the topic. See if it does the same for you.
As you go through the blog try to answer the questions in your own words before looking at the provided answer.
Stacks & Queues are both?
- Linear Data structures → each allows you to traverse elements one by one (only one data element can be reached at a time)
- Mainly used to push, pop, peak, shift → they only deal with whats at the end or the top → there is no random access operation
What is the benefit of limiting the types of operations for Stacks and Queues?
- By limiting the number of operations you can perform on this data structure ensures that whoever is using them uses only the tools/operations that they need to use. If you give them too many, it can cause errors.
Describe a Stack.
- Stacks are like plates.
- You can only access the plate on top → Last In, First Out. → LIFO
- i.e. You can only access the element that was most recently added to the stack.
Where are Stacks used?
- Stacks are important for language-specific engines.
- They are also used in browser history. As well as when you ‘undo’/’ctrl z’ something.
What are the bigO for Stack operations?
- lookup → O(n)
- pop → O(1)
- push → O(1)
- peek → O(1) → view the top most plate/element
Describe a Queue.
- A queue is a linear data structure that operates under First In, First Out → meaning that it's analogous to any line, like for a roller coaster → opposite of stacks.
- First person in line gets to go on the ride first.
What are Queues used for?
- any waitlist
- check ins
- uber/lyft
- printers → the person who clicks print first gets their documents printed first
What are the bigO for Queue operations?
- lookup → O(n)
- enqueue/push() → O(1)
- dequeue/unshift() → O(1)
- peek → O(1)
- *typically we do not use lookup when working with queues → focus on the push and unshift/enqueue and dequeue
Why would we not want to use an array to implement a queue?
- Because when we dequeue/unshift we’d have to shift all the following indexes to i-1 → very inefficient
How would you implement a Stack class? What parameters/attributes would be instantiated within the constructor method?
- Use a linked list → more specifically → use Nodes in order to implement the stack
- Parameters to be instantiated:
- this.top = null
- this.bottom = null
- this.length = 0
What operations would be associated with the Stack class?
- peek
- push
- pop
- length
- *bonus → how would you implement this?
How would you implement a Queue? What are the parameters/attributes?
- this.first
- this.last
- this.length
What are the operations for the Queue class?
- peek
- enqueue
- dequeue
What are Stacks + Queues good for?
- Fast operations
Fast peek
They are Ordered - Slow Lookup (requires traversal)
- *When using stacks we primarily only need to look at the beginning or end
- *When using queues we push to the back, pop from the front (linked lists)
And that's all for now folks! If you managed to get these answers and some that's fantastic. If you have any additional details you think should be added to these answers feel free to message me and lmk! I’ll update them for future readers. Thanks and happy hacking!