Stacks and Queues
Feb 122018A list can do everything an array can do, and more; the array data type is strictly “less useful” than the list data type. However, the array data structure is both faster and uses less memory than any list data structure.(1) This is common: if a data type supports fewer operations, then programmers who use that type have less freedom, but programmers who implement it (or choose an implementation) have more freedom. A data structure supporting fewer operations can often be more efficient in speed, memory use, or both; or, if you want more operations supported, expect a lower efficiency.
It’s therefore worth considering what other ADTs might be “less useful” than a list. Collections are often used to store items which will be processed one-by-one; in this use case, the main operations we need are to ‘put one in’ when a new item needs to be processed, and ‘take one out’ when we’re ready to process it.
There is a missing detail; when we ‘take one out’, which item should we get? We usually do want to process the items in a particular order.
Stack
A stack represents a collection with last in, first out behaviour. It supports the following operations:
- Create an empty stack.
- Push a new value
xonto the top the stack (put one in). - Pop a value from the top of the stack (take one out), removing whichever remaining value was most recently ‘pushed’, and returning it.
- Peek at whichever value would be ‘popped’ next, without removing it.
- Get the size of the stack (number of values remaining).
- Clear the stack (remove all values).
For intuition, imagine a stack of plates; when you add a new plate it goes on top of the stack, and when you take a plate it also comes from the top of the stack. You can also ‘peek’ at the top plate, but the plates below it are obscured. The plates at the top of the stack have been there shortest, and those at the bottom of the stack have been there longest.
Queue
A queue represents a collection with first in, first out, or first come, first serve behaviour. It supports the following operations:
- Create an empty queue.
- Enqueue a new value
xat the back of the queue (put one in). - Poll a value from the front of the queue (take one out), removing whichever remaining value was least recently ‘enqueued’, and returning it.
- Peek at whichever value would be ‘polled’ next, without removing it.
- Get the size of the queue (number of values remaining).
- Clear the queue (remove all values).
For intuition, imagine a queue of people waiting to be served; when a new customer arrives they join the back of the queue, and when a cashier becomes available, they serve the customer at the front of the queue. The customers at the front of the queue have been there the longest, and those at the back of the queue have been there shortest.
Priority Queue
A priority queue is a little different; the item you get when you ‘take one out’ depends on the items, rather than the order they were inserted in. Each item in a priority queue has a priority, and when you ‘take one out’ you get the one with the highest priority. The priority of an item can be represented as a number.
Warning
Perhaps confusingly, many implementations treat lower numbers as “higher” priority. These are called min-priority queues.
Priority queues support the following operations:
- Create an empty queue.
- Enqueue a new value
xwith priorityp(put one in). - Poll a value from the priority queue (take one out), removing whichever remaining value has the highest priority, and returning it.
- Peek at whichever value would be ‘polled’ next, without removing it.
- Get the size of the priority queue (number of values remaining).
- Clear the priority queue (remove all values).
For intuition, imagine a queue of people waiting at an accident-and-emergency clinic. When a doctor becomes available, they will treat whichever patient requires the most urgent treatment.
Footnotes
- In fact, for most purposes the most efficient list data structure is one which uses an array.
Comments