AS · Practice questions · Stacks, queues and linked lists

Follow the pointers.

Six original Cambridge-style questions on stacks, queues and linked lists, with pointer traces and mark points.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.

Keep these straight

Check, then move.

Stack (LIFO): push = check full, top + 1, store; pop = check empty, read, top − 1.
Queue (FIFO): add at the rear, remove from the front; circular pointers wrap with MOD; keep a count.
Linked list: node = data + pointer; start pointer, null pointer, free list.
Insert: new node's pointer first, then the previous node's pointer.

Recall

[2 marks]

Explain what is meant by an abstract data type (ADT) and name two examples.

A collection of data together with a set of operations on that data. ✓
Any two of: stack, queue, linked list. ✓

Trace

[4 marks]

A stack uses Stack : ARRAY[1:5] OF INTEGER, so an empty stack has TopOfStack = 0. Starting from empty, these operations are carried out: PUSH 12, PUSH 30, PUSH 7, POP, POP, PUSH 25, PUSH 18, PUSH 4, PUSH 9. State (a) the values returned by the POP operations, (b) the final value of TopOfStack and the contents of the stack, (c) what would happen with a further PUSH 6.

(a) 7, then 30. ✓
(b) TopOfStack = 5. ✓
(b) The stack holds 12, 25, 18, 4, 9 (bottom to top). ✓
(c) The stack is full, so stack overflow: 6 is not added. ✓

Trace

[4 marks]

A circular queue uses Queue : ARRAY[0:4] with FrontPointer = 0, RearPointer = −1 and NumberInQueue = 0. These operations are carried out: ENQUEUE 10, ENQUEUE 20, ENQUEUE 30, DEQUEUE, DEQUEUE, ENQUEUE 40, ENQUEUE 50, ENQUEUE 60. State the final values of the three variables and the next item to be dequeued.

FrontPointer = 2. ✓
RearPointer = 0 (60 wraps round into index 0). ✓
NumberInQueue = 4. ✓
The next item dequeued is 30. ✓

Explain

[4 marks]

Describe how a queue can be implemented using an array.

A 1D array holds the items, with a fixed size. ✓
A front pointer gives the index of the item to be removed next; a rear pointer gives the index of the last item added. ✓
Enqueue: check the queue is not full, move the rear pointer on and store the item; dequeue: check it is not empty, return the item at the front and move the front pointer on. ✓
Pointers wrap round to the start of the array (circular queue), and a counter records how many items are in the queue. ✓

Apply

[6 marks]

A linked list of integers in ascending order is stored using arrays, with −1 as the null pointer.

Index	Data	Pointer
0	27	2
1	9	0
2	41	−1
3		4
4		−1

StartPointer = 1 and FreeListPointer = 3. (a) 30 is inserted. Give the new contents of the Pointer array and the values of StartPointer and FreeListPointer. (b) 5 is then inserted. Give the values that change.

(a) 30 is stored in node 3; FreeListPointer becomes 4. ✓
(a) 30 goes after 27 (node 0): Pointer[3] = 2, then Pointer[0] = 3. ✓
(a) Pointer array 3, 0, −1, 2, −1; StartPointer = 1; FreeListPointer = 4. ✓
(b) 5 is stored in node 4; FreeListPointer becomes −1 (the free list is now empty). ✓
(b) 5 is smaller than the first item, so Pointer[4] = 1 (the old StartPointer). ✓
(b) StartPointer = 4. ✓

Analysis

[3 marks]

For each situation, state whether a stack, a queue or a linked list is most suitable and justify your choice: (a) the undo feature of a graphics program, (b) callers waiting to speak to a helpline, (c) a list of contacts kept in alphabetical order where contacts are often added and removed.

(a) Stack: the most recent action must be undone first (LIFO). ✓
(b) Queue: callers are answered in the order they called (FIFO). ✓
(c) Linked list: items can be inserted or deleted in order by changing pointers, without moving the other data. ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.