Chapter 36 - Stacks
No description yet. This curated deck is ready for daily study.
Card preview (21)
What is a stack?
» It is a LIFO data structure ( Last in First OUT)
What is LIFO?
» 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
What is the main purpose of stacks?
» 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
What are the 2 ways stacks can be implemented as?
» Dynamic » Static
What are the 2 additional variables when a stack is implemented as static(array)?
» A pointer to the top of the stack » A pointer holding the size of the array(maximum size of the stack)
What does push(item) do?
» Adds a new item to the top of the stack
What does pop() do?
» Removes and returns the top item from the stack
What does peek() do?
» Returns the top item from the stack but does not remove it
What does isEmpty() do?
» Check whether the stack is empty, and returns a Boolean value
What does isFull() do?
» Check whether the stack is full, and returns a Boolean valu
How can we test whether a stack is full?
» Examining the value of the stack pointer
What is a stack overflow?
» Where there is an attempt to push another item into the stack when it is already full
What is the value of the stack pointer if the stack is empty?
» -1
What is stack underflow?
» When there is an attempt to pop an item when the stack is empty
What is the call stack?
» Keeps track of the address of the instruction that control the subroutine, and should return to when the subroutine adds
What is a call stack made up of?
» Stack frames » Each stack frame corresponds to a call to a subroutine which has not yet terminated
How are local variables held in a stack?
» Held in a stack » Values are lost when a subroutine ends - as they are popped of the stack
What 3 operations can be performed on a stack?
» Pushing » Pop » Peek
What are the steps to push an item to a stack?
» 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
Are stacks usually dynamic data structures?
» Yes
What are 3 examples of data structures that are dynamic?
» Stack » Graph » List