Python Queue Example

Python Queue Example

Queues are a linear abstract data type with some key differences between stacks. Queues hold a collection of items in the order in which they were added. Items that are added to the back of a queue and removed from the front of the queue. You run into queues all the time. The last time you went grocery shopping you likely had to wait in a line to check out. If you think of a queue as a line of customers, a customer adds themselves to the end of the line and eventually leaves from the front of the line. This is called first-in-first-out or FIFO. This is different from stacks which are last-in-first-out. In addition, queues also preserve order so when you think about people joining a line, the order is preserved there as well. Now let’s look at examples of a queue in Python.

A Queue Class

python real world queue example

For this example of a queue in Python, we’ll use a class that will have all the methods needed to implement the functions of a queue. The class will simply be named Queue, and we’ll represent our queue as a list. In the __init__ method, we can initialize items to an empty list. To set up the basic functionality needed to get things into and out of our queue, we can stub out an enqueue() for adding and a dequeue() for removing. The enqueue() method needs a parameter of item so that we can add it to the queue. The dequeue() method doesn’t need an item parameter because we’re always going to be popping off the end of the list which automatically takes the last item of the list for us. To check on want the next item in the queue that’s going to be removed we can use a peek() method. We also want to be able to check for the size of the queue using size(), and whether the queue is empty using is_empty().

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

    def enqueue(self, item):
        pass

    def dequeue(self):
        pass

    def size(self):
        pass

    def peek(self):
        pass

    def is_empty(self):
        pass

enqueue()

We can now start coding the methods we need for our Queue class. We’ll start with the enqueue() method. For this method, we have to pass in as a parameter the item that we want to add into the queue. Inside the body of our method, we’re want to insert this item into the list in a queue-like fashion. With a queue, we will not be appending the item to the end of the list, like is done with a stack. We want to insert the item into the zeroth index of the list, or in other words the very first position of the list. The reason we do that is that we want to save the end of the list for popping items off and use the front of the list for inserting.

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

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        pass

    def size(self):
        pass

    def peek(self):
        pass

    def is_empty(self):
        pass

We can go back to the terminal to test this out in the interactive Python shell. We create a Queue object first and then enqueue an item into it. First, we put the string ‘Got in line first’ into the queue. This would be the first item to be processed from the queue. Then we add another string ‘Second in line’. Finally, we add the string ‘Last in line’. Now we can check the contents of the items, and we can see that they are in the correct order. If this was a line at the store, the items on the right will be processed first.

python enqueue method of queue class

dequeue()

Now let’s create the dequeue() method which will help us get items out of the queue. The front of the queue is actually the end of the list. Since this is the case, we can use the list’s built-in pop() method, and we’ll always get back the front-most item of the queue because the pop method always returns the last item in the list. Before you go trying to take items out of the queue, however, you should make sure there are some items to process from the queue. If you try to pop on an empty queue, you’ll get an error.

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

    def enqueue(self, item):
        self.items.insert(0, item)

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

    def size(self):
        pass

    def peek(self):
        pass

    def is_empty(self):
        pass

Once again we’ll test this out in the interactive Python interpreter. We create a new Queue, then add some items to it. These are the ‘First’, ‘Second’, and ‘Third’ strings. We confirm the items are now in the queue, and in the order we expect. Now once we start calling the dequeue() method, the right-most, or first, item should be processed. We see that this is the case and when continuing to call the dequeue() method, the items in the queue are processed just like a line at the grocery store.

python dequeue method of queue class

size()

The size() method of the Queue class is really quite easy. All it needs to do is return the length of the items in the queue list.

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

    def enqueue(self, item):
        self.items.insert(0, item)

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

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

    def peek(self):
        pass

    def is_empty(self):
        pass

Testing the size() method shows that it is working correctly.

size method for python queue

peek()

This method is used when we just want to look at what the next item in the queue is that’s going to be processed next. All that needs to be done is to return the last item in the list because that last item in the list is the item that’s going to get removed next. To ensure you do not get a list index out of range error, you’ll want to check if there are items to peek at before peeking. We can handle this situation in our code by saying that as long as there are items in the list show us the last item in the list. This works a little bit like dequeue() but the difference is that peek() leaves the queue intact, while dequeue() is actually processing or removing an item when it is called.

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

    def enqueue(self, item):
        self.items.insert(0, item)

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

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

    def peek(self):
        if self.items:
            return self.items[-1]
        else:
            return None

    def is_empty(self):
        pass

python peek into queue

is_empty()

The last method we’ll look at determines if the queue is empty or not. This is done by simply returning an equality check of self.items == []. In other words, if items is equal to an empty list, then True is returned. If items does not equal an empty list, False is returned.

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

    def enqueue(self, item):
        self.items.insert(0, item)

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

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

    def peek(self):
        if self.items:
            return self.items[-1]
        else:
            return None

    def is_empty(self):
        return self.items == []

is the python queue empty

Example of a print queue

With our new knowledge of how Queues work, let’s look at a more real-world scenario where one might encounter a queue. Think about when you print a document to a shared printer. If there are print jobs ahead of yours, it might take a little bit of time before your print job gets processed. That is how a queue works. You have to get in line at the end and wait for those in front of you to be processed. The following code shows how you might implement a queue for printing using three Python classes named PrintJob, PrintQueue, and Printer. The PrintQueue class makes use of the familiar queue methods of enqueue(), dequeue(), and is_empty(). For the PrintJob class, there is some logic that determines how many pages are left to print. In this example, we are only printing up to 5 pages. If a page gets printed, then the page count is decremented and once there are no more pages, then the printing is finished. The Printer class has logic to understand what PrintJob it is currently working on. These classes interact with each other since the Printer class is able to get the next job by dequeuing from a non-empty PrintQueue object.

import random


class PrintQueue:

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

    def __str__(self):
        pass

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def is_empty(self):
        return self.items == []


class PrintJob:

    def __init__(self):
        self.pages = random.randint(1, 6)

    def __str__(self):
        return f'PrintJob({self.pages})'

    def print_page(self):
        if self.pages > 0:
            self.pages -= 1

    def check_complete(self):
        if self.pages == 0:
            return True
        return False


class Printer:

    def __init__(self):
        self.current_job = None

    def get_job(self, print_queue):
        try:
            self.current_job = print_queue.dequeue()
        except IndexError:
            return "No more jobs to print."

    def print_job(self, job):
        while job.pages > 0:
            job.print_page()

        if job.check_complete():
            return "Printing complete."
        else:
            return "An error occurred."

Here is the code in action. We set up two print jobs of j1 and j2. Then we instantiate a print queue. using the queue, we enqueue the two jobs into the print queue. Now we set up a printer object via the Printer() class. To get the first job to print, we call the printer.get_job() method while passing in the queue itself. From there, we print the current job using the printer.print_job() method while passing in the current job. We can see that this first job only had 1 page and was printed out successfully. The next thing to do is grab the next job in the queue and print that one out. We see 5 pages printed out. Lastly, we try to get any more jobs from the queue, but we see that there are no more jobs to print since we have emptied the queue.

python queue real world example

Python Queue Example Summary

In this tutorial, we learned about the queue which is an abstract data type or a linear data structure. We saw how to build a queue using Python classes, and then how to implement a real-world scenario of a queue using a Printing example. Other uses of a queue in computer science include serving requests on a single shared resource, like a CPU task, or a call center software application that uses Queues to hold people calling them in order, until a service representative is free. You certainly have heard the message, your call will be answered in the order it was received. Another example might be the handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive. A one-way street is also an example of a queue where the first car to enter the one-way street is also the first car to exit the one-way street. You get the idea, but one last example of a queue is an automated car wash building. The first car to enter the building and get washed is also the first car to exit the building clean and shiny.