Homework 3 Stacks
Unit 7 Data structures
Homework 3 Stacks
1. Describe why a stack is not a suitable data structure for holding client records at a call
centre. Suggest a more suitable data structure and justify why it is suitable. [3]
A stack is not suitable for holding client records at a call center because:
Stacks follow LIFO (Last-In-First-Out) order, but call centers typically need FIFO (First-In-
First-Out) processing to handle clients in the order they arrived.
Important client records might get "buried" under newer records and not be accessed in a timely
manner.
A more suitable data structure would be a queue because:
Queues follow FIFO order, ensuring clients are served in the order they arrived.
This provides fair processing of client requests and maintains proper service order.
2. If a stack is implemented as a dynamic data structure, what bounds the number of items
that can be pushed?
[1]
If a stack is implemented as a dynamic data structure, the number of items that can be
pushed is bounded only by available memory.
3. The operation peek() returns the top item of a stack without removing it from the stack.
What should happen if a peek() is attempted on an empty stack? [1] If peek() is attempted
on an empty stack, it should throw an exception or return an error (like "Stack Underflow")
to indicate the operation cannot be performed on an empty stack.
4. Complete the following to show the state of a stack after the indicated operations. The
stack can only hold 4 items in total. [5]
Instruction Stack Front Result
Instruction Stack (from bottom to top) Front Result
stack ← new
[] -1 -
array(4)
push(rabbit) [rabbit] 0 -
push(fox) [rabbit, fox] 1 -
push(mouse) [rabbit, fox, mouse] 2 -
peek() [rabbit, fox, mouse] 2 mouse
pop() [rabbit, fox] 1 mouse
pop() [rabbit] 0 fox
push(hedgehog) [rabbit, hedgehog] 1 -
push(magpie) [rabbit, hedgehog, magpie] 2 -
[rabbit, hedgehog, magpie,
push(badger) 3 -
badger]
[rabbit, hedgehog, magpie,
isFull() 3 true
badger]
peek() [rabbit, hedgehog, magpie, 3 badger
1
Homework 3 Stacks
Unit 7 Data structures
badger]
pop() [rabbit, hedgehog, magpie] 2 badger
pop() [rabbit, hedgehog] 1 magpie
pop() [rabbit] 0 hedgehog
pop() [] -1 rabbit
2
Homework 3 Stacks
Unit 7 Data structures
4 (a) Describe the role of the call stack and stack frame in relation to subroutine calls. [5]
The call stack is a stack data structure that stores information about active
subroutines in a program. Its roles include:
1. Tracking the return address to go back to after a subroutine completes
2. Storing local variables and parameters
3. Maintaining the execution context of each subroutine
A stack frame is a single entry on the call stack that contains:
Return address (where to go back after the subroutine)
Parameters passed to the subroutine
Local variables of the subroutine
Other bookkeeping information
When a subroutine is called, a new stack frame is pushed onto the call stack.
When it returns, its frame is popped off, restoring the previous execution
context.
(b) Figure 1 shows the skeleton of a program containing several subroutine calls.
Figure 1 Figure 2
# Homework 3 Stacks - Answers
## Question 1
A stack is not suitable for holding client records at a call center because:
- Stacks follow LIFO (Last-In-First-Out) order, but call centers typically need FIFO (First-In-First-
Out) processing to handle clients in the order they arrived.
- Important client records might get "buried" under newer records and not be accessed in a
timely manner.
A more suitable data structure would be a **queue** because:
- Queues follow FIFO order, ensuring clients are served in the order they arrived.
- This provides fair processing of client requests and maintains proper service order.
## Question 2
If a stack is implemented as a dynamic data structure, the number of items that can be pushed
is bounded only by **available memory**.
## Question 3
If peek() is attempted on an empty stack, it should **throw an exception or return an error** (like
"Stack Underflow") to indicate the operation cannot be performed on an empty stack.
3
Homework 3 Stacks
Unit 7 Data structures
## Question 4
| Instruction | Stack (from bottom to top) | Front | Result |
|-----------------|----------------------------|-------|---------------|
| stack ← new array(4) | [] | -1 | - |
| push(rabbit) | [rabbit] |0 |- |
| push(fox) | [rabbit, fox] |1 |- |
| push(mouse) | [rabbit, fox, mouse] |2 |- |
| peek() | [rabbit, fox, mouse] | 2 | mouse |
| pop() | [rabbit, fox] | 1 | mouse |
| pop() | [rabbit] | 0 | fox |
| push(hedgehog) | [rabbit, hedgehog] |1 |- |
| push(magpie) | [rabbit, hedgehog, magpie] | 2 | - |
| push(badger) | [rabbit, hedgehog, magpie, badger] | 3 | - |
| isFull() | [rabbit, hedgehog, magpie, badger] | 3 | true |
| peek() | [rabbit, hedgehog, magpie, badger] | 3 | badger |
| pop() | [rabbit, hedgehog, magpie] | 2 | badger |
| pop() | [rabbit, hedgehog] | 1 | magpie |
| pop() | [rabbit] | 0 | hedgehog |
| pop() | [] | -1 | rabbit |
| isEmpty() | [] | -1 | true |
## Question 4(a)
The **call stack** is a stack data structure that stores information about active subroutines in a
program. Its roles include:
1. Tracking the return address to go back to after a subroutine completes
2. Storing local variables and parameters
3. Maintaining the execution context of each subroutine
A **stack frame** is a single entry on the call stack that contains:
- Return address (where to go back after the subroutine)
- Parameters passed to the subroutine
- Local variables of the subroutine
- Other bookkeeping information
When a subroutine is called, a new stack frame is pushed onto the call stack. When it returns,
its frame is popped off, restoring the previous execution context.
## Question 4(b)
| Line | Stack (return addresses only) |
|------|-------------------------------|
| 500 | [] |
| 501 | [] |
| 502 | [503] |
| 100 | [503] |
| 101 | [503, 102] |
| 200 | [503, 102] |
| 201 | [503, 102] |
| 202 | [503, 102, 203] |
| 300 | [503, 102, 203] |
| 301 | [503, 102, 203] |
| 399 | [503, 102, 203] |
| 203 | [503, 102] |
| 299 | [503, 102] |
4
Homework 3 Stacks
Unit 7 Data structures
| 102 | [503] |
| 199 | [503] |
| 503 | [] |
100 SUB subA(p1) Line Stack
101 subB (p1, 4) 500
102 … 501
199 ENDSUB 502 [503]
100
200 SUB subB(p10) 101
201 x 12 200
202 subC (p10, x) 201
203 … 202
299 ENDSUB 300
301
300 SUB subC (p1, p2) 399
301 … 203
399 ENDSUB 299
102
199
500 main() 503
501 p10 8
502 subA(p10)
503 …
Complete the table in Figure 2 to show the state of the stack during these subroutine
calls, using the notation [return address1, return address2, ..]
Show only return addresses.
The state of the stack at line 502 is given in the table. [5]
[Total 20 Marks]