QUESTION 21

Distinguish a stack and a queue.

2 marks

Answer

A stack removes the most recently inserted remaining item; a queue removes the earliest inserted remaining item. Their ADTs expose different access orders.

Compare stacks and queues and explain a queue implemented using two stacks.

5 marks

Answer in brief

Stacks implement LIFO while ordinary queues implement FIFO.

Example

After inserting 10, 20 and 30, a stack pop returns 30 and a queue dequeue returns 10. Stack operations use top. Queue insertion uses rear and removal uses front. Neither rule requires numerical sorting.

Applications

Undo and nested expression processing fit stacks. Arrival-order jobs and BFS fit queues. Either ADT may use arrays or linked nodes; the access rule does not depend on one memory layout.

Two-stack queue

Keep an input stack and an output stack.
Enqueue pushes onto the input stack.
For dequeue, if output is empty, transfer every input item to output by repeated pop/push.
Pop output; if both are empty, report underflow.

Why it works

The transfer reverses input order so the earliest remaining item reaches output’s top. Keep using output until it empties before another transfer. Moving input on every dequeue regardless of output state would not follow this algorithm.

Complexity

One dequeue can require O(n) transfer work. Across a sequence of operations, each item moves from input to output at most once and is then removed, giving O(1) amortised stack-operation work per queue operation. This is not a claim that every individual dequeue is worst-case constant. The stored items need O(n) space, and bounded stacks still need a capacity policy.

Reference table

↔ Scroll horizontally on a small screen

Stack and queue
Feature	Stack	Ordinary queue
Rule	LIFO	FIFO
Insert	Top	Rear
Remove	Top	Front
Example	Undo	Arrival-order service