Basics 0/97

Stacks and queues · 1 of 2

Stack and queue basics

Tell a stack from a queue, use both in code, and solve bracket matching, nested repeats and a running minimum with a stack.

3,528 words · 16 min read

Part 1 of 7 Stacks and queues

Newest first or oldest first

Type a, b and c in a text editor and press Undo three times. The editor takes back c, then b, then a: the newest change is undone first. Now send three documents a, b and c to a printer. They come out as a, b, c: the oldest job is printed first.

Both programs hold items that are waiting to be handled, and both received a, b and c in the same order. They differ in which waiting item they hand back next. The editor keeps its changes in a stack, and the printer keeps its jobs in a queue.

Definition

A stack removes the item that was added most recently. A queue removes the item that was added earliest.

A stack uses one end, called the top, like a stack of plates: a plate is put on the top and taken from the top, so the plate taken is the one put there last. Adding an item on top is a push and removing the top item is a pop. This order is called last in, first out, or LIFO.

A queue uses two ends, like the line at a shop's checkout. Items join at the back and leave from the front, so they leave in the order they arrived: first in, first out, or FIFO. Adding to a queue is also called enqueue, and removing from it dequeue.

Give a stack and a queue the same items

In the widget, push 1, 2 and 3 onto the stack, enqueue 1, 2 and 3 into the queue, and then remove everything from both. The stack's Removed row reads 3, 2, 1 and the queue's reads 1, 2, 3.

Stack

last in, first out

empty

Removed·

Queue

first in, first out

empty

Removed·

Which of the two a program needs depends on which waiting item has to be handled next. A stack fits when the item that arrived last must be finished first. Undo is one case. Function calls are another: when f calls g, g has to return before f can continue, which is why the record of running calls is named the call stack. A queue fits when items must be handled in the order they arrived, like the print jobs, or customers waiting in a line.