Abstract Data Types (ADTs)
1. The Stack (LIFO)
A Stack uses a TopPointer. We initialize the array with a "null" value (like 0 or empty string) to simulate fixed memory.
# SETUP
stack = [None] * 10 # Fixed size array
top_pointer = -1 # -1 means stack is empty
# ADD (PUSH)
def push(item):
global top_pointer
if top_pointer < 9:
top_pointer += 1
stack[top_pointer] = item
else:
print("Stack Overflow")
# REMOVE (POP)
def pop():
global top_pointer
if top_pointer == -1:
print("Stack Underflow")
return None
else:
item = stack[top_pointer]
top_pointer -= 1
return item
# SEARCH
def search_stack(target):
for i in range(top_pointer + 1):
if stack[i] == target:
return i # Return index
return -1
2. The Linear Queue (FIFO)
Requires a FrontPointer (to remove) and a RearPointer (to add).
# SETUP
queue = [None] * 10
front_ptr = 0
rear_ptr = -1
size = 0
# ADD (ENQUEUE)
def enqueue(item):
global rear_ptr, size
if size < 10:
rear_ptr += 1
queue[rear_ptr] = item
size += 1
else:
print("Queue Full")
# REMOVE (DEQUEUE)
def dequeue():
global front_ptr, size
if size == 0:
print("Queue Empty")
return None
else:
item = queue[front_ptr]
front_ptr += 1
size -= 1
return item
3. Circular Queue
A Circular Queue uses the full capacity of the array by wrapping the Rear and Front pointers back to index 0 when they reach the end.
# SETUP
queue = [None] * 10
front_ptr = 0
rear_ptr = -1
size = 0
max_size = 10
# ADD (ENQUEUE)
def enqueue(item):
global rear_ptr, size
if size < max_size:
# Use modulo to wrap pointer back to 0 if it hits 10
rear_ptr = (rear_ptr + 1) % max_size
queue[rear_ptr] = item
size += 1
else:
print("Queue Full")
# REMOVE (DEQUEUE)
def dequeue():
global front_ptr, size
if size == 0:
print("Queue Empty")
return None
else:
item = queue[front_ptr]
# Use modulo to wrap pointer back to 0
front_ptr = (front_ptr + 1) % max_size
size -= 1
return item
# SEARCH
def search_circular(target):
for i in range(size):
# Calculate actual index based on offset from front
idx = (front_ptr + i) % max_size
if queue[idx] == target:
return idx
return -1
⚠️ Exam Alert: When searching a Circular Queue, students often forget that the index they are looking for might be lower than the
front_ptr if wrapping has occurred. Always use the (front_ptr + i) % max_size formula to traverse it correctly.
4. Linked List (Static Array Method)
In Paper 4, you must often use a class to represent a Node and an array of objects to represent the list.
class Node:
def __init__(self, data, next_node):
self.data = data
self.next = next_node
# SETUP: Initialize array with empty nodes pointing to the next free slot
linked_list = [Node("", i + 1) for i in range(9)]
linked_list.append(Node("", -1)) # End of free list
start_ptr = -1
free_ptr = 0
# ADD (INSERT AT FRONT)
def insert(new_data):
global free_ptr, start_ptr
if free_ptr != -1:
new_node_idx = free_ptr
# Update free pointer to the next available slot
free_ptr = linked_list[free_ptr].next
# Place data and point to current start
linked_list[new_node_idx].data = new_data
linked_list[new_node_idx].next = start_ptr
start_ptr = new_node_idx
else:
print("No free space")
# SEARCH
def find(target):
current = start_ptr
while current != -1:
if linked_list[current].data == target:
return current
current = linked_list[current].next
return -1
# DELETE
def delete(target):
global start_ptr, free_ptr
current = start_ptr
prev = -1
while current != -1 and linked_list[current].data != target:
prev = current
current = linked_list[current].next
if current != -1: # Found it
if prev == -1: # Node is at the start
start_ptr = linked_list[current].next
else:
linked_list[prev].next = linked_list[current].next
# Return the deleted node back to the Free List
linked_list[current].next = free_ptr
free_ptr = current
⚠️ Teacher's Note: The
global keyword is mandatory in Python when modifying the pointers defined outside the function scope. Without it, Python creates a local variable instead of updating the global pointer, breaking the ADT logic.