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 first3. Queues
to leave4. 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 pointer17. 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 set22. 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 be23. 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.