Abstract Data Types (ADTs)
What is an ADT?
An ADT is a "logical" model of a data structure. It defines what the data can do (e.g., Push/Pop) rather than how it is stored in memory. In A-Level, we use physical Arrays to build these logical models.
An ADT is a "logical" model of a data structure. It defines what the data can do (e.g., Push/Pop) rather than how it is stored in memory. In A-Level, we use physical Arrays to build these logical models.
1. The Stack (LIFO)
A Stack is a Last-In, First-Out structure. Imagine a stack of books; you can only add or remove from the very top. It is primarily used for managing Interrupts, Recursion, and "Undo" functions.
- LIFO: The last item added is the first one removed.
- Pointers: Uses a single TopPointer.
- Overflow: Occurs when you try to PUSH to a full stack.
- Underflow: Occurs when you try to POP from an empty stack.
Implementation Logic
DECLARE Stack : ARRAY[1:10] OF INTEGER
DECLARE TopPointer : INTEGER
TopPointer ← 0 // Base case: Stack is empty
PROCEDURE Push(NewItem)
IF TopPointer = 10 THEN
OUTPUT "Stack Overflow Error"
ELSE
TopPointer ← TopPointer + 1
Stack[TopPointer] ← NewItem
ENDIF
ENDPROCEDURE
FUNCTION Pop() RETURNS INTEGER
IF TopPointer = 0 THEN
OUTPUT "Stack Underflow Error"
RETURN -1
ELSE
Value ← Stack[TopPointer]
TopPointer ← TopPointer - 1
RETURN Value
ENDIF
ENDFUNCTION
DECLARE TopPointer : INTEGER
TopPointer ← 0 // Base case: Stack is empty
PROCEDURE Push(NewItem)
IF TopPointer = 10 THEN
OUTPUT "Stack Overflow Error"
ELSE
TopPointer ← TopPointer + 1
Stack[TopPointer] ← NewItem
ENDIF
ENDPROCEDURE
FUNCTION Pop() RETURNS INTEGER
IF TopPointer = 0 THEN
OUTPUT "Stack Underflow Error"
RETURN -1
ELSE
Value ← Stack[TopPointer]
TopPointer ← TopPointer - 1
RETURN Value
ENDIF
ENDFUNCTION
2. The Linear Queue (FIFO)
A Queue is a First-In, First-Out structure. Think of a line at a supermarket. It is used in Print Buffers and IO scheduling.
- FIFO: The first item added is the first one removed.
- Pointers: Uses FrontPointer (to remove) and RearPointer (to add).
- Size: We track the current number of items to detect Full/Empty states easily.
Implementation Logic
DECLARE Queue : ARRAY[1:10] OF STRING
DECLARE FrontPointer, RearPointer, Size : INTEGER
FrontPointer ← 1 : RearPointer ← 0 : Size ← 0
PROCEDURE Enqueue(NewItem)
IF Size = 10 THEN
OUTPUT "Queue Full"
ELSE
RearPointer ← RearPointer + 1
Queue[RearPointer] ← NewItem
Size ← Size + 1
ENDIF
ENDPROCEDURE
DECLARE FrontPointer, RearPointer, Size : INTEGER
FrontPointer ← 1 : RearPointer ← 0 : Size ← 0
PROCEDURE Enqueue(NewItem)
IF Size = 10 THEN
OUTPUT "Queue Full"
ELSE
RearPointer ← RearPointer + 1
Queue[RearPointer] ← NewItem
Size ← Size + 1
ENDIF
ENDPROCEDURE
3. The Linked List
A Linked List is a dynamic ADT. Items do not have to be stored in order in memory because each Node tells you where the next one is located via a pointer.
| Term | Definition |
|---|---|
| Node | A record containing the Data and a Pointer. |
| StartPointer | Points to the index of the first actual item. |
| FreePointer | Points to the first available empty slot in the array. |
| Null (-1) | Indicates the end of the list. |
Implementation Logic
// Define the structure
TYPE Node
DECLARE Data : STRING
DECLARE NextNode : INTEGER
ENDTYPE
DECLARE List : ARRAY[0:5] OF Node
DECLARE StartPointer, FreePointer : INTEGER
// Initialize the list pointers
PROCEDURE Initialise()
FOR i ← 0 TO 4
List[i].NextNode ← i + 1
NEXT i
List[5].NextNode ← -1
FreePointer ← 0 : StartPointer ← -1
ENDPROCEDURE
PROCEDURE AddNode(NewData)
IF FreePointer = -1 THEN
OUTPUT "Overflow"
ELSE
newNodeIndex ← FreePointer
FreePointer ← List[FreePointer].NextNode
List[newNodeIndex].Data ← NewData
List[newNodeIndex].NextNode ← StartPointer
StartPointer ← newNodeIndex
ENDIF
ENDPROCEDURE
TYPE Node
DECLARE Data : STRING
DECLARE NextNode : INTEGER
ENDTYPE
DECLARE List : ARRAY[0:5] OF Node
DECLARE StartPointer, FreePointer : INTEGER
// Initialize the list pointers
PROCEDURE Initialise()
FOR i ← 0 TO 4
List[i].NextNode ← i + 1
NEXT i
List[5].NextNode ← -1
FreePointer ← 0 : StartPointer ← -1
ENDPROCEDURE
PROCEDURE AddNode(NewData)
IF FreePointer = -1 THEN
OUTPUT "Overflow"
ELSE
newNodeIndex ← FreePointer
FreePointer ← List[FreePointer].NextNode
List[newNodeIndex].Data ← NewData
List[newNodeIndex].NextNode ← StartPointer
StartPointer ← newNodeIndex
ENDIF
ENDPROCEDURE
⚠️ Teacher's Demo Tip:
When using your pseudocode interpreter, emphasize that the index of the array does not represent the order of the list. The pointers are the only thing that matters. This is the hardest "mental jump" for students coming from IGCSE.