Data Structures and Algorithms - Module 3, Lesson 2

Study Notes

A Stack is an Abstract Data Type (ADT) commonly used in programming.
It's named "Stack" because it can be visually represented as a stack of items, such as plates.
A Stack is a linear data structure, like a list, operating on a "Last-In, First-Out" (LIFO) principle.
- The last item added is the first one removed
Operations:
- PUSH: Adding an element to the top of the stack
- POP: Removing and returning the element from the top of the stack
- PEEK: Viewing the element at the top; does not remove the element
Additional methods to implement a stack:
- isEMPTY(): Checks if the stack is empty
- isFULL(): Checks if the stack is full
- COUNT(): Returns the number of elements in the stack
- CLEAR(): Removes all elements from the stack
- CONTAINS(T): Checks if the stack contains a given element

Stack Overflow: Occurs when attempting to push an element onto a full stack
Stack Underflow: Occurs when attempting to pop an element from an empty stack

PUSH operation:
- Check if the stack is full
  - If full, print "overflow" and terminate the program
- Otherwise: increment the top pointer and insert the element in the stack
POP operation:
- Check if the stack is empty
  - If empty, print "underflow" and terminate
- Otherwise: Retrieve the top element and decrement the top pointer then return the element.
PEEK Operation: Retrieve the top element without removing from the stack
isEMPTY operation: Check if 'top' is less than 1.
- return TRUE if it is; otherwise, return FALSE
isFULL operation: Check if 'top' is equal to MAXIMUM SIZE.
- return TRUE if it is; otherwise, return FALSE