Section 7 Chapter 39 - Stacks

Question 1

Stack

Answer 1

A data structure that functions as an ordered collection of elements where elements can be added and removed in a “Last In, First out” way

Question 2

Applications of stacks (2)

Answer 2

• Going back on a web browser

- Undoing

Question 3

How to implement a stack

Answer 3

A list can be used to mimic a stack, with elements only being able to be either appended to the end, or removed from the end.
Alternatively a static array can be used with a pointer for the top of the stack

Question 4

Operations on a stack (5)

Answer 4

• push
• pop
• peek
• isEmpty
• isFull

Question 5

Overflow of a stack

Answer 5

A stack will have a maximum size. An attempt to add an element to a stack that would push the size past the limit will result in a stack overflow

Question 6

Underflow of a stack

Answer 6

Will occur if the stack is attempted to be popped while being empty

Question 7

Role of a stack in subroutine calls

Answer 7

A call stack is used when a program is running to keep track of addresses and instructions. When a subroutine is entered, its local variables, parameters and the return address are all added to the call stack (together these values form a stack frame). When the subroutine ends the stack frame is popped and the program jumps to the return address. If there are nested subroutines then the call stack may contain many stack frames

Question 8

Stack frame

Answer 8

A call stack is composed of stack frames. Each stack frame corresponds to a call to a subroutine which has not yet terminated.

Question 9

How parameters and local variables are stored

Answer 9

They are both stored in the stack frame

Question 10

Advantage of storing local variables in the stack

Answer 10

It is much faster than using the heap

Question 11

Contents of a stack frame

Answer 11

• Local variables
• Parameters
• Return address