Describe how a queue, stack and linked list can be implemented using arrays

10.4 Introduction to Abstract Data Types (ADT)

Learning Objective

Describe how a queue, stack and linked list can be implemented using arrays.

Why Use an Array for an ADT?

Arrays provide contiguous memory, constant‑time access by index and a fixed maximum size. By managing additional variables (such as front, rear, top, or next‑index), we can give the array the behaviour of higher‑level abstract data types.

1. Stack – LIFO (Last In, First Out)

A stack can be realised with a one‑dimensional array stack[0 … N‑1] and an integer top that points to the most recently inserted element.

• Initial state: top = -1 (empty stack).
• Push operation:

  1. Check if top == N‑1 (stack full). If so, raise overflow.
  2. Increment top.
  3. Assign stack[top] = value.

• Pop operation:

  1. Check if top == -1 (stack empty). If so, raise underflow.
  2. Retrieve value = stack[top].
  3. Decrement top.
  4. Return value.

• Peek operation simply returns stack[top] without modifying top.

2. Queue – FIFO (First In, First Out)

A queue can be built from an array queue[0 … N‑1] using two indices: front (position of the first element) and rear (position where the next element will be inserted). To avoid moving elements, a circular buffer is used.

• Initial state: front = 0, rear = 0, size = 0.
• Enqueue operation:

  1. If size == N, the queue is full – raise overflow.
  2. Assign queue[rear] = value.
  3. Set rear = (rear + 1) mod N.
  4. Increment size.

• Dequeue operation:

  1. If size == 0, the queue is empty – raise underflow.
  2. Retrieve value = queue[front].
  3. Set front = (front + 1) mod N.
  4. Decrement size.
  5. Return value.

• Peek operation returns queue[front] without changing indices.

3. Linked List Using an Array (Static Linked List)

A linked list can be simulated with two parallel arrays:

• data[0 … N‑1] – stores the actual element values.
• next[0 … N‑1] – stores the index of the next node (or –1 for null).

A separate variable head holds the index of the first node, and a free list (often a stack of unused indices) manages allocation.

Initialisation

for i = 0 to N‑1:
next[i] = i+1          // link all cells into a free list
next[N‑1] = -1
head = -1                  // empty list
free = 0                   // first free cell

Insert at the beginning

1. If free == -1, the array is full – raise overflow.
2. Set new = free.
3. Update free = next[free] (remove from free list).
4. Assign data[new] = value.
5. Set next[new] = head.
6. Set head = new.

Delete the first node

1. If head == -1, the list is empty – raise underflow.
2. Set del = head.
3. Update head = next[head].
4. Return the node to the free list:

   next[del] = free
   free = del
   

Comparison of Operations

Key Points to Remember

• Array‑based ADTs have a fixed maximum capacity; overflow must be handled.
• Using a circular buffer eliminates the need to shift elements in a queue.
• A static linked list trades dynamic memory allocation for predictable memory usage, useful in embedded contexts.
• All basic operations (push, pop, enqueue, dequeue, insert‑head, delete‑head) run in constant time \$O(1)\$ when the array implementation is correctly managed.