Introductory Programming in Python: Lesson 29
Advanced Data Structures: Queues

First come, First Served

We are familiar with the concept of a queue from every bank and government department in the world. We go, stand in a line, and are served, or dis-served as the case may be, when we reach the front. What this implies, is that the order in which people are served, is the order in which they join the queue, commonly referred to in English as 'First come, first served'. In programming we prefer the phrase 'First in, first out'.

Looking at the concept of a queue, we notice three things. We have a front position, i.e. the next object to be served, and end of queue, and a preservation of the order in which objects are added to queue. This seems to lend itself to the idea of a list, which has a first position, index 0, and end to which we can add, using the append method, and preserves the order of the objects it contains.

A small Chinese take out store has recently become very busy. They have asked you to write the software to control the order system. They have installed a computer monitor in the kitchen which they want to display orders to the kitchen staff as they are made, and which the kitchen staff can delete when they have been processed, and three tills at the front counter accepting orders. They want their counter staff to be able to punch in an order, have that order automatically assigned a number which will be printed on a receipt given to the customer, and the orders to be displayed in a list ordered oldest to newest on the kitchen monitor.

The above problem represents a perfect example of a queue. It also highlights the idea that queues are most often used as a way of passing messages between multiple programs, e.g. three copies of the same program each controlling the tills, the program controlling the kitchen display, and the server controlling the queue. For the moment we are going to focus on the server program, which must accept messages describing orders, accept messages indicating the next order has been prepared and is ready, and send messages to the kitchen display.

Implementing a Queue Using a List

As mentioned earlier, we could simply use a list to handle the queue. We're going to assume that we have one pipe available to which the till programs can write order messages of the form

NEWORDER
item description (cost)
[item description (cost)]
[item description (cost)]
ENDORDER

and that the display in the kitchen is connected directly to the server.

#server.py: A small take out order queue server

def displayqueue():
    print "\n\n\n"
    for o in orderqueue:
        print o[0]
        for i in o[1]:
            print "\t%s"%i
            
ordernum = 1
orderqueue = []
pipe = open("orderpipe","r")

while True:
    line = pipe.readline()
    if line == "NEWORDER\n":
        order = []
        line = pipe.readline():
        while line != "ENDORDER\n":
            order.append(line.rstrip())
            line = pipe.readline()
        orderqueue.append((ordernum, order))
        ordernum += 1
        displayqueue()
    elif line == "PROCESSED":
        del orderqueue[0]
        displayqueue()
    else:
        print "Warning: ", line.rstrip()

Ignoring all the auxiliary stuff, we see on the first line in bold, we start with an empty queue. The second line in bold is where we add an order, which we have formed into a tuple of order number and a list of the items the order is composed of, to the end of the queue. The third line in bold is where we pull the first item in queue out, once the kitchen has prepared it.

Exercises