Get startedGet started for free

Working with queues

1. Working with queues

Now, we'll discover queues, hash tables, and tree data structures. We'll then cover recursion.

2. Queues

In this video, we will work with queues. Queues are a data structure that follows the FIFO ordering principle, which stands for First-In-First-Out. The first inserted item is the first to be removed. Let's think of a line of people in a supermarket. The first person who joins the line is the first

3. Queues

to leave

4. Queues

the line.

5. Queues - structure

Here is a queue of restaurant orders.

6. Queues - structure

The beginning of the queue is called the head,

7. Queues - structure

and the end is called the tail.

8. Queues - features

In queues, as in stacks,

9. Queues - features

we can only insert data at the end of the queue. This operation is called enqueue. However, contrary to stacks,

10. Queues - features

we can only remove data from the head.

11. Queues - features

This operation is called dequeue. There are other kinds of queues: doubly ended, circular, and priority, but we won't study them.

12. Queues - real-world use cases use

Queues have many applications, like storing printing tasks in a printer. Documents are printed in the order they are received. Queues can also be implemented in applications where the order of user requests matters, like applications that sell tickets to a concert or offer taxi services.

13. Queues - implementation

Queues can be implemented using singly linked lists. To do this, we will use the familiar Node class. We will also define the Queue class, setting the head and tail to None.

14. Queues - enqueue

Let's implement the enqueue method for the Queue class. First, we create the new_node, and then check if the queue is empty. If it is,

15. Queues - enqueue

both the head and tail will point to the new_node.

16. Queues - enqueue

If the queue is not empty, the tail's next pointer

17. Queues - enqueue

will point to the new_node.

18. Queues - enqueue

Finally, the tail will point to the new_node.

19. Queues - dequeue

Let's implement the dequeue method to remove an element from a queue. In this case, we only act if the queue has elements.

20. Queues - dequeue

We create the current_node variable that points to the node we want to remove, the node at the head.

21. Queues - dequeue

Then, we move the head to the current_node's next node. Finally, we set

22. Queues - dequeue

current_node-dot-next to None. At this point, we need to check if our queue had one element at the beginning. If it did, we will be

23. Queues - dequeue

in the situation shown, with the head pointing to None and the tail pointing to the node we want to remove. In this case,

24. Queues - dequeue

we will need to set the tail to None.

25. SimpleQueue in Python

In Python, the queue module offers the Queue and SimpleQueue classes, which allow working with queues. We will focus on SimpleQueue, which offers fewer features than the Queue class, but is enough for the scope of this course. Let's import the queue module and create a new SimpleQueue. We can add elements using the put method, get the size of the queue using qsize, remove elements using get, which also returns the removed element, and check if the queue is empty, among other functionalities.

26. Let's practice!

Let's practice!

Create Your Free Account

or

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.