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

10.4 Introduction to Abstract Data Types (ADT)

Abstract Data Types (ADTs) let us think about data and operations without worrying about the low‑level details. In this section we’ll look at three classic ADTs – queue, stack and linked list – and see how they can be built on top of simple arrays. 📚

Queues – “First In, First Out” (FIFO)

Imagine a line at a coffee shop. The first person to arrive is the first to be served. A queue behaves the same way: items are enqueued at the rear and dequeued from the front.

Array implementation (circular queue)

• Two indices: front (where we remove) and rear (where we add).
• When rear reaches the end of the array, it wraps around to the start – hence “circular”.
• Use a size counter to detect full/empty conditions.

Key operations

1. enqueue(item) – add at rear, then rear = (rear + 1) mod capacity.
2. dequeue() – remove from front, then front = (front + 1) mod capacity.

Stacks – “Last In, First Out” (LIFO)

Think of a stack of plates. The last plate you put on top is the first one you take off. A stack keeps a single index, top, pointing to the current top element.

Array implementation

• Array of fixed size.
• Initially top = -1 (empty).
• Push: top++; store item at array[top].
• Pop: retrieve array[top]; then top--.

1. push(item) – add to top.
2. pop() – remove from top.
3. peek() – look at top without removing.

Linked Lists – Dynamic Chains

Picture a chain of beads. Each bead knows the next bead in the chain. In a linked list each element (node) stores data and an index (or pointer) to the next node. Using an array we can simulate this by storing nodes in an array and using an integer as the “pointer”.

Array‑based linked list

• Array nodes[capacity] where each entry holds {data, nextIndex}.
• Maintain a freeList head pointing to the first free node.
• Insert: take node from freeList, set its data, link it into the list.
• Delete: unlink node, return it to freeList.

Example: inserting at head

1. Let newNode = freeList, freeList = nodes[newNode].nextIndex.
2. Set nodes[newNode].data = value.
3. Set nodes[newNode].nextIndex = head.
4. Update head = newNode.

Exam Tips & Quick Review

Summary Table