Chapter 36 - Stacks Flashcards Preview

A OCR Computer Science A level > Chapter 36 - Stacks > Flashcards

Flashcards in Chapter 36 - Stacks Deck (21)
Loading flashcards...
1
Q

What is a stack?

A

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

2
Q

What is LIFO?

A

» 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

3
Q

What is the main purpose of stacks?

A

» 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

4
Q

What are the 2 ways stacks can be implemented as?

A

» Dynamic
» Static

5
Q

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

A

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

6
Q

What does push(item) do?

A

» Adds a new item to the top of the stack

7
Q

What does pop() do?

A

» Removes and returns the top item from the stack

8
Q

What does peek() do?

A

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

9
Q

What does isEmpty() do?

A

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

10
Q

What does isFull() do?

A

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

11
Q

How can we test whether a stack is full?

A

» Examining the value of the stack pointer

12
Q

What is a stack overflow?

A

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

13
Q

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

A

» -1

14
Q

What is stack underflow?

A

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

15
Q

What is the call stack?

A

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

16
Q

What is a call stack made up of?

A

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

17
Q

How are local variables held in a stack?

A

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

18
Q

What 3 operations can be performed on a stack?

A

» Pushing
» Pop
» Peek

19
Q

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

A

» 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

20
Q

Are stacks usually dynamic data structures?

A

» Yes

21
Q

What are 3 examples of data structures that are dynamic?

A

» Stack
» Graph
» List

Decks in A OCR Computer Science A level Class (75):