Section 7 Chapter 39 - Stacks

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

• Going back on a web browser - Undoing

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

• push • pop • peek • isEmpty • isFull

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

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

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

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

They are both stored in the stack frame

It is much faster than using the heap

• Local variables • Parameters • Return address