The Project | About Us | Contribute | Donations | License

HOME

In this section, we will provide a series of practical exercises to reinforce your understanding of queues. Each exercise will include a problem statement, followed by a detailed solution. We will also highlight common mistakes and provide additional tips to help you master the concepts.

Exercise 1: Implementing a Queue

Problem Statement

Implement a queue using a list in Python. Your queue should support the following operations:

enqueue(item): Add an item to the end of the queue.
dequeue(): Remove and return the item from the front of the queue. If the queue is empty, return None.
is_empty(): Return True if the queue is empty, otherwise return False.
size(): Return the number of items in the queue.

Solution

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            return None
        return self.items.pop(0)

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

    def size(self):
        return len(self.items)

# Example usage:
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
print(queue.size())     # Output: 2
print(queue.is_empty()) # Output: False

Explanation

enqueue(item): Adds an item to the end of the list using append().
dequeue(): Removes the first item from the list using pop(0). If the queue is empty, it returns None.
is_empty(): Checks if the list is empty by comparing its length to zero.
size(): Returns the length of the list.

Common Mistakes

Forgetting to check if the queue is empty before calling dequeue().
Using pop() without an index, which removes the last item instead of the first.

Exercise 2: Circular Queue Implementation

Problem Statement

Implement a circular queue using a fixed-size list (array). Your queue should support the following operations:

enqueue(item): Add an item to the end of the queue. If the queue is full, return False.
dequeue(): Remove and return the item from the front of the queue. If the queue is empty, return None.
is_empty(): Return True if the queue is empty, otherwise return False.
is_full(): Return True if the queue is full, otherwise return False.
size(): Return the number of items in the queue.

Solution

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = self.rear = -1

    def enqueue(self, item):
        if self.is_full():
            return False
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        return True

    def dequeue(self):
        if self.is_empty():
            return None
        item = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        return item

    def is_empty(self):
        return self.front == -1

    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front

    def size(self):
        if self.is_empty():
            return 0
        if self.rear >= self.front:
            return self.rear - self.front + 1
        return self.capacity - self.front + self.rear + 1

# Example usage:
cq = CircularQueue(3)
print(cq.enqueue(1))  # Output: True
print(cq.enqueue(2))  # Output: True
print(cq.enqueue(3))  # Output: True
print(cq.enqueue(4))  # Output: False (Queue is full)
print(cq.dequeue())   # Output: 1
print(cq.size())      # Output: 2
print(cq.is_empty())  # Output: False
print(cq.is_full())   # Output: False

Explanation

enqueue(item): Adds an item to the queue. If the queue is full, it returns False. Otherwise, it updates the rear index and inserts the item.
dequeue(): Removes the item from the front of the queue. If the queue is empty, it returns None. Otherwise, it updates the front index.
is_empty(): Checks if the queue is empty by comparing front to -1.
is_full(): Checks if the queue is full by comparing the next position of rear to front.
size(): Calculates the number of items in the queue based on the positions of front and rear.

Common Mistakes

Not handling the wrap-around condition correctly in enqueue() and dequeue().
Forgetting to reset front and rear to -1 when the queue becomes empty after a dequeue() operation.

Exercise 3: Priority Queue Implementation

Problem Statement

Implement a priority queue using a list of tuples in Python. Each tuple should contain an item and its priority. Your priority queue should support the following operations:

enqueue(item, priority): Add an item with a given priority to the queue.
dequeue(): Remove and return the item with the highest priority. If the queue is empty, return None.
is_empty(): Return True if the queue is empty, otherwise return False.
size(): Return the number of items in the queue.

Solution

class PriorityQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item, priority):
        self.queue.append((item, priority))
        self.queue.sort(key=lambda x: x[1], reverse=True)

    def dequeue(self):
        if self.is_empty():
            return None
        return self.queue.pop(0)[0]

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

    def size(self):
        return len(self.queue)

# Example usage:
pq = PriorityQueue()
pq.enqueue('task1', 1)
pq.enqueue('task2', 3)
pq.enqueue('task3', 2)
print(pq.dequeue())  # Output: 'task2'
print(pq.size())     # Output: 2
print(pq.is_empty()) # Output: False

Explanation

enqueue(item, priority): Adds a tuple (item, priority) to the queue and sorts the queue based on priority in descending order.
dequeue(): Removes and returns the item with the highest priority (first item in the sorted list). If the queue is empty, it returns None.
is_empty(): Checks if the queue is empty by comparing its length to zero.
size(): Returns the length of the queue.

Common Mistakes

Forgetting to sort the queue after adding a new item.
Using the wrong sorting order (ascending instead of descending).

Conclusion

In this section, we have covered various exercises to help you understand and implement different types of queues, including simple queues, circular queues, and priority queues. By practicing these exercises, you should have a solid understanding of how queues work and how to implement them in Python.

Next, we will move on to the next module, which focuses on trees, another fundamental data structure in programming.

Exercises with Queues

Exercise 1: Implementing a Queue

Problem Statement

Solution

Explanation

Common Mistakes

Exercise 2: Circular Queue Implementation

Problem Statement

Solution

Explanation

Common Mistakes

Exercise 3: Priority Queue Implementation

Problem Statement

Solution

Explanation

Common Mistakes

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Trees

Module 6: Graphs

Module 7: Conclusions and Additional Resources