Chapter 36 - Stacks

Question 1

What is a stack?

Answer 1

» It is a LIFO data structure ( Last in First OUT)

Question 2

What is LIFO?

Answer 2

» Items are added to the top and removed from the top
» Last item to be pushed onto the stack must also be the first item to be popped fof

Question 3

What is the main purpose of stacks?

Answer 3

» Hold return address when subroutines are called
» Stacks are used to track the flow of the program
»When subroutines end, the processor must return the PC to its previous state
» We can achieve this using a stack

Question 4

What are the 2 ways stacks can be implemented as?

Answer 4

» Dynamic
» Static

Question 5

What are the 2 additional variables when a stack is implemented as static(array)?

Answer 5

» A pointer to the top of the stack
» A pointer holding the size of the array(maximum size of the stack)

Question 6

What does push(item) do?

Answer 6

» Adds a new item to the top of the stack

Question 7

What does pop() do?

Answer 7

» Removes and returns the top item from the stack

Question 8

What does peek() do?

Answer 8

» Returns the top item from the stack but does not remove it

Question 9

What does isEmpty() do?

Answer 9

» Check whether the stack is empty, and returns a Boolean value

Question 10

What does isFull() do?

Answer 10

» Check whether the stack is full, and returns a Boolean valu

Question 11

How can we test whether a stack is full?

Answer 11

» Examining the value of the stack pointer

Question 12

What is a stack overflow?

Answer 12

» Where there is an attempt to push another item into the stack when it is already full

Question 13

What is the value of the stack pointer if the stack is empty?

Answer 13

» -1

Question 14

What is stack underflow?

Answer 14

» When there is an attempt to pop an item when the stack is empty

Question 15

What is the call stack?

Answer 15

» Keeps track of the address of the instruction that control the subroutine, and should return to when the subroutine adds

Question 16

What is a call stack made up of?

Answer 16

» Stack frames
» Each stack frame corresponds to a call to a subroutine which has not yet terminated

Question 17

How are local variables held in a stack?

Answer 17

» Held in a stack
» Values are lost when a subroutine ends - as they are popped of the stack

Question 18

What 3 operations can be performed on a stack?

Answer 18

» Pushing
» Pop
» Peek

Question 19

What are the steps to push an item to a stack?

Answer 19

» Check for stack overflow. Ouput an error if the stack is full
» Increment the stack pointer - so it points to the next available space in our array
» Insert the new data item at the location pointed by the stack pointer

Question 20

Are stacks usually dynamic data structures?

Answer 20

» Yes

Question 21

What are 3 examples of data structures that are dynamic?

Answer 21

» Stack
» Graph
» List