EnglandComputer ScienceSyllabus dot point

How do stacks, queues and linked lists work, and how are they implemented and used?

Dynamic data structures: stacks (LIFO) and queues (FIFO) with their push, pop, enqueue and dequeue operations and pointer management, linear and circular queues, and singly and doubly linked lists with insertion and deletion.

An Eduqas Component 1 answer on stacks, queues and linked lists: LIFO and FIFO behaviour, push, pop, enqueue and dequeue with pointer management, the wrap-around in a circular queue, and inserting and deleting nodes in a linked list.

Generated by Claude Opus 4.814 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Quick answer

A stack is a last-in, first-out (LIFO) structure: you push onto the top and pop from the top, controlled by a single top pointer. A queue is a first-in, first-out (FIFO) structure: you enqueue at the rear and dequeue from the front, controlled by front and rear pointers. A circular queue treats its array as a ring so freed front slots are reused, wrapping the rear pointer with $\text{rear} \leftarrow (\text{rear} + 1) \bmod \text{size}$ . A linked list stores each item in a node holding the data plus a pointer to the next node; a head pointer marks the start and the last node points to null. Inserting or deleting a node only changes a couple of pointers, so a linked list grows and shrinks freely, but you must traverse from the head to reach an item, giving $O(n)$ access rather than the array's $O(1)$ .

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

Eduqas wants you to describe stacks and queues, their operations and pointer management, the wrap-around in a circular queue, and how a linked list inserts and deletes nodes by changing pointers. These are the core dynamic structures: unlike a fixed array, they model data that grows and shrinks.

The answer

Stacks (LIFO)

Queues (FIFO) and circular queues

Linked lists

Trace a stack and a linked-list insertion

Start with an empty stack (top $= -1$ ), then push(7), push(3), pop(), push(9). Then insert a node into a linked list between two existing nodes.

step 1: Apply the stack operations

push(7): top becomes $0$ , stack is $[7]$ . push(3): top becomes $1$ , stack is $[7, 3]$ . pop(): returns $3$ , top becomes $0$ , stack is $[7]$ . push(9): top becomes $1$ , stack is $[7, 9]$ .

step 2: State the final stack

The stack holds $[7, 9]$ with $9$ on top, because the most recent push that was not popped sits on top (LIFO).

step 3: Insert into a linked list

To insert node N between nodes A and B (where A.next currently points to B): set N.next <- A.next (so N points to B), then set A.next <- N.

step 4: Note the order of the two pointer updates

Point the new node at B first, then point A at the new node. Reversing the order would lose the link to B and orphan the rest of the list.

Examples in context

The call stack is a stack: each function call pushes a frame and each return pops one, which is exactly why infinite recursion causes a stack overflow. A print spooler is a queue: documents print in submission order. A circular buffer (a circular queue) backs streaming audio so freed slots are reused continuously. Linked lists underpin structures that change size a lot, such as the chains in a hash table or the adjacency lists of a graph, both of which Eduqas covers in the next dot point.

Try this

Q1. State the order of removal for a stack and for a queue. [2 marks]

Cue. Stack: last in, first out (LIFO). Queue: first in, first out (FIFO).

Q2. A circular queue of size $8$ has its rear pointer at index $7$ . After one more enqueue, what is the rear index? [1 mark]

Cue. $(7 + 1) \bmod 8 = 0$ .

Q3. Give one advantage and one disadvantage of a linked list compared with an array. [2 marks]

Cue. Advantage: grows and shrinks at run time with cheap insertion and deletion. Disadvantage: no direct indexing, so reaching an item needs an $O(n)$ traversal from the head.

Exam-style practice questions

Practice questions written in the style of WJEC Eduqas exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Eduqas 20206 marksA stack is implemented in an array with a top pointer initially set to

-1

. Describe, using pseudocode, the push and pop operations, including how an overflow and an underflow are detected.

Show worked answer →

Push (up to 3 marks): check for overflow first, then increment the pointer, then store the value.

PROCEDURE push(value)
    IF top = maxIndex THEN
        REPORT "stack overflow"
    ELSE
        top <- top + 1
        stack[top] <- value
    ENDIF
ENDPROCEDURE

Pop (up to 3 marks): check for underflow first, then read the value, then decrement.

FUNCTION pop()
    IF top = -1 THEN
        REPORT "stack underflow"
    ELSE
        value <- stack[top]
        top <- top - 1
        RETURN value
    ENDIF
ENDFUNCTION

Markers reward incrementing the pointer before storing on push, decrementing after reading on pop, and the overflow (top at the maximum) and underflow (top at $-1$ ) checks.

Eduqas 20224 marksExplain why a circular queue is often preferred to a linear queue implemented in an array, and describe how the rear pointer wraps around.

Show worked answer →

In a linear array queue, repeated enqueues and dequeues move both pointers towards the end, so the front of the array becomes unusable even when the queue is not full, wasting space (up to 2 marks).

A circular queue treats the array as a ring: when the rear pointer reaches the last index, the next enqueue sets it back to index $0$ using modulo arithmetic, $\text{rear} \leftarrow (\text{rear} + 1) \bmod \text{size}$ , so the freed front slots are reused (up to 2 marks).

Markers reward the wasted-space problem of the linear queue and the modulo wrap-around of the circular queue. A full-or-empty distinction (using a counter or a spare slot) earns credit too.

Related dot points

Sources & how we know this

WJEC Eduqas GCE AS/A Level Computer Science specification (from 2015) — Eduqas (2015)