10.4 Stack Abstract Data Types - A-Level Computer Science

Learning Objectives

By the end of this lesson, you will be able to:

Show understanding that an Abstract Data Type (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 to store data and perform operations on it
Describe how a stack can be implemented using arrays
Describe key features of a stack and justify its use for a given situation
Add, edit, and delete data from a stack structure
Understand and explain stack overflow and underflow conditions
Identify real-world applications of stacks

Key Terms

Abstract Data Type (ADT)

A collection of data and a set of operations on that data

Stack

A list containing several items operating on the Last In, First Out (LIFO) principle

LIFO

Last In, First Out - the principle that the last item added to a stack is the first to be removed

Push

Operation to add an item to the top of a stack

Pop

Operation to remove an item from the top of a stack

BaseOfStackPointer

Pointer that always points to the first slot in the stack

TopOfStackPointer

Pointer that points to the last element pushed onto the stack

Stack Overflow

Condition when trying to push an item onto a full stack

Stack Underflow

Condition when trying to pop an item from an empty stack

Linear Structure

A data structure where elements are arranged in a linear sequence

Instance

A specific occurrence or example of a data structure

Backtracking

A problem-solving technique that uses stacks to explore possible solutions

Abstract Data Types (ADTs)

An Abstract Data Type (ADT) is a collection of data and a set of operations on that data. It defines what operations can be performed on the data, but not how these operations are implemented.

Common ADT Operations

Create a new instance of the data structure
Find an element in the data structure
Insert a new element into the data structure
Delete an element from the data structure
Access all elements stored in the data structure

Examples of ADTs

Stack - Last In, First Out (LIFO) structure
Queue - First In, First Out (FIFO) structure
Linked List - Sequence of nodes linked together
Binary Tree - Hierarchical structure with parent-child relationships
Dictionary - Key-value pair storage

Real-Life Example: School Locker System

Think of an ADT like a school locker system:

Data: The books, bags, and other items in the locker
Operations: Open locker, put item in, take item out, search for item, lock locker
Implementation details hidden: You don't need to know how the lock mechanism works internally
Different implementations: Combination lock, key lock, digital lock - all provide the same operations

Check Your Understanding: ADTs

1. What is an Abstract Data Type (ADT)? [2 marks]

Answer

[1 mark] An ADT is a collection of data
[1 mark] Together with a set of operations on that data
[Additional] It defines what operations can be performed, not how they are implemented

2. List three common operations on an ADT. [3 marks]

Answer

[1 mark] Create a new instance of the data structure
[1 mark] Insert a new element into the data structure
[1 mark] Delete an element from the data structure
[Additional] Other valid answers: Find an element, Access all elements

3. Give two examples of ADTs other than stack. [2 marks]

Answer

[1 mark] Queue
[1 mark] Linked List
[Additional] Other valid answers: Binary Tree, Dictionary

Stack Abstract Data Type

A Stack is a list containing several items operating on the Last In, First Out (LIFO) principle. Items can be added to the stack (push) and removed from the stack (pop). The first item added to a stack is the last item to be removed from the stack.

Stack Operations

Core Stack Operations

Create empty stack - Initialize a new stack
Add item to stack (Push) - Place an item on top of the stack
Remove item from stack (Pop) - Take the top item from the stack
Search item in stack - Check if an item exists in the stack

Stack Characteristics

Linear structure - Elements are arranged in a line
LIFO principle - Last In, First Out
Has top and base pointers - Tracks stack boundaries
Limited access - Only the top element is accessible

Stack Operations Visualizer

Visualize how a stack works with LIFO principle. Watch what happens when you push and pop items.

Top Pointer →

Base Pointer →

Stack: Empty | Items: 0 | Top Pointer: -1

How it works:

Push: Adds an item to the top of the stack. Top pointer moves up.
Pop: Removes the top item from the stack. Top pointer moves down.
LIFO: The last item pushed is always the first item popped.
Stack has maximum capacity of 8 items to prevent overflow.

Real-Life Example: Plate Stack in Cafeteria

A stack works exactly like a stack of plates in a cafeteria:

Pushing Plates

Clean plates are added to the TOP of the stack
Last plate added is on top
You can only access the top plate
Bottom plate stays there until all others are removed

Popping Plates

Customers take plates from the TOP
Last plate added is first to be taken
First plate added is last to be taken
This is LIFO in action!

Other examples: Browser back button (pages visited), Undo operations in word processors, Call stack in programming.

Applications of Stack

Memory Management

Stacks are used in computer memory to manage function calls and local variables. Each function call pushes a new frame onto the call stack.

Expression Evaluation

Stacks are used to evaluate arithmetic expressions (infix to postfix conversion) and to check for balanced parentheses in expressions.

Backtracking in Recursion

Stacks store return addresses and local variables during recursive function calls, allowing the program to backtrack to previous states.

Advantages of Stack

Easy to ensure reverse order: Items are removed in reverse order of insertion
Efficient operations: Push and pop operations are O(1) time complexity
Memory efficient: Only uses memory for stored items
Simple implementation: Easy to implement using arrays or linked lists

Disadvantages of Stack

Stack overflow: Can occur when trying to push an item onto a full stack
Stack underflow: Can occur when trying to pop an item from an empty stack
Limited access: Can only access the top element
Fixed size: Array-based stacks have a fixed maximum size

Activity 1: Stack Operations Practice

Trace the operations on a stack and determine the final state:

Start with an empty stack
Push: A
Push: B
Push: C
Pop: (what item is removed?)
Push: D
Pop: (what item is removed?)
Pop: (what item is removed?)
What item remains in the stack?

Solution:

Stack: [ ] (empty)
Push A: Stack: [A] (A at top)
Push B: Stack: [A, B] (B at top)
Push C: Stack: [A, B, C] (C at top)
Pop: Removes C. Stack: [A, B] (B at top)
Push D: Stack: [A, B, D] (D at top)
Pop: Removes D. Stack: [A, B] (B at top)
Pop: Removes B. Stack: [A] (A at top)
Item remaining: A

Key point: Remember LIFO - Last In, First Out. The last item pushed is always the first popped.

Check Your Understanding: Stack ADT

1. What does LIFO stand for and what does it mean for a stack? [2 marks]

Answer

[1 mark] LIFO stands for Last In, First Out
[1 mark] It means the last item added to the stack is the first item to be removed
[Additional] This is the fundamental principle of stack operation

2. What are the two main operations on a stack and what do they do? [4 marks]

Answer

[2 marks] Push: Adds an item to the top of the stack
[2 marks] Pop: Removes an item from the top of the stack
[Additional] Other operations include: Create empty stack, Search item in stack

3. Name two real-world applications of stacks. [2 marks]

Answer

[1 mark] Memory management (call stack for function calls)
[1 mark] Expression evaluation (arithmetic expression parsing)
[Additional] Other valid answers: Backtracking in recursion, Undo operations, Browser back button

4. What is stack overflow and when does it occur? [2 marks]

Answer

[1 mark] Stack overflow occurs when trying to push an item onto a full stack
[1 mark] It can cause program crashes or unexpected behavior
[Additional] This is a disadvantage of stack data structure, especially with fixed-size arrays

5. What advantage does a stack provide in terms of item removal order? [1 mark]

Answer

[1 mark] Easy to ensure that items are removed (read) in reverse order
[Additional] This is useful for undo operations, backtracking, and parsing nested structures

Stack Implementation Using Arrays

A stack can be implemented using an array and a set of pointers. As an array has a finite size, the stack may become full and this condition must be allowed for.

Array Implementation Steps

Define 1D array with an appropriate data type and size
Declare integer variable for StackPointer which will store index of value on top of stack
Declare integer variable for size of stack which limits max values in stack
Initialize both StackPointer and the stack size to indicate an empty stack
Store each item on stack as one array element
Develop routines (procedures/functions) for the Push and Pop operations
Ensure that Push and Pop routines include checks for conditions of a full or empty stack

Array-Based Stack Implementation

See how a stack is implemented using an array. Watch how the TopOfStackPointer moves as items are pushed and popped.

Array: [ , , , , , , , ] | Top Pointer: -1 | Base Pointer: 0

Array indices: 0 (Base) to 7 (Max)

Key Points:

BaseOfStackPointer: Always points to index 0 (first array element)
TopOfStackPointer: Points to the last pushed element, starts at -1 for empty stack
Push: Increment TopOfStackPointer, store value at that index
Pop: Get value at TopOfStackPointer, decrement TopOfStackPointer
Full stack: When TopOfStackPointer = array size - 1
Empty stack: When TopOfStackPointer = -1

BaseOfStackPointer

Always points to the first slot in the stack (array index 0)
Value remains the same during stack operations
When stack is empty, BaseOfStackPointer has value 0
Represents the bottom/foundation of the stack

TopOfStackPointer

Points to the last element pushed onto the stack
When an element is popped, TopOfStackPointer decreases
When stack is empty, TopOfStackPointer has value -1
When stack has one item, BaseOfStackPointer = TopOfStackPointer

Array Declaration for Stack

DECLARE Stack : ARRAY[0:7] OF CHAR
; Creates an array with 8 elements (indices 0 to 7) for character storage

This creates an array that can hold 8 characters. The stack will use this array to store items, with index 0 as the base and index 7 as the maximum top position.

Stack States: Empty vs Full

Empty Stack

7	6
5	4
3	2
1	0

TopOfStackPointer = -1
BaseOfStackPointer = 0
All array slots are empty
Cannot pop from empty stack (underflow)

Stack with Four Items

7	6
5	4
3	D
2	C
1	0

Items pushed: A (index 0), B (index 1), C (index 2), D (index 3)
TopOfStackPointer = 3 (points to D)
BaseOfStackPointer = 0 (points to A)
Next pop will remove D from index 3

Activity 2: Array Stack Operations

Given a stack implemented as an array Stack[0:7] with the following operations:

Start with empty stack (TopOfStackPointer = -1)
Push 'X'
Push 'Y'
Push 'Z'
Pop (what value is removed?)
What is the value of TopOfStackPointer after step 5?
Push 'W'
What array index contains 'W'?
What array index contains 'X'?

Solution:

Empty stack: TopOfStackPointer = -1
Push 'X': TopOfStackPointer = 0, Stack[0] = 'X'
Push 'Y': TopOfStackPointer = 1, Stack[1] = 'Y'
Push 'Z': TopOfStackPointer = 2, Stack[2] = 'Z'
Pop: Removes 'Z' from Stack[2], TopOfStackPointer = 1
TopOfStackPointer after step 5: 1
Push 'W': TopOfStackPointer = 2, Stack[2] = 'W'
'W' is at array index: 2
'X' is at array index: 0 (BaseOfStackPointer always points here)

Key point: TopOfStackPointer always points to the last pushed item. When popping, we remove from that position, then decrement the pointer.

Exam Style Question

ESQ# 2: Identify and describe the following Stack abstract data type.

Answer should include:

Linear structure
Last in first out structure
Has top and base stack pointers
Uses push to add items to top of stack
Uses pop to remove items from top of stack

Marking guidance: This is a typical 4-5 mark question. You would get 1 mark for each correct characteristic mentioned. Make sure to use precise terminology like "LIFO", "push", "pop", "top pointer", "base pointer".

Check Your Understanding: Stack Implementation

1. What is the purpose of TopOfStackPointer in array implementation? [2 marks]

Answer

[1 mark] Points to the last element pushed onto the stack
[1 mark] Tracks the current top position in the array
[Additional] When stack is empty, TopOfStackPointer = -1

2. What value does TopOfStackPointer have when the stack is empty? [1 mark]

Answer

[1 mark] -1
[Additional] This indicates no valid index in the array contains stack data

3. What happens to TopOfStackPointer when an item is popped? [2 marks]

Answer

[1 mark] It decreases by 1
[1 mark] It points to the element now at the top of the stack
[Additional] Example: If TopOfStackPointer was 5, after pop it becomes 4

4. Why must push and pop routines check for full or empty stack? [2 marks]

Answer

[1 mark] To prevent stack overflow (pushing to full stack)
[1 mark] To prevent stack underflow (popping from empty stack)
[Additional] These conditions can cause program crashes or data corruption

5. When do BaseOfStackPointer and TopOfStackPointer have the same value? [1 mark]

Answer

[1 mark] When there is only one item in the stack
[Additional] BaseOfStackPointer always = 0, TopOfStackPointer = 0 when first item is pushed

Key Takeaways

An Abstract Data Type (ADT) is a collection of data and a set of operations on that data
A Stack is an ADT that operates on the Last In, First Out (LIFO) principle
Main stack operations are Push (add to top) and Pop (remove from top)
Stacks are linear structures with top and base pointers
Stacks can be implemented using arrays with BaseOfStackPointer and TopOfStackPointer
BaseOfStackPointer always points to the first slot (index 0) and doesn't change
TopOfStackPointer points to the last pushed item, starts at -1 for empty stack
Stack overflow occurs when pushing to a full stack
Stack underflow occurs when popping from an empty stack
Stacks are used in memory management, expression evaluation, and backtracking in recursion
The advantage of stacks is they easily ensure items are removed in reverse order
When implementing with arrays, check for full/empty conditions before push/pop operations
When there's only one item in stack, BaseOfStackPointer = TopOfStackPointer

Question Bank

1. Explain what an Abstract Data Type (ADT) is and give two examples. [4 marks]

Marking Scheme & Answer

[2 marks] An ADT is a collection of data and a set of operations on that data
[1 mark] Example 1: Stack (LIFO structure)
[1 mark] Example 2: Queue (FIFO structure)
[Additional] Other examples: Linked list, Binary tree, Dictionary. ADT defines what operations can be performed, not how they're implemented.

2. Describe the LIFO principle and how it applies to stacks. [3 marks]

Marking Scheme & Answer

[1 mark] LIFO stands for Last In, First Out
[1 mark] It means the last item added to the stack is the first to be removed
[1 mark] In stacks, push adds to top, pop removes from top - maintaining LIFO order
[Additional] Real-world example: Stack of plates - last plate washed is first to be used

3. Explain stack overflow and stack underflow with examples of when they occur. [4 marks]

Marking Scheme & Answer

[2 marks] Stack overflow: Occurs when trying to push an item onto a full stack. Example: Array-based stack with 8 slots trying to push a 9th item.
[2 marks] Stack underflow: Occurs when trying to pop an item from an empty stack. Example: Calling pop when TopOfStackPointer = -1.
[Additional] Both can cause program crashes. Good implementations check for these conditions before push/pop operations.

4. How is a stack implemented using an array? Describe the role of BaseOfStackPointer and TopOfStackPointer. [5 marks]

Marking Scheme & Answer

[1 mark] Define an array with fixed size: DECLARE Stack : ARRAY[0:n] OF dataType
[2 marks] BaseOfStackPointer: Always points to index 0 (first array slot). Value remains constant.
[2 marks] TopOfStackPointer: Points to last pushed item. Starts at -1 for empty stack. Increases with push, decreases with pop.
[Additional] Push: Increment TopOfStackPointer, store value at that index. Pop: Get value at TopOfStackPointer, decrement pointer.

5. Trace the stack operations and give the final TopOfStackPointer value: [6 marks]
Start: Empty stack (TopOfStackPointer = -1)
Push A, Push B, Pop, Push C, Push D, Pop, Pop

Marking Scheme & Answer

Start: TopOfStackPointer = -1, Stack: []
Push A: TopOfStackPointer = 0, Stack: [A]
Push B: TopOfStackPointer = 1, Stack: [A, B]
Pop: Remove B, TopOfStackPointer = 0, Stack: [A]
Push C: TopOfStackPointer = 1, Stack: [A, C]
Push D: TopOfStackPointer = 2, Stack: [A, C, D]
Pop: Remove D, TopOfStackPointer = 1, Stack: [A, C]
Pop: Remove C, TopOfStackPointer = 0, Stack: [A]
Final TopOfStackPointer: 0

6. What are the advantages and disadvantages of using a stack data structure? [4 marks]

Marking Scheme & Answer

[2 marks] Advantages: Easy to ensure reverse order removal; Efficient O(1) push/pop operations; Simple implementation; Useful for specific applications (undo, backtracking)
[2 marks] Disadvantages: Stack overflow/underflow risks; Limited access (only top element); Fixed size in array implementation; Not suitable for random access needs

7. Describe two real-world applications of stacks in computing. [4 marks]

Marking Scheme & Answer

[2 marks] Memory Management: Call stack for function calls. Each function call pushes a frame with return address and local variables. Returns pop the frame.
[2 marks] Expression Evaluation: Converting infix to postfix notation, evaluating arithmetic expressions, checking balanced parentheses.
[Additional] Other applications: Undo operations in software, Backtracking algorithms, Browser history (back button).

8. Write pseudocode for the push operation in an array-based stack implementation. Include overflow check. [5 marks]

Marking Scheme & Answer

PROCEDURE Push(value : CHARACTER)
  IF TopOfStackPointer = MAX_SIZE - 1 THEN
    // Stack overflow check
    OUTPUT "Stack overflow - cannot push"
  ELSE
    TopOfStackPointer ← TopOfStackPointer + 1
    Stack[TopOfStackPointer] ← value
  ENDIF
ENDPROCEDURE

Key elements: Check for overflow (TopOfStackPointer = MAX_SIZE-1), increment TopOfStackPointer, store value at new position.

9. Explain why BaseOfStackPointer remains constant while TopOfStackPointer changes during stack operations. [3 marks]

Marking Scheme & Answer

[1 mark] BaseOfStackPointer always points to the first array element (index 0)
[1 mark] This position represents the bottom/foundation of the stack which doesn't move
[1 mark] TopOfStackPointer tracks the current top position which changes with push/pop operations
[Additional] Base pointer is fixed, top pointer is dynamic - this is fundamental to array-based stack implementation

10. A stack is implemented as an array Stack[0:7]. After operations: Push X, Push Y, Pop, Push Z, Push W. What is in Stack[0] and Stack[2]? What is TopOfStackPointer value? [4 marks]

Marking Scheme & Answer

[1 mark] Stack[0] contains: X (first pushed item, at base)
[1 mark] Stack[2] contains: W (after operations, W is at index 2)
[2 marks] TopOfStackPointer value: 2 (points to W at index 2)
[Additional] Operations trace: Push X (index 0), Push Y (index 1), Pop (remove Y, pointer=0), Push Z (index 1), Push W (index 2)