5)Stacks and Queues:

Stacks and Queues:

  • Stacks are last-in first-out (LIFO), like a stack of dinner plates or trays.
  • Queues are first-in first-out (FIFO), like a queue at an amusement park ride.
  • Both are easily implemented with a linked list.
  • With a stack, there's only one access point: the top (the linked list's head), and nodes point down / toward the tail.
  • With a queue, there are two: the first node (the head [of the line]) and the last (the tail). Nodes point back / toward the tail and are added to the tail (!).
  • Priority queues are neat structures (technically ADTs) where ordering is determined not by insertion time, but by some priority field:
    • Support insertion, find-min (or find-max), and delete-min (delete-max) operations.
    • The idea is that if I consistently just want the highest priority element, the priority queue will take care of that for me at insertion time, instead of my having to manually resort at extraction time.
    • Backing data structures include heaps (and balanced binary trees).
    • Generally implemented by keeping an extra pointer to the highest priority element, so on insertion, update iff new element is higher priority, and on deletion, delete then use find-min (or find-max) to restore the pointer.
  • Popping everything from a stack and pushing it all to another stack reverses the ordering.
    Pushing everything back of course reverts the ordering.
  • Two stacks are Turing-complete.