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.