# Queue On List

**Queue on List:**

A Queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. It can be implemented using a list in Python, where elements are added at one end (rear) and removed from the other end (front).

**Implementation:**

Here's the implementation of a Queue using a list in Python:

```
class Queue:
def __init__(self):
self.queue = []
def is_empty(self):
return len(self.queue) == 0
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if self.is_empty():
return None
return self.queue.pop(0)
def front(self):
if self.is_empty():
return None
return self.queue[0]
def size(self):
return len(self.queue)
```

In this implementation, we have a `Queue`

class that encapsulates the list as the underlying data structure. The class provides the following methods:

`is_empty()`

: Checks if the queue is empty.`enqueue(item)`

: Adds an item to the rear of the queue.`dequeue()`

: Removes and returns the item at the front of the queue.`front()`

: Returns the item at the front of the queue without removing it.`size()`

: Returns the size (number of elements) of the queue.

**Time Complexity Analysis:**

The time complexity of the Queue operations implemented using a list is as follows:

`is_empty()`

: O(1) - Checking the length of a list takes constant time.`enqueue(item)`

: O(1) - Appending an item to the end of a list takes constant time.`dequeue()`

: O(n) - Removing an item from the front of a list requires shifting all other elements, resulting in a linear time complexity. In the worst case, we may need to shift all elements.`front()`

: O(1) - Accessing the first element of a list takes constant time.`size()`

: O(1) - Retrieving the length of a list takes constant time.

**Space Complexity Analysis:**

The space complexity of the Queue implementation using a list is O(n), where n is the number of elements in the queue. This is because we need to store all the elements in the list.

**Solving a Question:**

Let's solve a question using the Queue implemented using a list.

**Question: Implement Queue using Stacks**

Implement a Queue data structure using two stacks. The implementation should support the following operations: `push`

, `pop`

, `peek`

, and `empty`

.

**Solution:**

```
class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, x):
while self.stack1:
self.stack2.append(self.stack1.pop())
self.stack1.append(x)
while self.stack2:
self.stack1.append(self.stack2.pop())
def pop(self):
return self.stack1.pop()
def peek(self):
return self.stack1[-1]
def empty(self):
return len(self.stack1) == 0
```

In this solution, we implement the `MyQueue`

class using two stacks (`stack1`

and `stack2`

). The `push`

operation is implemented by moving all elements from `stack1`

to `stack2`

, adding the new element to `stack1`

, and then moving all elements back to `stack1`

to maintain the order. The `pop`

operation simply pops an element from `stack1`

. The `peek`

operation returns the top element of `stack1`

without removing it. The `empty`

operation checks if `stack1`

is empty.

**Time Complexity Analysis:**

The time complexity for the `push`

operation is O(n) because we move all elements from one stack to another and then back. In the worst case, we need to iterate through all elements in the stack.

The time complexity for the `pop`

, `peek`

, and `empty`

operations is O(1) since we directly access the top element of `stack1`

or check if it is empty.

**Space Complexity Analysis:**

The space complexity is O(n), where n is the number of elements in the stack. This is because we store all elements in `stack1`

and `stack2`

.

**Overall:**

The Queue implemented using a list provides an efficient way to simulate a Queue data structure in Python. The time complexity for the operations is reasonable, with O(1) for most operations except for `push`

, which has a time complexity of O(n) due to the need for element shifting. The space complexity is also reasonable at O(n). This implementation is suitable for scenarios where the number of `push`

operations is balanced with the number of `pop`

operations, and the number of elements in the Queue is not excessively large.

Let's solve a question using the Queue implemented using a list.

**Question: Number of Islands**

Given a 2D grid map of `'1'`

s (land) and `'0'`

s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Example:

```
Input:
[
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
```

**Solution:**

We can solve this problem using a breadth-first search (BFS) algorithm and a queue. We start from each `'1'`

cell and perform BFS to explore all connected `'1'`

cells and mark them as visited.

Here's the implementation:

```
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
num_rows, num_cols = len(grid), len(grid[0])
visited = set()
num_islands = 0
for i in range(num_rows):
for j in range(num_cols):
if grid[i][j] == '1' and (i, j) not in visited:
self.bfs(grid, i, j, visited)
num_islands += 1
return num_islands
def bfs(self, grid: List[List[str]], row: int, col: int, visited: set):
num_rows, num_cols = len(grid), len(grid[0])
queue = [(row, col)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited.add((row, col))
while queue:
curr_row, curr_col = queue.pop(0)
for dr, dc in directions:
new_row, new_col = curr_row + dr, curr_col + dc
if (
0 <= new_row < num_rows and
0 <= new_col < num_cols and
grid[new_row][new_col] == '1' and
(new_row, new_col) not in visited
):
queue.append((new_row, new_col))
visited.add((new_row, new_col))
# Test the solution with the given example
grid = [
["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"]
]
solution = Solution()
print(solution.numIslands(grid))
```

**Time Complexity Analysis:**

The time complexity of this solution is O(M * N), where M is the number of rows and N is the number of columns in the grid. We visit each cell in the grid exactly once.

**Space Complexity Analysis:**

The space complexity is O(M * N) as well. In the worst case, the queue can store all the cells in the grid if they are all `'1'`

s and connected.

Overall, this solution efficiently solves the "Number of Islands" problem using the Queue implemented using a list. The time complexity and space complexity are both reasonable and depend on the size of the grid.

Let's solve another question using the concept of Queue implemented using a list.

**Question: Binary Tree Level Order Traversal**

Given a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example:

```
Input: [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Output: [
[3],
[9,20],
[15,7]
]
```

**Solution:**

To perform a level order traversal of a binary tree, we can use a queue. We start by adding the root node to the queue. Then, while the queue is not empty, we dequeue a node, add its value to the current level list, and enqueue its left and right child nodes if they exist. We repeat this process until all nodes have been processed.

Here's the implementation:

```
from typing import List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
result = []
queue = [root]
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
# Test the solution with the given example
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
solution = Solution()
print(solution.levelOrder(root))
```

**Time Complexity Analysis:**

The time complexity of this solution is O(N), where N is the number of nodes in the binary tree. We visit each node once.

**Space Complexity Analysis:**

The space complexity is O(M), where M is the maximum number of nodes at any level of the binary tree. In the worst case, the queue can store all the nodes at the maximum level, which is M.

Overall, this solution efficiently performs the level order traversal of a binary tree using the Queue implemented using a list. The time complexity and space complexity are both reasonable and depend on the size of the tree.

I'll provide the code for the previous two solutions without using any external library and provide detailed comments explaining each step.

**Solution 1: Binary Tree Level Order Traversal**

```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
# Check if the root is None
if not root:
return []
# Initialize the result list and the queue
result = []
queue = [root]
# Perform level order traversal using a queue
while queue:
level = [] # Store the nodes at the current level
level_size = len(queue) # Get the size of the current level
# Process all nodes at the current level
for _ in range(level_size):
node = queue.pop(0) # Dequeue a node
level.append(node.val) # Add the node value to the level list
# Enqueue the left and right child nodes if they exist
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level) # Add the level list to the result list
return result
```

**Solution 2: Minimum Depth of Binary Tree**

```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def minDepth(self, root: TreeNode) -> int:
# Check if the root is None
if not root:
return 0
queue = [(root, 1)] # Initialize the queue with the root node and its depth
# Perform level order traversal using a queue
while queue:
node, depth = queue.pop(0) # Dequeue a node and its depth
# Check if the current node is a leaf node
if not node.left and not node.right:
return depth
# Enqueue the left and right child nodes with their depths
if node.left:
queue.append((node.left, depth + 1))
if node.right:
queue.append((node.right, depth + 1))
```

Both solutions follow a similar approach of performing a level order traversal using a queue. The first solution returns the level order traversal of the binary tree as a list of lists, while the second solution finds the minimum depth of the binary tree.

The time complexity for both solutions is O(N), where N is the number of nodes in the binary tree. We visit each node once during the level order traversal.

The space complexity for both solutions is O(M), where M is the maximum number of nodes at any level of the binary tree. In the worst case, the queue can store all the nodes at the maximum level, which is M.

These solutions demonstrate the use of queues to solve tree-related problems efficiently without relying on external libraries.

Here's the code for the "Number of Islands" problem without using any external library, along with detailed comments explaining each step:

```
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# Check if the grid is empty
if not grid:
return 0
# Get the dimensions of the grid
rows = len(grid)
cols = len(grid[0])
# Initialize a counter for the number of islands
num_islands = 0
# Define the directions for exploring neighboring cells
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
# Helper function to perform DFS on the grid
def dfs(row, col):
# Check if the current cell is within the grid bounds
if row < 0 or row >= rows or col < 0 or col >= cols:
return
# Check if the current cell is land
if grid[row][col] == "1":
# Mark the current cell as visited
grid[row][col] = "0"
# Explore the neighboring cells in all directions
for d in directions:
new_row = row + d[0]
new_col = col + d[1]
dfs(new_row, new_col)
# Traverse the entire grid and perform DFS on unvisited land cells
for row in range(rows):
for col in range(cols):
if grid[row][col] == "1":
num_islands += 1
dfs(row, col)
return num_islands
grid = [
["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"]
]
solution = Solution()
num_of_islands = solution.numIslands(grid)
print("Number of islands:", num_of_islands)
Number of islands: 1
```

The code uses Depth-First Search (DFS) to traverse the grid and count the number of islands. It checks each cell in the grid and if it is a land cell ("1"), it marks it as visited and explores its neighboring cells using DFS. By performing this operation on all unvisited land cells, we can count the number of islands.

The time complexity of the solution is O(M * N), where M is the number of rows and N is the number of columns in the grid. We visit each cell once during the traversal.

The space complexity is O(M * N) as well. This is due to the recursive calls in the DFS function, which can go as deep as the size of the grid in the worst case.

You can use the `numIslands`

function of the `Solution`

class to find the number of islands in a given grid. The function takes the grid as input and returns the count of islands.

To use this code, you can create an instance of the `Solution`

class and call the `numIslands`

function, passing the grid as an argument. For example:

```
```

The code uses Depth-First Search (DFS) to traverse the grid and count the number of islands. It checks each cell in the grid and if it is a land cell ("1"), it marks it as visited and explores its neighboring cells using DFS. By performing this operation on all unvisited land cells, we can count the number of islands.

The time complexity of the solution is O(M * N), where M is the number of rows and N is the number of columns in the grid. We visit each cell once during the traversal.

The space complexity is O(M * N) as well. This is due to the recursive calls in the DFS function, which can go as deep as the size of the grid in the worst case.