Stacks and queues

Stacks and queues are containers defined by which item comes out next. A stack is like a pile of plates: you add and remove from the top, so the newest item leaves first. A queue is like a line at a shop: you join at the back and leave from the front, so the oldest item leaves first. Both make adding and removing constant time. Stacks show up in function calls, undo history and matching brackets; queues show up in task schedulers, message buffers and breadth-first search. A ring buffer is a fixed-size queue stored in an array whose front and back positions wrap around to the start.