Trace a Sequence of Stack and Queue Operations

Apply each operation to the whole structure and write down what is left.

Tracing a sequence of stack or queue operations means applying them one at a time and writing down the whole structure after each, so that the final state, and every value removed on the way, can be read off the page. This card covers that procedure on a stack and on a queue, and the mistake of reading a stack from the wrong end.

The goal is the final contents of each structure and the value each removal returns, for two short sequences. On a stack: push 1, push 2, pop, push 3. On a queue: enqueue 1, enqueue 2, dequeue, enqueue 3. The only prerequisites are the two rules: push, pop and peek work at the top of a stack, and dequeue and peek work at the front of a queue, while enqueue adds at the back.

Write each structure on one line, in the order its items will leave: a stack from its top, a queue from its front. The next item to leave is then always the first one on the line, and no step depends on remembering which end is which.

Before the steps: what does each structure hold at the end, read in the order its items will leave?

The stack holds 3 then 1, and the queue holds 2 then 3. The pop returned 2 and the dequeue returned 1.

A run printed each structure after every operation:

Each structure after every operation

Push 1

The stack holds one item, which is both its top and its bottom.

text

stack, top first: 1

Push 2

2 goes on top, so it is written first.

text

stack, top first: 2 1

Pop

Pop removes the top item, 2, and returns it. 1 is on top again.

text

stack, top first: 1

Push 3

3 goes on top of the 1.

text

stack, top first: 3 1

Enqueue 1

The queue holds one item, at its front and at its back.

text

queue, front first: 1

Enqueue 2

2 joins at the back, so it is written last.

text

queue, front first: 1 2

Dequeue

Dequeue removes the front item, 1, and returns it.

text

queue, front first: 2

Enqueue 3

3 joins behind the 2.

text

queue, front first: 2 3

The trace is right when every removal agrees with its rule: the pop returned the item pushed most recently among those still there, and the dequeue returned the one enqueued earliest. Counting is a second check. Each sequence added three items and removed one, so each structure ends with two.

The usual mistake is to write a stack the way it was filled, bottom first, as 1 3, and then take the first item on the line as the next to leave. Read that way, the stack behaves like a queue: a further pop seems to return 1, and it returns 3. Writing the top first, every time, leaves no room to confuse the two.

← → move through sections and cards