Computational Thinking and Data Structures: Question 4

Syllabus 10.4

Structured AS 8 marks

A web browser needs to store the addresses of the pages a user has visited, so that clicking a "Back" button always returns to the most recently visited page first, then to the page visited before that, and so on.

(a) State which abstract data type, a stack or a queue, should be used to store the page addresses so that the browser's "Back" button behaves as described above, and justify your answer by referring to the order in which addresses are added and removed. [2]

(b) The browser implements this abstract data type, named PageStack, using a 1D array of up to 4 elements, DECLARE PageStack : ARRAY[1:4] OF STRING, together with an integer pointer variable Top that stores the array index of the item most recently added (Top = 0 means PageStack is currently empty). Starting from an empty PageStack, the following page visits and Back-button presses occur, in order:

Visit "Home" (PUSH)
Visit "News" (PUSH)
Visit "Sport" (PUSH)
Press Back (POP)
Visit "Weather" (PUSH)
Press Back (POP)

Complete a trace table showing the value of Top and the contents of PageStack after each of these six operations. [4]

(c) State which page address would be returned to if the user presses Back one more time, immediately after the six operations above. [1]

(d) Describe, with reference to the pointer variable Top, how the PUSH and POP operations keep PageStack behaving as a stack rather than as a queue. [1]

Show worked solution Hide worked solution

Part (a): Stack or queue?

The Back button must always return to the page visited most recently, before returning to earlier pages in reverse order of when they were visited. This is a last-in, first-out (LIFO) access pattern: the last address added is the first one removed. That is precisely the defining behaviour of a stack.

A queue would be the wrong choice here, because a queue is first-in, first-out (FIFO). It would return the oldest visited page first, which is not how a Back button works.

[2 marks]: [1] for stating “stack”, [1] for justifying it with reference to LIFO order (most recently added item removed first).

Part (b): Tracing PUSH and POP with the Top pointer

Top always stores the array index of the item most recently added. PUSH increases Top by 1 and then stores the new value at PageStack[Top]. POP reads the value currently at PageStack[Top] and then decreases Top by 1 (the array slot itself is simply left to be overwritten by a future PUSH).

Operation	Top	Contents of `PageStack` (bottom → top)
Visit “Home” (PUSH)	1	`[Home]`
Visit “News” (PUSH)	2	`[Home, News]`
Visit “Sport” (PUSH)	3	`[Home, News, Sport]`
Press Back (POP)	2	`[Home, News]`. “Sport” is returned
Visit “Weather” (PUSH)	3	`[Home, News, Weather]`
Press Back (POP)	2	`[Home, News]`. “Weather” is returned

Note that the fifth row’s PUSH "Weather" legitimately reuses array position 3 (the same position “Sport” previously occupied), because Top had returned to 2 and then increased back to 3. The old value at position 3 is simply overwritten.

[4 marks]: [1] for the correct value of Top after each of the six operations, [1] for the correct contents after the three PUSH operations, [1] for correctly removing the most recently added item on each POP (not the oldest item), [1] for the final state Top = 2, PageStack containing [Home, News].

Part (c): One more Back press

After the six operations, Top = 2, so PageStack[Top] is PageStack[2] = "News". Pressing Back once more returns to “News”, and Top would then decrease to 1. [1 mark]

Part (d): Why this keeps PageStack behaving as a stack

Both PUSH and POP only ever act at the single array position that Top identifies: PUSH moves Top up by one position and writes there, and POP reads from that same position before moving Top back down by one. Because every addition and every removal happens at this one end of the array, the most recently added item is always sitting at Top and so is always the next one removed, last-in, first-out. A queue, by contrast, would need to add items at one end (the rear) and remove them from the other end (the front), which would require two separate pointers rather than one. [1 mark]

Final answers

(a) A stack. LIFO order matches the Back button’s “most recent page first” behaviour.
(b) See the trace table above; final state after all six operations: Top = 2, PageStack containing [Home, News].
(c) “News” is returned; Top becomes 1.
(d) PUSH/POP both act only at the position Top points to, so the last item added is always the first removed (LIFO), the defining behaviour of a stack.

Common mistakes

Choosing a queue instead of a stack, because a queue is the more familiar everyday idea of 'joining a line', without checking that the Back button must return to the most RECENTLY visited page first (last in, first out), which is exactly what a stack provides, not a queue (first in, first out).
Incrementing Top only when reading a value, or decrementing it only when adding a value, reversing the roles of PUSH and POP relative to the pointer Top.
After a POP, leaving Top unchanged (still pointing at the removed item) rather than decrementing it, so that the next PUSH would overwrite the wrong array position or the stack would appear one item taller than it really is.
Believing that PageStack[3] is permanently 'Sport' once it has been popped, rather than recognising that PUSH Weather afterwards legitimately reuses (overwrites) that same array position, since Top again points to index 3.
Describing PUSH and POP as if they operate at opposite ends of the array (as a queue's ENQUEUE and DEQUEUE would), rather than recognising that both operations act only at the single end of the array indicated by Top.