forked from ninas/umonya_notes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathqueues.html
132 lines (108 loc) · 5.01 KB
/
queues.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Introductory Programming in Python: Advanced Data Structures: Queues</title>
<link rel='stylesheet' type='text/css' href='style.css' />
<meta http-equiv='Content-Type' content='text/html; charset=utf-8' />
<script src="animation.js" type="text/javascript">
</script>
</head>
<body onload="animate_loop()">
<div class="page">
<h1>Introductory Programming in Python: Lesson 29<br />
Advanced Data Structures: Queues</h1>
<div class="centered">
[<a href="classes.html">Prev: Classes and Objects</a>] [<a href="index.html">Course Outline</a>] [<a href="stacks.html">Next: Advanced Data Structures: Stacks</a>]
</div>
<h2>First come, First Served</h2>
<p>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'.</p>
<p>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.</p>
<blockquote class='problem'>
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.
</blockquote>
<p>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.</p>
<h2>Implementing a Queue Using a List</h2>
<p>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</p>
<pre class='listing'>
NEWORDER
item description (cost)
[item description (cost)]
[item description (cost)]
ENDORDER
</pre>
<p>and that the display in the kitchen is connected directly to the
server.</p>
<pre class='listing'>
#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
<b>orderqueue = []</b>
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()
<b>orderqueue.append((ordernum, order))</b>
ordernum += 1
displayqueue()
elif line == "PROCESSED":
<b>del orderqueue[0]</b>
displayqueue()
else:
print "Warning: ", line.rstrip()
</pre>
<p>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.</p>
<h2>Exercises</h2>
<div class="centered">
[<a href="classes.html">Prev: Classes and Objects</a>] [<a href="index.html">Course Outline</a>] [<a href="stacks.html">Next: Advanced Data Structures: Stacks</a>]
</div>
</div>
<div class="pagefooter">
Copyright © James Dominy 2007-2008; Released under the <a href="http://www.gnu.org/copyleft/fdl.html">GNU Free Documentation License</a><br />
<a href="intropython.tar.gz">Download the tarball</a>
</div>
</body>
</html>