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

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)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store