Quick & Dirty Notes / Mini-Quiz: Stacks & Queues

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.

  • 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
  • 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.
  • 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.
  • Stacks are important for language-specific engines.
  • They are also used in browser history. As well as when you ‘undo’/’ctrl z’ something.
  • lookup → O(n)
  • pop → O(1)
  • push → O(1)
  • peek → O(1) → view the top most plate/element
  • 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.
  • any waitlist
  • check ins
  • uber/lyft
  • printers → the person who clicks print first gets their documents printed first
  • 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
  • Because when we dequeue/unshift we’d have to shift all the following indexes to i-1 → very inefficient
  • 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
  • peek
  • push
  • pop
  • length
  • *bonus → how would you implement this?
  • this.first
  • this.last
  • this.length
  • peek
  • enqueue
  • dequeue
  • 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!

Just another one of those dreamers with a sparkle in his eyes.