Module 3 Algorithm Thinking Stack & Queue

Stack:

Untitled

Stack:
- Definition: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, where elements are added and removed from the same end called the top.
- Characteristics:
  - Elements can only be added or removed from the top of the stack.
  - Common operations include push (adding an element to the top), pop (removing the top element), and peek (viewing the top element without removing it).
- Use Cases: Function call stack, undo mechanisms, backtracking algorithms.
Use Cases:
- Function call stack in programming languages.
- Undo mechanisms in text editors.
- Backtracking algorithms.
Algorithms: Stack-based algorithms include Depth-First Search (DFS) and Backtracking.
Time Complexity:
- Push and pop operations: \(O(1)\).
- Searching for an element: \(O(n)\).

Python Code Example:

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if self.is_empty():
            return None
        return self.stack.pop()

    def is_empty(self):
        return len(self.stack) == 0

    def peek(self):
        if self.is_empty():
            return None
        return self.stack[-1]

# Example Usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3

Queue:
- Queue:
- Definition: A queue is a linear data structure that follows the First In, First Out (FIFO) principle, where elements are added at the rear (enqueue) and removed from the front (dequeue).
- Characteristics:
  - Elements are processed in the same order they were added, like waiting in line.
  - Common operations include enqueue (adding an element to the rear), dequeue (removing the front element), and peek (viewing the front element without removing it).
- Use Cases: Implementing BFS (Breadth-First Search), managing resources (e.g., CPU scheduling, printer queues), caching mechanisms (e.g., LRU cache).
- Use Cases:
  - Implementing BFS (Breadth-First Search) algorithm.
  - Managing resources (e.g., CPU scheduling, printer queues).
  - Caching mechanisms (e.g., LRU cache).
- Algorithms: BFS (Breadth-First Search), Queue-based traversal algorithms.
- Time Complexity:
  - Enqueue and dequeue operations: \(O(1)\).
  - Searching for an element: \(O(n)\).
- Python Code Example:
```
from collections import deque

# Example of using deque as a queue
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue.popleft())  # Output: 1
```

Difference between Stack and Queue Data Structures are as follows:

Stacks	Queues
A stack is a data structure that stores a collection of elements,
with operations to push (add) and pop (remove) elements from the top of
the stack.	A queue is a data structure that stores a collection of elements,
with operations to enqueue (add) elements at the back of the queue, and
dequeue (remove) elements from the front of the queue.
Stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list.	Queues are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list.
Stacks are often used for tasks that require backtracking, such as parsing expressions or implementing undo functionality.	Queues are often used for tasks that involve processing elements in a
specific order, such as handling requests or scheduling tasks.
Insertion and deletion in stacks takes place only from one end of the list called the top.	Insertion and deletion in queues takes place from the opposite ends
of the list. The insertion takes place at the rear of the list and the
deletion takes place from the front of the list.
Insert operation is called push operation.	Insert operation is called enqueue operation.
Stacks are implemented using an array or linked list data structure.	Queues are implemented using an array or linked list data structure.
Delete operation is called pop operation.	Delete operation is called dequeue operation.
In stacks we maintain only one pointer to access the list, called
the top, which always points to the last element present in the list.	In queues we maintain two pointers to access the list. The front
pointer always points to the first element inserted in the list and is
still present, and the rear pointer always points to the last inserted
element.
Stack is used in solving problems works on recursion.	Queue is used in solving problems having sequential processing.
Stacks are often used for recursive algorithms or for maintaining a history of function calls.	Queues are often used in multithreaded applications, where tasks are added to a queue and executed by a pool of worker threads.
Stack does not have any types.	Queue is of three types – 1. Circular Queue 2. Priority queue 3. double-ended queue.
Can be considered as a vertical collection visual.	Can be considered as a horizontal collection visual.
Examples of stack-based languages include PostScript and Forth.	Examples of queue-based algorithms include Breadth-First Search (BFS) and printing a binary tree level-by-level.

Applications of stack:

Some CPUs have their entire assembly language based on the concept of performing operations on registers that are stored in a stack.
Stack structure is used in the C++ run-time system.

Applications of queue:

Queue data structure is implemented in the hardware microinstructions inside a CPU.
Queue structure is used in most operating systems.