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.
No comments