Data Structures: Arrays, Records, Stacks and Queues

A data structure is an organised way of storing and managing data so that it can be accessed and modified efficiently. Choosing the right data structure is essential for writing effective programs.

---

Arrays

An array is a collection of elements of the same data type, stored in contiguous (consecutive) memory locations. Each element is accessed using an index (a number that indicates its position).

Key Features of Arrays

• Fixed size — the size of an array is usually defined when it is created
• Same data type — all elements must be the same type (e.g., all integers or all strings)
• Indexed — elements are accessed by their position (index), usually starting from 0

Example

names = ["Alice", "Bob", "Charlie", "Diana"]

Index	0	1	2	3
Value	Alice	Bob	Charlie	Diana

• names[0] returns "Alice"
• names[2] returns "Charlie"

One-Dimensional and Two-Dimensional Arrays

A one-dimensional (1D) array is a single list of values:

scores = [85, 92, 78, 90]

A two-dimensional (2D) array is like a table (rows and columns):

grid = [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]

• grid[0][1] returns 2 (row 0, column 1)
• grid[2][0] returns 7 (row 2, column 0)

Exam Tip: When asked about 2D arrays, think of them as a table. The first index selects the row and the second index selects the column.

---

Records

A record is a data structure that stores a collection of related fields, which can be of different data types. Records are used to represent a single entity with multiple attributes.

Example

A student record might contain:

Field	Data Type	Example
name	String	"Alice Smith"
age	Integer	15
year_group	Integer	11
email	String	"alice@school.com"

In pseudocode, you might access a record like this:

student.name = "Alice Smith"
student.age = 15
student.year_group = 11
student.email = "alice@school.com"

Records differ from arrays because:

• Arrays store elements of the same type; records store different types
• Array elements are accessed by index; record fields are accessed by name

---

Stacks

A stack is a Last In, First Out (LIFO) data structure. The last item added to the stack is the first one to be removed — just like a stack of plates.

The control flow of stack operations is summarised below:

graph TD
    A["Stack operation"] --> B{"Operation type?"}
    B -->|Push| C{"Stack full?"}
    C -->|Yes| D["Stack overflow error"]
    C -->|No| E["Add item to top"]
    B -->|Pop| F{"Stack empty?"}
    F -->|Yes| G["Stack underflow error"]
    F -->|No| H["Remove and return top item"]
    B -->|Peek| I["Return top item without removing"]

Key Operations

Operation	Description
Push	Add an item to the top of the stack
Pop	Remove and return the item from the top of the stack
Peek (or Top)	View the top item without removing it
isEmpty	Check if the stack is empty
isFull	Check if the stack is full (for fixed-size stacks)

Example: Stack Operations

Starting with an empty stack:

Operation	Stack (top → bottom)	Returned Value
Push(5)	[5]	—
Push(3)	[3, 5]	—
Push(8)	[8, 3, 5]	—
Pop()	[3, 5]	8
Peek()	[3, 5]	3
Pop()	[5]	3

Real-World Uses of Stacks

• Undo functionality in text editors — each action is pushed onto a stack; pressing undo pops the last action
• Browser back button — each visited page is pushed onto a stack
• Function call stack — when a program calls a function, the return address is pushed onto the stack
• Evaluating mathematical expressions — used in reverse Polish notation

---

Queues

A queue is a First In, First Out (FIFO) data structure. The first item added to the queue is the first one to be removed — just like a queue of people waiting in a line.

Key Operations

Operation	Description
Enqueue	Add an item to the back (rear) of the queue
Dequeue	Remove and return the item from the front of the queue
Peek (or Front)	View the front item without removing it
isEmpty	Check if the queue is empty
isFull	Check if the queue is full

Example: Queue Operations

Starting with an empty queue:

Operation	Queue (front → back)	Returned Value
Enqueue(5)	[5]	—
Enqueue(3)	[5, 3]	—
Enqueue(8)	[5, 3, 8]	—
Dequeue()	[3, 8]	5
Peek()	[3, 8]	3
Dequeue()	[8]	3

Real-World Uses of Queues

• Print queues — documents are printed in the order they are submitted
• Keyboard buffer — keystrokes are processed in the order they are typed
• CPU scheduling — processes waiting for the processor form a queue
• Network data packets — processed in the order they arrive

---

Comparing Stacks and Queues

Feature	Stack	Queue
Order	LIFO (Last In, First Out)	FIFO (First In, First Out)
Add	Push (to top)	Enqueue (to back)
Remove	Pop (from top)	Dequeue (from front)
Real-world analogy	Stack of plates	Queue at a shop

Exam Tip: Remember the mnemonics: Stack = LIFO (Last In, First Out), Queue = FIFO (First In, First Out). Be prepared to trace through push/pop or enqueue/dequeue operations on a diagram.

---

Key Points

• An array stores elements of the same data type, accessed by index.
• A 2D array is like a table with rows and columns.
• A record stores related fields of different data types, accessed by field name.
• A stack is LIFO — push and pop from the top.
• A queue is FIFO — enqueue at the back, dequeue from the front.

---

Extended Worked Examples

Worked Example A: Full Stack Trace (Function Call Simulation)

When a program calls a function, the CPU pushes the return address (and local variables) onto a call stack. Consider:

FUNCTION main()
    x = square(5)
    OUTPUT x
ENDFUNCTION

FUNCTION square(n)
    RETURN n * n
ENDFUNCTION