Code & Robots, level 12
🥞 Stacks and Queues
How does the undo button know which change to take back first?
- How does the undo button know which change to take back first? Many programs keep a record of your changes in a stack. The NIST Dictionary of Algorithms and Data Structures defines a stack as a collection of items in which only the most recently added item may be removed, an arrangement also known as last in, first out, or LIFO. Adding an item is called pushing it onto the stack, and removing the top item is called popping it, so the only item you can ever reach directly is the one most recently added. Picture a pile of cafeteria trays: a worker sets a clean tray on top, and the next person in line takes that very tray from the top. So when you type three words and then press undo, the editor pops the most recent change first, and the last word you typed is the first one to disappear from the screen.
- A queue works in precisely the opposite way. NIST defines it as a collection of items in which only the earliest added item may be accessed, an arrangement known as first in, first out, or FIFO. Adding an item to the back of a queue is called enqueuing it, and removing the item at the front is called dequeuing it. A line of people at a ticket window behaves exactly like a queue, since whoever arrived first is served first and every newcomer joins at the back, and computers use queues whenever tasks should be handled in the order in which they arrive. When several people send documents to one shared printer, for instance, the printer handles the first document it received, then the second, and so on, so that nobody's pages jump ahead of anyone else's, which keeps the order fair for everyone waiting.
- Both structures can be built on top of a simpler one, the array, which stores items in numbered positions, usually starting at position 0. Choosing between a stack and a queue depends entirely on the order that a particular problem requires. Suppose you push A, then B, then C onto a stack; popping three times returns C, then B, then A, which is the reverse of the original order. Put the same three letters into a queue instead, and dequeuing three times returns A, then B, then C, exactly the original order. Data structures like these are tools for organizing information so that a program can do its job correctly and efficiently. The CSTA standards ask high school students to compare and contrast such fundamental data structures and their uses, because selecting the appropriate one can make a program simpler, faster and considerably easier for other people to understand.
Try it at home: Stack three books and take them off one at a time, then line up three toys and send them through a doorway, and say which was a stack and which a queue.
Questions and answers
Stacks and Queues
- A collection where only the most recently added item may be removed is called a… stack
- 🥞 What does LIFO stand for? Last in, first out
- Adding an item to the top of a stack is called… pushing (You push onto a stack and pop off its top.)
- ↩️ Why does a stack suit an undo button? It removes the most recent change first (Undo takes back your last change first, which is last in, first out.)
- A collection where only the earliest added item may be accessed is called a… queue (In a queue, only the earliest added item can be reached, like the front of a line.)
- 🧍 What does FIFO stand for? First in, first out