Show understanding that an ADT is a collection of data and a set of operations on those data
Show understanding that a stack, queue and linked list are examples of ADTs
Use a stack, queue and linked list to store data
Describe how a queue, stack and linked list can be implemented using arrays
Describe key features of stack, queue and linked list and justify their use for a given situation
Be able to add, edit and delete data from these structures
📋 Prior Knowledge Required
Understanding of arrays and how they store data in memory
Knowledge of pointers and memory addresses
Basic understanding of data structures
Familiarity with pseudocode and programming concepts
Understanding of variables and data types
🌟 Did You Know?
Abstract Data Types (ADTs) are fundamental building blocks in computer science. They define what operations can be performed on data, but not how those operations are implemented. This separation of specification from implementation is a key principle in software engineering!
1. What is an Abstract Data Type (ADT)?
An Abstract Data Type (ADT) is a collection of data and a set of operations on that data. The key word is abstract — it specifies WHAT operations can be performed, but not HOW they are implemented.
📖 Key Characteristics of ADTs
Data: The information being stored and manipulated
Operations: The actions that can be performed on the data
Abstraction: Implementation details are hidden from the user
Encapsulation: Data and operations are bundled together
Reusability: Same ADT can be used in different programs
Maintainability: Implementation can change without affecting usage
Abstraction: Users don't need to know implementation details
💡 Exam Tip
Remember: ADTs define the interface (what operations are available) but not the implementation (how those operations work). The same ADT can be implemented in different ways — for example, a Stack can be implemented using an array or a linked list!
2. Stack Abstract Data Type
A Stack is an abstract data type that stores data using the Last In, First Out (LIFO) principle. Think of it like a pile of plates — the last plate you put on top is the first one you take off!
📖 Stack Definition
A list containing several items operating on the LIFO principle
Items can be added (push) and removed (pop) from the same end only
The first item pushed onto the stack will be the last one popped off
Only the top element is accessible at any time
2.1 Stack Operations
Operation
Description
push(value)
Add an item to the top of the stack
pop()
Remove and return the item from the top of the stack
peek()
Return the top value without removing it
isEmpty()
Check if the stack is empty
isFull()
Check if the stack is full (for array implementation)
size()
Return the number of elements in the stack
🧠 Memory Trick
Think of a stack of plates in a cafeteria. You can only take the top plate, and when you add a clean plate, it goes on top. The last plate placed is the first one removed — LIFO!
2. Stack Implementation Using Arrays
A stack can be implemented using an array and a set of pointers. Since an array has a finite size, the stack may become full — this condition must be allowed for.
2.2 Stack Pointers
📖 Stack Pointer Types
BaseOfStackPointer: Always points to the first slot in the stack (usually index 0)
TopOfStackPointer: Points to the last element pushed onto the stack
When stack is empty: TopOfStackPointer = -1, BaseOfStackPointer = 0
When base and top pointers are equal, there is only one item in the stack
2.3 Stack Overflow & Underflow
⚠️ Stack Overflow
Occurs when trying to push an item onto a stack that is already full. This happens when TopOfStackPointer reaches the maximum array size. Can cause program crash!
⚠️ Stack Underflow
Occurs when trying to pop an item from an empty stack. This happens when TopOfStackPointer = -1. Can cause program crash!
📝 Implementing Stack with 1D Array
Define a 1D array with appropriate data type and size
Declare integer variable for StackPointer (stores index of top value)
Declare integer variable for size of stack (limits max values)
Initialize both StackPointer and size to indicate an empty stack
Store each item on stack as one array element
Develop routines (procedures/functions) for Push and Pop operations
Ensure Push and Pop routines include checks for full or empty stack
💡 Exam Tip
The base pointer value always remains the same during stack operations. Only the top pointer changes when items are pushed or popped. When TopPointer = -1, the stack is empty!
2. Stack Applications & Summary
2.4 Applications of Stacks
Application
Description
Memory Management
Managing function calls and local variables in program execution
Expression Evaluation
Evaluating arithmetic expressions (infix to postfix conversion)
Real-world Example: When you press "Undo" in a word processor, the application uses a stack to store your recent actions. Each action is pushed onto the stack. When you undo, the last action is popped and reversed!
📌 Stack Summary
Principle: LIFO (Last In, First Out)
Main Operations: Push (add), Pop (remove), Peek (view top)
Pointers: Base pointer (fixed), Top pointer (changes)
Empty Stack: TopPointer = -1
Errors: Stack Overflow (push to full), Stack Underflow (pop from empty)
Advantage: Easy to ensure items are removed in reverse order
Disadvantage: Overflow and underflow can cause crashes
3. Queue Abstract Data Type
A Queue is an abstract data type that stores data in the order it arrives, using the First In, First Out (FIFO) principle. Think of it like a line of people waiting at a shop — the first one in is the first one served!
📖 Queue Definition
A list containing several items operating on the FIFO principle
Items can be added at one end (enqueue) and removed from the other end (dequeue)
The first item added to the queue is the first one to be removed
Items enter at the rear and leave from the front
3.1 Queue Operations
Operation
Description
enQueue(value)
Add an element to the back/rear of the queue
deQueue()
Remove and return an element from the front of the queue
peek()
Return the value at the front without removing it
isEmpty()
Check whether the queue is empty
isFull()
Check whether the queue is full (for array implementation)
🧠 Memory Trick
Think of a queue at a bus stop or checkout line at a store. The first person to join the line is the first person to be served. New people join at the back, and people leave from the front — FIFO!
3.2 Linear Queue Implementation
A Linear Queue is implemented using an array. Items are added to the next available space starting from the front, and items are removed from the front of the queue.
📝 Linear Queue Implementation Steps
Declare a 1D array of suitable size and data type
Declare integer variable for FrontOfQueuePointer
Declare integer variable for EndOfQueuePointer (or RearPointer)
Initialize both pointers to represent an empty queue
Declare integer variable for NumberInQueue
Declare integer variable for SizeOfQueue to limit max items
📖 Linear Queue Pointers
When queue is empty: EndOfQueuePointer = -1
When one value joins: EndOfQueuePointer is incremented before adding value
When an item leaves (dequeue): All items must be shifted forward
FrontOfQueuePointer typically stays at position 0
❌ Common Mistake
In a linear queue, when items are dequeued, you must either: (1) shift all remaining items forward one position, OR (2) use a circular queue to avoid this inefficient shifting. The linear queue approach is inefficient because it requires moving all elements!
💡 Exam Tip
When asked about the disadvantage of a linear queue, always mention: Items must be shifted forward when dequeuing, which is inefficient. The solution is to use a circular queue!
3.3 Circular Queue Implementation
A Circular Queue (or circular buffer) is a static array with a fixed capacity. When items are dequeued, space is freed up at the start of the array. Rather than shifting items, the queue wraps around to reuse empty slots!
📖 How Circular Queue Works
As items are enqueued and rear reaches the last position, it wraps around to the start
When items are dequeued, front pointer also wraps around
Before adding: Check queue is not full (next position ≠ front)
Before removing: Check queue is not empty
Both pointers updated to point to first element after reaching last
📝 Circular Queue Wrapping Logic
If RearPointer = maxSize - 1, next enqueue sets RearPointer = 0
If FrontPointer = maxSize - 1, next dequeue sets FrontPointer = 0
Queue is full when: next rear position = front position
Queue is empty when: front passes rear (or initially both = -1)
4. Linked List Abstract Data Type
A Linked List is an abstract data type where each item, or node, contains a data field and a pointer to the next node in the sequence. It's like a chain of items where each item stores two things: the actual data and a pointer to the next item!
📖 Linked List Components
Node: An element of the list containing data and a pointer
Data Field: Contains the actual value/data
Pointer Field: Stores the address of the next node
Start Pointer: Variable storing address of first element
Null Pointer: Pointer that doesn't point to anything (end of list)
Heap: Empty positions managed as a free list
4.1 Key Features
Feature
Description
Structure
Chain of nodes, each pointing to the next
Access Method
Sequential traversal from start to desired node
Insertion
Usually at start; only pointers need updating
Deletion
From any position; update previous node's pointer
Dynamic
Can grow/shrink without fixed size (when using dynamic memory)
💡 Exam Tip
Linked lists can only be traversed from the start — you cannot directly access an element at a specific position like with arrays. You must follow each node's pointer until you reach the desired element!
4.2 Linked List Operations
Adding a Node to the Beginning
📝 Steps to Add at Start
Copy content of StartPointer into new node's pointer field
Set StartPointer to point to the new node
Update FreeListPointer to next free position
Deleting a Node
📝 Steps to Delete a Node
First node: Copy pointer field of node to delete into StartPointer
Other nodes: Update previous node's pointer to skip deleted node
Update FreeListPointer to point to deleted position
The node is not removed; it's just ignored (added to free list)
Implementation Methods
Method
Description
Two 1D Arrays
One array for data values, another for pointers. Same index = one node.
Record Data Type
Define a record with data and pointer fields. Declare array of records.
Record Type Example (Pseudocode):
TYPE ListNode
DECLARE Name : STRING
DECLARE Pointer : INTEGER
END TYPE
DECLARE NameList : ARRAY[1:50] OF ListNode
4.3 Linked List: Advantages & Disadvantages
Advantages
Disadvantages
Insertion/deletion only requires updating pointers
Store pointers for every data item — extra storage required
No need to shift elements after insertion/deletion
Memory required is more than arrays (pointer field takes space)
Stacks and queues can be easily implemented using linked list
Cannot directly access element at index X — must traverse
Dynamic size — can grow/shrink as needed
More complex to implement than arrays
Efficient for frequent insertions/deletions
Slower access time — O(n) to find an element
📌 When to Use Each ADT
Stack: When you need LIFO behavior (undo operations, recursion, expression evaluation)
Queue: When you need FIFO behavior (print jobs, task scheduling, BFS)
Linked List: When you need frequent insertions/deletions and don't need direct access
5. Exam-Style Questions
1. A stack is an example of an Abstract Data Type (ADT). [4 marks]
(a) State what ADT stands for.
(b) Explain what is meant by an ADT.
(c) Name two other examples of ADTs.
Answer:
(a) ADT stands for Abstract Data Type
(b) An ADT is a collection of data and a set of operations on that data. It specifies WHAT operations can be performed but not HOW they are implemented (abstraction)
(c) Two other examples: Queue, Linked List, Binary Tree, Dictionary
Additional points for deeper understanding:
ADTs separate the logical view from the implementation
Common operations include: Create, Insert, Delete, Find, Access
2. Describe the principle of operation of a stack. Give one application where a stack would be used. [4 marks]
Answer:
A stack operates on the LIFO (Last In, First Out) principle
Items are added (pushed) and removed (popped) from the same end (the top)
Only the top element is accessible at any time
Application: Memory management, expression evaluation, backtracking in recursion, undo operations in software, browser history (back button), syntax parsing for balanced parentheses
Additional points for deeper understanding:
Uses two pointers: base pointer (fixed) and top pointer (changes)
Stack overflow occurs when pushing to a full stack
Stack underflow occurs when popping from an empty stack
3. A stack is implemented using an array. The array has indices 0 to 7. The stack contains the values: ['A', 'B', 'C'] where 'C' was added last. [4 marks]
(a) State the value of the TopPointer.
(b) State the value of the BasePointer.
(c) After the operation POP() is executed, what is the new value of TopPointer?
Answer:
(a) TopPointer = 2 (points to index of 'C', the last element pushed)
(b) BasePointer = 0 (always points to first slot, never changes)
(c) After POP(), TopPointer = 1 (decremented by 1, now points to 'B')
Additional points for deeper understanding:
If TopPointer = -1, the stack is empty
If TopPointer = 7 (max index), the stack is full
The popped value 'C' is returned and removed from the top
4. Explain the difference between stack overflow and stack underflow. Give an example of when each might occur. [4 marks]
Answer:
Stack Overflow: Occurs when attempting to PUSH an item onto a stack that is already full (TopPointer has reached maximum capacity)
Stack Underflow: Occurs when attempting to POP an item from an empty stack (TopPointer = -1)
Overflow example: Trying to push a 9th item onto a stack with capacity of 8 items
Underflow example: Trying to pop from a newly created empty stack
Additional points for deeper understanding:
Both conditions can cause program crashes if not handled
Programs should always check: if TopPointer = maxSize-1 before PUSH
Programs should always check: if TopPointer = -1 before POP
5. Describe the principle of operation of a queue. Give one application where a queue would be used. [4 marks]
Answer:
A queue operates on the FIFO (First In, First Out) principle
Items are added at the rear (enqueue) and removed from the front (dequeue)
The first item added to the queue is the first item to be removed
Application: Print job scheduling, keyboard buffer, customer service systems, task scheduling in operating systems, BFS algorithm
Additional points for deeper understanding:
Uses two pointers: FrontPointer and RearPointer
Linear queues require shifting items when dequeuing (inefficient)
Circular queues solve this by wrapping pointers around
5. Exam-Style Questions (Continued)
6. Explain why a circular queue is more efficient than a linear queue implemented using an array. [4 marks]
Answer:
In a linear queue, when items are dequeued, all remaining items must be shifted forward one position — this is O(n) time complexity
In a circular queue, items are not shifted — pointers simply wrap around to reuse empty slots at the start
Circular queue operations are O(1) time complexity — much more efficient
Circular queue makes better use of available memory by reusing freed-up slots
Additional points for deeper understanding:
Linear queue wastes space at the front as items are dequeued
Circular queue treats the array as if first and last elements are connected
When RearPointer reaches max index, next enqueue goes to index 0
7. A linked list is to be implemented using arrays. Describe how a linked list can be implemented using two 1D arrays. [4 marks]
Answer:
Use two 1D arrays: one for storing data values, another for storing pointers
Elements at the same index in both arrays represent one node (data + pointer)
Data array can be of string or any appropriate type for the data
Pointer array stores the index of the next node (or null/special value for end)
Additional points for deeper understanding:
A StartPointer variable stores the index of the first node
A FreeListPointer tracks available positions for new nodes
Alternative: Use a record type with data and pointer fields
Example: Data[3]="Math", Pointer[3]=5 means next node is at index 5
8. Describe the advantages and disadvantages of using a linked list compared to an array. [6 marks]
Answer:
Advantages of Linked List:
Easy insertion/deletion — only pointers need to be changed, no shifting required
Dynamic size — can grow/shrink as needed (when using dynamic memory allocation)
Efficient for frequent insertions and deletions at any position
Disadvantages of Linked List:
Extra memory required — each node needs space for both data AND pointer
No direct access — must traverse from start to reach any element, O(n) time
More complex to implement and manage compared to arrays
Slower access time compared to arrays which have O(1) direct access
Additional points for deeper understanding:
Arrays are better when you need random/direct access to elements
Linked lists are better when you need frequent insertions/deletions
Arrays have better cache locality (contiguous memory)
9. A linked list contains nodes with data and pointer fields. Describe how to delete the first node in a linked list. [4 marks]
Answer:
Copy the pointer field of the node to be deleted (first node) into the StartPointer
This makes StartPointer point to what was previously the second node
Update FreeListPointer to point to the deleted node's index (so it can be reused)
Store the old FreeListPointer value in the deleted node's pointer field
Additional points for deeper understanding:
The deleted node is not physically removed — it's added to the free list
Deleting first node is O(1) operation — very efficient
Deleting other nodes requires traversing to find the previous node first
The previous node's pointer is updated to skip the deleted node
10. Justify the use of a stack for the "undo" operation in a word processor. [4 marks]
Answer:
A stack uses LIFO principle — the last action performed should be the first action undone
Each user action is pushed onto the stack when performed
When "undo" is pressed, the most recent action is popped and reversed
This matches user expectations — undo reverses the most recent change first
Additional points for deeper understanding:
Multiple undos simply pop multiple items from the stack
A queue would undo the oldest action first, which doesn't make sense for undo
The stack naturally maintains the order of actions for sequential reversal
Redo operations can use a second stack to store undone actions
6. Glossary
📖 Key Terms and Definitions
Abstract Data Type (ADT) → A collection of data and a set of operations on that data, where implementation details are hidden from the user.
Stack → An ADT that stores data using the LIFO (Last In, First Out) principle. Items are added and removed from the same end.
Queue → An ADT that stores data using the FIFO (First In, First Out) principle. Items are added at the rear and removed from the front.
Linked List → An ADT where each item (node) contains data and a pointer to the next node in the sequence.
LIFO → Last In, First Out — the access principle for stacks where the most recently added item is the first to be removed.
FIFO → First In, First Out — the access principle for queues where the first item added is the first to be removed.
Push → The operation of adding an item to the top of a stack.
Pop → The operation of removing an item from the top of a stack.
Enqueue → The operation of adding an item to the rear of a queue.
Dequeue → The operation of removing an item from the front of a queue.
Node → An element of a linked list containing a data field and a pointer field.
Pointer → A variable that stores the address of another data element or node.
Null Pointer → A pointer that does not point to any valid data; used to indicate the end of a linked list.
Start Pointer → A variable that stores the address of the first element in a linked list.
Stack Overflow → Error that occurs when attempting to push an item onto a full stack.
Stack Underflow → Error that occurs when attempting to pop an item from an empty stack.
Circular Queue → A queue implementation where the rear and front pointers wrap around to reuse empty slots.
Top Pointer → Points to the last (top) element in a stack.
Base Pointer → Points to the first element in a stack; remains constant.
Traverse → To visit each element in a data structure in sequence.
7. Exam Success Tips (Part 1)
💡 Remember: LIFO vs FIFO
Stack = LIFO (Last In, First Out) — Think of a stack of plates
Queue = FIFO (First In, First Out) — Think of a queue at a shop
Stack: Push/Pop from same end (TOP)
Queue: Enqueue at REAR, Dequeue from FRONT
💡 Stack Pointers - Key Rules
TopPointer points to last element pushed; changes with each operation
BasePointer always stays the same (usually 0)
Empty stack: TopPointer = -1
Full stack: TopPointer = maxSize - 1
💡 Queue Implementation Tips
Linear queue problem: Must shift all items forward when dequeuing
Circular queue solution: Pointers wrap around, no shifting needed
Remember: Rear changes after enqueue, Front changes after dequeue
Empty queue: RearPointer = -1 (or Front passes Rear)
🧠 Memory Trick: ADT Operations
Stack: PUSH = add to TOP, POP = remove from TOP
Queue: ENQUEUE = add to REAR, DEQUEUE = remove from FRONT
Remember: "Push" sounds like pushing DOWN on a stack (but we add to top!)
Remember: "Queue" — join at the back (rear), leave from the front
❌ Common Mistakes to Avoid
Don't confuse LIFO (stack) with FIFO (queue)!
Don't forget to check for overflow before PUSH and underflow before POP
Don't say you can directly access elements in a linked list — you must traverse
Don't forget that circular queue pointers wrap around to 0 after reaching max
Remember: Empty stack has TopPointer = -1, NOT 0!
7. Exam Success Tips (Part 2)
💡 Linked List - Key Points
Each node has data + pointer to next node
Start Pointer stores address of first node
Null Pointer marks end of list (often represented as 0 or -1)
Must traverse from start — cannot directly access elements
💡 Adding/Deleting in Linked Lists
Adding at start: Copy StartPointer to new node's pointer, update StartPointer
Deleting first: Copy node's pointer to StartPointer
Deleting other: Update previous node's pointer to skip deleted node
Always update FreeListPointer when deleting to track available space
⚠️ When Asked to Justify an ADT Choice
Always mention:
The access principle needed (LIFO or FIFO)
The type of operations required (insert/delete at start/end)
Why that ADT matches the requirement
Why other ADTs would NOT work as well
🌟 Quick Reference Table
ADT
Principle
Add Operation
Remove Operation
Stack
LIFO
Push (top)
Pop (top)
Queue
FIFO
Enqueue (rear)
Dequeue (front)
Linked List
Sequential
Usually at start
Any position
🧠 Time Complexity Summary
Array: Direct access O(1), Insert/Delete O(n)
Stack: Push/Pop O(1)
Queue: Enqueue/Dequeue O(1)
Linked List: Access O(n), Insert/Delete O(1) at start, O(n) elsewhere
8. Key Takeaways
📌 Abstract Data Types (ADT)
An ADT is a collection of data and operations on that data
ADTs define WHAT operations are available, not HOW they work