What is the primary difference between a Stack and a Queue?

A Stack uses the LIFO (Last In, First Out) principle where the last item added is the first removed. A Queue uses the FIFO (First In, First Out) principle where the first item added is the first removed.

How does a Circular Queue differ from a Linear Queue in terms of memory efficiency?

A Linear Queue wastes space at the front of the array as items are dequeued. A Circular Queue reuses that empty space by allowing the rear pointer to wrap around to the beginning of the array.

Compare the memory requirements of an Array vs. a Linked List.

Arrays store only data in contiguous blocks, making them memory-efficient for the data itself. Linked Lists require extra memory for each node to store the pointer (address) to the next item.

What is 'Stack Overflow' and when does it occur?

Stack Overflow is an error that occurs when a program attempts to push an item onto a stack that has already reached its maximum allocated capacity.

What happens during a 'Stack Underflow' error?

Stack Underflow occurs when an operation attempts to pop or remove an item from a stack that is currently empty.

What is a common mistake when deleting a node from a Linked List?

A common error is failing to update the pointer of the preceding node, which results in a 'broken' chain or losing access to the rest of the list.

Define a 'Node' in the context of a Linked List.

A node is a composite data structure containing two parts: the actual data being stored and a pointer (or reference) to the next node in the sequence.

What does the 'Peek' operation do in a Stack or Queue?

The Peek operation returns the value of the item at the top (Stack) or front (Queue) without removing it from the structure.

What is the purpose of a 'Base Pointer' in a Stack?

The base pointer identifies the fixed starting location of the stack in memory, allowing the system to track the stack's origin even as the top pointer moves.

Why is a Linked List considered a 'Dynamic' data structure?

It is dynamic because it can grow or shrink in size during program execution by allocating or deallocating memory for individual nodes as needed.

ADT overview | Cambridge International Examinations AS-Level Computer Science

Revision Notes

AS-Level

Cambridge International Examinations

Computer Science

10. Data Types & Structures

ADT overview

Summary

An Abstract Data Type (ADT) is a high-level model that defines a data structure by its behavior and the operations that can be performed on it, rather than its specific implementation in code. By separating the logical properties of data from the physical storage details, ADTs allow for modular program design and data abstraction.

1. Definition & Core Concepts

An Abstract Data Type (ADT) is a formal specification of a data collection and the set of operations that can be performed on that data.
It focuses on what the data represents and what operations can be performed, rather than how those operations are implemented in a specific programming language.
Common examples of ADTs include Stacks, Queues, and Linked Lists, each defined by unique rules for data access and manipulation.

2. The Stack ADT

A Stack operates on the Last In, First Out (LIFO) principle, meaning the most recently added item is the first one to be removed.
It utilizes two primary pointers: a base pointer (fixed at the start) and a top pointer (which moves as items are added or removed).
Core operations include push(value) to add an item, pop() to remove the top item, and peek() to view the top item without removing it.
Stack Overflow occurs when attempting to push onto a full stack, while Stack Underflow occurs when attempting to pop from an empty stack.

A diagram of a Stack ADT showing the LIFO principle with Push and Pop operations.

3. The Queue ADT

A Queue follows the First In, First Out (FIFO) principle, where the first item added is the first one to be processed.
Linear Queues use an array where items are added at the 'rear' and removed from the 'front'; however, they can become inefficient as space at the front is wasted after deletions.
Circular Queues solve the space efficiency problem by 'wrapping' the rear pointer back to the start of the array when it reaches the end, provided space has been freed by deletions.
Key operations include enQueue(value) to add to the back and deQueue() to remove from the front.

4. The Linked List ADT

5. Key Distinctions

6. Exam Strategy & Tips