ADT Stack, Queue, and Binary Tree Features
Stacks
A stack is a fundamental abstract data structure that operates on a LIFO principle.
LIFO
Last-in, First-out principle.
This means that the last element added to the stack is the first one to be removed.
Analogy- A stack is like a stack of plates.
- You can only add or remove the top plate, which makes it easy to manage but limits access to other plates.
Key Characteristics of a Stack
- LIFO Order: Elements are added and removed from the top of the stack.
- Limited access: Only the top element is accessible at any given time.
- Dynamic size: Stacks can grow or shrink depending on the implementation (linked list) or have a fixed size (array).
Core Operations of a Stack
- Push: Adds an element to the top of the stack.
- Pop: Removes and returns the top element of the stack.
- Peek (or Top): Returns the top element without removing it.
- isEmpty: Checks if the stack is empty, returning true or false..
In IB's official pseudocode, stacks have methods:
- push()
- pop()
- isEmpty()
Recursive functions use the call stack, a special stack in memory, to keep track of function calls and their local variables:
- Stacks are used to store return addresses when a function is called.
- This ensures that the program can return to the correct location after the function completes.
- When a function is called, its return address and local variables are pushed onto the stack.
- When the function returns, these are popped off, restoring the previous state.
You can experiment with call stacks on websites like pythontutor.com.
Example- Stacks are used in applications like text editors to implement undo functionality.
- Each action is pushed onto a stack, and undoing an action involves popping it off and reversing it.
- In web browsers, the back button uses a stack to store previously visited pages, allowing you to navigate backwards.
Queues
A queue is a fundamental abstract data structure that operates on a FIFO principle.
FIFO
First-In, First-Out principle.
This means that the first element added to the queue is the first one to be removed.
AnalogyA queue is like a line at a coffee shop: customers join at the back and wait until they are next to the counter to make an order.
Example
Key Characteristics of a Queue
- FIFO order: Elements are added at the rear and removed from the front.
- Linear structure: Elements are arranged in a linear order, with restricted access to the front and rear.
