A stack Abstract Data Type (ADT) is to be implemented using pseudocode, with procedures to initialise it and to push new items onto the stack. A 1D array Stack stores the contents of the stack.

Mark scheme

Marking points from the official mark scheme (Oct/Nov 2023). The mark or mark type is shown in brackets.

1. [1] BasePointer: INTEGER, Points to the bottom of the stack
2. [1] TopPointer: INTEGER, Points to the top of the stack
3. [1] Stack: REAL, List of decimal numbers stored in the stack
4. [1] BasePointer ← 1
5. [1] TopPointer ← 0
6. [1] IF TopPointer < MaxSize THEN
7. [1] TopPointer ← TopPointer + 1
8. [1] Stack[TopPointer] ← NewItem
9. [1] A linked list is a dynamic data structure / not restricted in size
10. [1] Has greater freedom to expand or contract by adding or removing nodes as necessary
11. [1] Allows more efficient editing using pointers (instead of moving the data).
12. [1] An array is a static data structure1 generally fixed in size
13. [1] When the array is full, the stack cannot be extended any further.
14. [1] The compiler must produce object code to
15. [1] ...push return addresses / values of local variables onto a stack
16. [1] ...with each recursive call // ... to set up winding
17. [1] ...pop return addresses / values of local variables off the stack ...
18. [1] ...after the base case is reached // ... to implement unwinding.