Collin:COCS-2436

# Stacks and Queues

## Objectives

1. Understand the concepts of stacks and queues, LIFO vs FIFO principles
2. Learn about the operations and applications of stacks and queues
3. Implement stacks and queues using arrays and linked lists
4. Explore the use of stacks and queues in various algorithms
5. Analyze time complexity of operations

---

## What is Stacks ?
- Definition of a stack: LIFO (Last-In-First-Out) data structure
- Stack is a linear data structure that stores it’s elements in sequential order similar to Arrays. 
- When adding or removing elements, it follows a particular order called LIFO - which is short for Last In First Out.
- Real-world examples of stacks (e.g., stack of plates)

![stack](assets/stack.png)

---

## Stack Operations

- Push: Add an element to the top of the stack
- Pop: Remove and return the top element from the stack
- Peek: Return the top element without removing it
- IsEmpty: Check if the stack is empty

![stack](assets/stack1.png)

---

## Implementing Stacks

- Array-based implementation of stacks
    - Advantages: Constant-time operations
    - Limitations: Fixed size
- Linked list-based implementation of stacks
    - Advantages: Dynamic size, constant-time operations
- Implementing generic stacks in Java

~.~

---

## Applications of Stacks

- Expression evaluation 
  - Evaluating mathematical expressions, such as infix (e.g., 2 + 3 * 4) or postfix (e.g., 2 3 4 * +), can be done efficiently using a stack.  
  - When processing an infix expression, a stack is used to keep track of the operators, allowing the operands to be processed in the correct order to obtain the final result.    
  - For postfix expressions, the stack is used to store the operands, and the operators are applied directly to the operands on the stack, simplifying the evaluation process.  
  - Using a stack for expression evaluation ensures that the operations are performed in the correct order, following the rules of mathematical precedence and associativity.

---

- [Backtracking algorithms](https://www.geeksforgeeks.org/backtracking-algorithms/#)
  - Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally by trying different options and undoing them if they lead to a dead end. It is commonly used in situations where you need to explore multiple possibilities to solve a problem, like searching for a path in a maze or solving puzzles like Sudoku. 
  - Stacks are used to keep track of the choices made and the state of the problem at each step.  
  - The LIFO (Last-In-First-Out) nature of stacks allows the algorithm to easily undo the most recent decisions and explore alternative paths.
  - Solving puzzles (e.g., Sudoku, crossword puzzles), Scheduling problems, Resource allocation problems
  - Finding the shortest path through a maze  
  
    ![img.png](assets/backT.gif)
---

- Function call management or **Call Stack**
  - The Call Stack is a stack data structure that keeps track of the functions or methods being called in a program.
  - When a function is called, it is "pushed" onto the top of the Call Stack.
  - When a function completes, it is "popped" off the top of the Call Stack, and the program returns to the previous function that called it.
  - The Call Stack ensures that the program returns to the correct point after a function has completed, allowing it to execute the rest of the program correctly.
  - This makes the Call Stack a crucial application of the stack data structure in programming, as it enables the proper flow of function calls and returns.

---

- System uses call stack to manage recursive method calls
    * Each call creates new stack frame storing local variables & parameters
    * Stack frames track return addresses and return values
    
    ```java
    // Example: Factorial using recursion
    int factorial(int n) {
        if (n == 0) return 1;     // base case
        return n * factorial(n-1); // recursive case
    }
    ```
    - Stack frames for factorial(3):
    ```
    [factorial(0)] → 1
    [factorial(1)] → 1 * 1
    [factorial(2)] → 2 * 1
    [factorial(3)] → 3 * 2
  ```

- Key Points:
    * Recursive solutions naturally use stack properties
    * Stack handles state management automatically
    * Consider stack overflow for deep recursion

---

## What is Queue?

- A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, Real-world examples of queue (e.g., waiting in line)
- Elements are added to the rear (or back) of the queue and removed from the front of the queue.
- The first element added to the queue will be the first one to be removed.
- Queues are often used to model real-world waiting lines or processing tasks in the order they were received.
- Queues are useful in scenarios where you need to process data or tasks in the order they were requested, such as print spoolers, customer service systems, and job scheduling.

![queue](assets/queue.png)
---
## Queue Operations
- Enqueue: Add an element to the rear of the queue
- Dequeue: Remove and return the element from the front of the queue
- Peek: Return the front element without removing it
- IsEmpty: Check if the queue is empty

![queueOps](assets/queue1.png)

---

## Implementing Queues
- Array-based implementation of queues
    - Challenges: Handling wrap-around
- Linked list-based implementation of queues
    - Advantages: Dynamic size, constant-time operations
- Implementing generic queues in Java

~.~

---

## Applications of Queues

- Call Center System
  - A call center system uses a queue to manage incoming calls from customers.
  - Calls are added to the queue in the order they are received, and agents can dequeue calls from the front of the queue to handle them.
  - This ensures that calls are processed in the order they were received, following the FIFO principle.
  - Load Balancing: The queue helps manage the flow of incoming calls by balancing the load between available agents and avoiding call drops during peak hours.
  - Prioritization: Some systems implement priority queues where urgent issues might get bumped up in the queue, but in general, queues ensure fairness by attending calls in the order they come in.

---

- Operating System Task/Job Scheduling
  - In an operating system, queues are used to manage tasks and jobs that need to be processed by the CPU.
  - The operating system maintains multiple queues for different types of tasks, such as system processes, user applications, and background tasks.
  - The CPU scheduler dequeues tasks from the front of the appropriate queue based on priority, time-sharing, or other scheduling algorithms.
  - Queues help ensure that tasks are processed fairly and efficiently, preventing resource starvation and improving system performance.
  - Task scheduling: The operating system uses queues to manage tasks and allocate CPU time based on priority, deadlines, and other criteria.

---

- Printer Queue/Print Spooling
  - In a printer queue or print spooler, documents are added to a queue in the order they are sent for printing.
  - The printer dequeues documents from the front of the queue and prints them one by one.
  - This ensures that documents are printed in the order they were submitted, following the FIFO principle.
  - Print spooling: The queue helps manage the flow of print jobs to the printer, allowing multiple users to submit documents for printing without interfering with each other's jobs.

--- 
- Message Bus/Event Handling Systems
  - Message bus systems and event handling systems use queues to manage the flow of messages and events between components.
  - Messages are enqueued in the order they are received and dequeued by the components for processing.
  - Queues help decouple the sender and receiver, allowing components to operate independently and handle messages asynchronously.
  - Event handling: Queues are used to manage events, such as user interactions, system notifications, and application updates, ensuring that events are processed in the order they occur.
---   
- Breadth-First Search (BFS) algorithm
  - The BFS algorithm uses a queue to explore nodes in a graph or tree level by level.
  - Starting from the root node, the algorithm enqueues neighboring nodes at each level and dequeues nodes to explore their children.
  - This process continues until all nodes have been visited, ensuring that nodes are visited in the order of their distance from the root.

---
## Depth-First Search (DFS) vs. Breadth-First Search (BFS)

```
      0
     / \
    1   2
   / \   \
  3   4   5
```

DFS would visit: 0, 1, 3, 4, 2, 5 (going deep first).  
BFS would visit: 0, 1, 2, 3, 4, 5 (going wide first).

#### Key Differences Between DFS and BFS

| Aspect | DFS (Stack-based) | BFS (Queue-based) |
|--------|-------------------|-------------------|
| Order | Explores deep before wide | Explores wide before deep |
| Memory | Lower for deep graphs | Lower for wide graphs |
| Find path | Any path quickly | Shortest path |
| Complete | May get stuck in infinite paths | Always finds solution if exists |
| Implementation | Uses Stack (LIFO) | Uses Queue (FIFO) |
| Applications | Topological sorting, Cycle detection | Shortest path, Network broadcasting |
||||

BFS is particularly useful for finding the shortest path in unweighted graphs, as it guarantees that when you first discover a node, you've reached it by the shortest possible path from the start.

---
## Stack vs. Queue: Side-by-Side Comparison

| Aspect | Stack | Queue |
|--------|-------|-------|
| **Access Pattern** | LIFO (Last-In-First-Out) | FIFO (First-In-First-Out) |
| **Main Operations** | Push, Pop, Peek | Enqueue, Dequeue, Peek |
| **End Access** | Single end (top) | Two ends (front, rear) |
| **Visualization** | ![Stack](assets/stack.png) | ![Queue](assets/queue.png) |
| **Real-world Analogy** | Stack of plates, Undo feature | Waiting line, Print queue |
| **Usage Example** | Function calls, Expression evaluation | Task scheduling, BFS |

---

## Time Complexity Analysis

#### Stack Operations

| Operation | Array-based | Linked List-based |
|-----------|----------|--------|
| Push      | O(1)*    | O(1)   |
| Pop       | O(1)     | O(1)   |
| Peek      | O(1)     | O(1)   |
| isEmpty   | O(1)     | O(1)   |
| Search    | O(n)     | O(n)   |

*O(n) when array needs to be resized
#### Queue Operations

| Operation | Array-based (Circular) | Linked List-based |
|-----------|---------|----------|
| Enqueue   | O(1)*   | O(1)     |
| Dequeue   | O(1)    | O(1)     |
| Peek      | O(1)    | O(1)     |
| isEmpty   | O(1)    | O(1)     |
| Search    | O(n)    | O(n)     |

*O(n) when array needs to be resized

---

## Stack and Queue Variations

#### Deque (Double-Ended Queue)
- Allows insertion and removal at both ends
- Can function as both stack and queue
- Operations: addFirst, addLast, removeFirst, removeLast
- Java implementation: `ArrayDeque<E>`

```java
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("First");    // Add to front
deque.addLast("Last");      // Add to rear
String first = deque.removeFirst();  // Remove from front
String last = deque.removeLast();    // Remove from rear
```
---
#### Priority Queue
- Elements have priorities assigned to them
- Higher priority elements are dequeued before lower priority ones
- Java implementation: `PriorityQueue<E>`

```java
// Min priority queue (smallest element first)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5); pq.add(2); pq.add(8);
System.out.println(pq.poll());  // Outputs: 2
```
---
#### Circular Queue
- Special case of array-based queue
- Efficiently uses array space by wrapping around
- Prevents shifting elements when dequeuing

~.~
---

## Stack Overflow and Underflow

#### Stack Overflow
- Occurs when trying to push onto a full stack
- Common in fixed-size implementations
- Causes:
  - Recursive functions with no base case
  - Infinite loops in recursive calls
  - Insufficient stack memory allocation
--- 
#### Stack Underflow
- Occurs when trying to pop from an empty stack
- Always check if stack is empty before popping

```java
// Safe pop operation
public T safePop() {
    if (isEmpty()) {
        System.out.println("Warning: Stack is empty");
        return null;
    }
    return pop();
}
```
---
## Queue Overflow and Underflow
- Similar concepts apply to queues
- Always check queue state before operations
- Implement proper error handling

---

## Visualizing Stack/Queue Operations

#### Stack Visualization
1. Push(A) → [A]
2. Push(B) → [A, B]
3. Push(C) → [A, B, C]
4. Pop() → [A, B], returns C
5. Push(D) → [A, B, D]
6. Pop() → [A, B], returns D
7. Pop() → [A], returns B
---- 
#### Queue Visualization
1. Enqueue(A) → [A]
2. Enqueue(B) → [A, B]
3. Enqueue(C) → [A, B, C]
4. Dequeue() → [B, C], returns A
5. Enqueue(D) → [B, C, D]
6. Dequeue() → [C, D], returns B
7. Dequeue() → [D], returns C

---

## Common Errors to Avoid
- Forgetting to check for empty stacks/queues
- Violating the stack/queue principles (LIFO/FIFO)
- Inefficient implementations leading to performance issues

---
## Knowledge Check: http://quiz.codewithme.com 
### OR
##### Visit gosocrative.com and enter room name cocs2436
---
# LABs