Stacks, queues and linked lists
Three ways to keep items in order
- AS topic 10.4: a stack, a queue and a linked list are abstract data types (ADTs). You must use them and say how an array can store them.
- A stack is like a pile of plates: you add and remove at the top only. The last item in is the first out (LIFO).
- A queue is like a line at the canteen: you join at the rear and leave at the front. The first item in is the first out (FIFO).
- In a linked list, each item stores a pointer to the next item. The items can sit anywhere in memory.

The same three items leave a stack and a queue in opposite orders.
A stack in an array
- Store the items in
Stack : ARRAY[1:5]. A pointer,TopOfStack, holds the index of the top item. It is0when the stack is empty. - Push: if
TopOfStack = 5the stack is full. Otherwise add 1 toTopOfStack, then store the item there. - Pop: if
TopOfStack = 0the stack is empty. Otherwise readStack[TopOfStack], then subtract 1. - A pop does not clear the cell. The old value stays, but it is no longer part of the stack.
![Four snapshots of Stack[1:5]: empty with TopOfStack 0; after pushing 4 and 9 TopOfStack is 2; after pushing 7 it is 3; popping returns 7 and TopOfStack is 2 again](/static/code/as-pseudocode/stack-array.png)
DECLARE Stack : ARRAY[1:5] OF INTEGER
DECLARE TopOfStack : INTEGER
TopOfStack ← 0
PROCEDURE Push(Item : INTEGER)
IF TopOfStack = 5 THEN
OUTPUT "Stack full"
ELSE
TopOfStack ← TopOfStack + 1
Stack[TopOfStack] ← Item
ENDIF
ENDPROCEDURE
FUNCTION Pop() RETURNS INTEGER
DECLARE Item : INTEGER
IF TopOfStack = 0 THEN
OUTPUT "Stack empty"
RETURN -1
ELSE
Item ← Stack[TopOfStack]
TopOfStack ← TopOfStack - 1
RETURN Item
ENDIF
ENDFUNCTION
CALL Push(4)
CALL Push(9)
CALL Push(7)
OUTPUT Pop()
OUTPUT Pop()
OUTPUT "TopOfStack = ", TopOfStack
- The output is
7, then9, thenTopOfStack = 1: the items come back in the opposite order. StackandTopOfStackare declared outside the modules, soPushandPopshare them.
A queue in an array
- Store the items in
Queue : ARRAY[1:4].FrontPointerholds the index of the first item andRearPointerthe index of the last. - Enqueue (join): add 1 to
RearPointer, then store the item there. Dequeue (leave): readQueue[FrontPointer], then add 1 toFrontPointer. - Both pointers only move forward, so the front cells become free. A circular queue reuses them: a pointer that passes the last cell goes back to 1.
- A counter,
NumberInQueue, tells a full queue (4) from an empty one (0).
![Queue[1:4] in three snapshots: Ann, Ben, Cat with Front 1 and Rear 3; after a dequeue and Dev joining, Front is 2 and Rear 4; Eve joins in cell 1 because the rear wraps](/static/code/as-pseudocode/queue-circular.png)
DECLARE Queue : ARRAY[1:4] OF STRING
DECLARE FrontPointer, RearPointer, NumberInQueue : INTEGER
FrontPointer ← 1
RearPointer ← 0
NumberInQueue ← 0
PROCEDURE Enqueue(Item : STRING)
IF NumberInQueue = 4 THEN
OUTPUT "Queue full"
ELSE
RearPointer ← RearPointer + 1
IF RearPointer > 4 THEN
RearPointer ← 1
ENDIF
Queue[RearPointer] ← Item
NumberInQueue ← NumberInQueue + 1
ENDIF
ENDPROCEDURE
FUNCTION Dequeue() RETURNS STRING
DECLARE Item : STRING
IF NumberInQueue = 0 THEN
RETURN "empty"
ENDIF
Item ← Queue[FrontPointer]
FrontPointer ← FrontPointer + 1
IF FrontPointer > 4 THEN
FrontPointer ← 1
ENDIF
NumberInQueue ← NumberInQueue - 1
RETURN Item
ENDFUNCTION
CALL Enqueue("Ann")
CALL Enqueue("Ben")
CALL Enqueue("Cat")
OUTPUT Dequeue()
CALL Enqueue("Dev")
CALL Enqueue("Eve")
OUTPUT "Eve is in cell ", RearPointer
OUTPUT Dequeue()
- The output is
Ann, thenEve is in cell 1, thenBen. Ann left first because she joined first.
A queue: join at the rear, leave at the front
The first item in is the first item out.
A linked list in two arrays
Dataholds the items.NextPointerholds, for each cell, the index of the next item.StartPointerholds the index of the first item. A pointer of0means "no next item": the list ends there. (Some papers use-1for this null pointer. Use the value the question gives.)- To read the list in order, start at
StartPointerand follow the pointers until you reach0. The order of the cells does not matter. - The unused cells form a second list, the free list, which starts at
FreePointer.

DECLARE Data : ARRAY[1:5] OF STRING
DECLARE NextPointer : ARRAY[1:5] OF INTEGER
DECLARE StartPointer, Current : INTEGER
Data[1] ← "Kim"
NextPointer[1] ← 3
Data[2] ← "Ali"
NextPointer[2] ← 4
Data[3] ← "Sam"
NextPointer[3] ← 0
Data[4] ← "Jo"
NextPointer[4] ← 1
StartPointer ← 2
Current ← StartPointer
WHILE Current <> 0
OUTPUT Data[Current]
Current ← NextPointer[Current]
ENDWHILE
- The output is
Ali,Jo,Kim,Sam: alphabetical order, although the cells are not in that order. Current ← NextPointer[Current]is the step that moves along the list.
Insert into a linked list
- To add "Lee" after "Kim", take a free cell (cell 5), store "Lee" in it, then change two pointers. No item moves.
- The new node points to the item that was after Kim:
NextPointer[5] ← NextPointer[1], which is 3. - Kim points to the new node:
NextPointer[1] ← 5.
- The new node points to the item that was after Kim:
- Do step 1 first. If Kim's pointer changes first, the index of Sam is lost.
- To delete an item, make the item before it point to the item after it. The freed cell goes back to the free list.
![Inserting Lee in free cell 5 after Kim: first NextPointer[5] becomes 3 so Lee points to Sam, then NextPointer[1] becomes 5 so Kim points to Lee](/static/code/as-pseudocode/list-insert.png)
Two pointers change; nothing moves.
Common mistakes
| Wrong | Right | Why |
|---|---|---|
store, then add 1 to TopOfStack |
add 1, then store | TopOfStack points at the top item, so the new item goes one above it |
push without testing TopOfStack = 5 |
test for full first | the item would be written past the end of the array |
| a queue whose pointers never wrap | IF RearPointer > 4 THEN RearPointer ← 1 |
the free cells at the front are never used again |
read the linked list as Data[1], Data[2], … |
start at StartPointer and follow NextPointer |
the cells are not in list order |
| change the old node's pointer first | set the new node's pointer first | the rest of the list would be lost |
Now you try
- Draw the array and the pointers on paper first. Write each pointer's value after every operation.
Independent transfer
The final task gives you a list stored in two arrays. Plan how you will follow the pointers, then solve it before opening support. Check that an empty list (start pointer 0) outputs nothing.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Stack : ARRAY[1:5] starts empty, so TopOfStack is(是) 0. Then: push 6, push 2, pop, push 8, push 5, pop. Give TopOfStack, then the value at the top of the stack, separated by a space.
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
A circular queue in Queue : ARRAY[1:4] starts with FrontPointer ← 1, RearPointer ← 0, NumberInQueue ← 0. Then: enqueue A, B, C, D; dequeue twice; enqueue E. Give FrontPointer, then RearPointer, separated by a space.
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
The linked list in Fruit and NextPointer starts at StartPointer. A pointer of 0 ends the list. Output the items in list order, one per line.
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
Read five items into Data[1:5], then five pointers into NextPointer[1:5], then StartPointer. A pointer of 0 ends the list, and a StartPointer of 0 means the list is empty. Output the items in list order, one per line, then the line N items, where N is how many items the list holds.
点击“运行”查看此处输出。