What type of data structure is a stack?
A stack is LIFO type of data structure
Last in first out
What are some real life applications of stacks?
- used in calculations of reverse polish notation
- used in recursive algorithms
- Can hold information when subroutines are called
Is a stack a dynamic or static type of data structure?
It can be implemented as either
Explain how a stack could be implemented as a static data structure?
Could do this using a (static) array and two variables. One that holds the index of the pointer and one that holds the size of the list
What are the 5 operations that could be carried out on a stack data structure?
- pop()
- push(item)
- peek()
- isEmpty()
- isFull()
What does the pop() operation do?
It removes and returns the top item from the stack
What does the push(item) operation do?
It adds a new item to the top of the stack
What does the peek() operation do?
It returns the top item from the stack but does not remove it
What does the isEmpty() operation do?
tests to see if the stack is empty
What does the isFull() operation do?
tests to see if the stack is full
What could cause an overflow when implementing a stack using an array?
If an item is appended to a full list of n items, the pointer will go up to n+1, causing an error as the item can’t be added to the list
What could cause an underflow when implementing a stack using an array?
If an item is removed from an empty list, this will cause an error as there will be no items left to remove and the pointer will become -1
What is a major use of a call stack?
Stores information about the active subroutines while the program is running
What does the call stack keep track of?
It keeps track of the return addresses (of several nested subroutines) As each subroutine completes each address is popped off the stack.
Why store local variables in a call stack?
Because it’s more efficient than using dynamic memory allocation
What is a call stack composed of?
Stack frames. Each stack frame corresponds to call to a subroutine.
What are the three things a stack frame holds?
Return addresses
Local Variable
Parameters
