Introduction to Abstract Data Types (ADT) — stack, queue, linked list

An Abstract Data Type (ADT) is a mathematical model that defines:

• A collection of data (the structure)
• A set of operations that can be performed on that data

The key word is abstract — the ADT specifies what operations exist and what they do, but not how they are implemented. The implementation details (arrays, pointers, etc.) are hidden from the user.

Why ADTs matter:

• Separation of concerns: users don't need to know internal details
• Reusability: same ADT can have different implementations
• Maintainability: change implementation without affecting code that uses the ADT

Cambridge ADTs in topic 10.4: Stack, Queue, Linked List.

A stack stores items so that the last item added is the first removed (like a stack of plates).

Key operations:

• push(item) — add item to top
• pop() — remove and return top item
• peek() / top() — view top item without removing
• isEmpty() — check if stack has no items
• isFull() — check if stack has reached capacity (for bounded stacks)

Pseudocode example:

// Stack using array with fixed size
DECLARE stack : ARRAY[1:100] OF INTEGER
DECLARE top : INTEGER
top <- 0

PROCEDURE push(value : INTEGER)
  IF top = 100 THEN OUTPUT "Stack overflow" ELSE
    top <- top + 1
    stack[top] <- value
  ENDIF
ENDPROCEDURE

PROCEDURE pop() RETURNS INTEGER
  IF top = 0 THEN OUTPUT "Stack underflow" ELSE
    RETURN stack[top]
    top <- top - 1
  ENDIF
ENDPROCEDURE

Common uses: Function call stack, undo operations, expression evaluation, backtracking algorithms, browser history.

A queue stores items so that the first item added is the first removed (like a queue of people).

Key operations:

• enqueue(item) — add item to rear
• dequeue() — remove and return front item
• front() / peek() — view front item without removing
• isEmpty() — check if queue has no items
• isFull() — check if queue has reached capacity

Pseudocode example (circular array):

DECLARE queue : ARRAY[1:100] OF INTEGER
DECLARE front, rear : INTEGER
DECLARE count : INTEGER
front <- 1
rear <- 0
count <- 0

PROCEDURE enqueue(value : INTEGER)
  IF count = 100 THEN OUTPUT "Queue full" ELSE
    rear <- (rear MOD 100) + 1
    queue[rear] <- value
    count <- count + 1
  ENDIF
ENDPROCEDURE

PROCEDURE dequeue() RETURNS INTEGER
  IF count = 0 THEN OUTPUT "Queue empty" ELSE
    value <- queue[front]
    front <- (front MOD 100) + 1
    count <- count - 1
    RETURN value
  ENDIF
ENDPROCEDURE

Common uses: Print spoolers, task scheduling, breadth-first search, buffering data streams.

A linked list is a sequence of nodes, where each node contains:

• Data (the value)
• Pointer/Reference to the next node

The list is accessed via a pointer to the head (first node). The last node's pointer is NULL.

Key operations:

• Insert at front, end, or middle
• Delete from front, end, or middle
• Search for a value
• Traverse (visit each node in order)

Pseudocode structure:

TYPE NodePtr = POINTER TO Node
TYPE Node = RECORD
  data : INTEGER
  next : NodePtr
ENDRECORD

DECLARE head : NodePtr
head <- NULL

// Insert at front
PROCEDURE insertFront(value : INTEGER)
  DECLARE newNode : NodePtr
  NEW(newNode)
  newNode^.data <- value
  newNode^.next <- head
  head <- newNode
ENDPROCEDURE

// Traverse and print
PROCEDURE printList()
  DECLARE current : NodePtr
  current <- head
  WHILE current != NULL
    OUTPUT current^.data
    current <- current^.next
  ENDWHILE
ENDPROCEDURE

Variants: Singly linked (shown), doubly linked (prev + next), circular.

Stack with array:

• Use an array and an integer top (index of top element)
• push increments top, stores value
• pop returns value at top, decrements top
• Fixed maximum size (unless dynamic array)

Queue with array (circular buffer):

• Use an array, front index, rear index, and count
• enqueue adds at rear, wraps around with MOD
• dequeue removes from front, wraps around
• Avoids shifting elements on every dequeue

Linked list with arrays (parallel arrays):

• Two arrays: data[] for values, next[] for "pointers" (indices)
• head stores index of first node (0 = NULL)
• free list tracks available slots
• Example:

  DECLARE data : ARRAY[1:100] OF INTEGER
  DECLARE next : ARRAY[1:100] OF INTEGER
  DECLARE head, free : INTEGER
  head <- 0
  free <- 1
  FOR i <- 1 TO 99: next[i] <- i+1 ENDFOR
  next[100] <- 0
  
  // Allocate node: take from free list
  // Free node: return to free list
  

Trade-offs:

• Array implementations: fixed size, fast access, simple memory
• Pointer implementations: dynamic size, extra memory for pointers