-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathqueue.html
124 lines (124 loc) · 5.18 KB
/
queue.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
<html dir="ltr">
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type"/>
<title>Arc: Queue operations</title>
<link rel="shortcut icon" href="/assets/favicon.png">
<link rel="stylesheet" type="text/css" href="code.css">
<link href="/assets/bootstrap.css" rel="stylesheet">
</head>
<body style='margin:12px 50px 0'>
<div class="navbar navbar-inverse">
<div class="navbar-inner">
<ul class="nav navbar-nav">
<li><a href="/ref/">Arc 3.1</a>
<li><a href="http://tryarc.org">Try it</a></li>
<li><a href="http://github.com/arclanguage/anarki">Get it</a></li>
<li><a href="http://ycombinator.com/arc/tut.txt">Tutorial</a></li>
<li><a href="http://arclanguage.org/forum">Forum</a></li>
</ul>
</div>
</div> <!-- end of navbar -->
<div class="links">Previous: <a href="tree.html">Trees</a>
Up: <a href="index.html">Contents</a>
Next: <a href="error.html">Error handling</a>
</div>
<h1 class="links">Queue operations</h1>
Arc implements a queue datatype, which is useful to add and remove elements in a first-in-first-out order. The queue datatype provides two advantages over using a plain list. The queue provides constant-time operations to add and remove elements and to determine the queue length. The queue also provides atomic access to its contents.
<p>Internally the queue is implemented by a three-element list. The first element is the queue's contents as a list. The second element is a reference to the last element in the list. The third element is the length of the queue. By maintaining a reference to the end of the queue, an element can be added to the end of the queue in constant time, without traversing the whole list. By storing the length explicitly, the length can also be returned in constant time. For example, the following shows a queue with two elements:
<pre class="repl">
arc> (let q (queue) (enq 'a q) (enq 'b q) q)
((a b) (b) 2)
</pre>
<p>
Most Arc operations do not have any "knowledge" of a queue, and if applied to a queue will act on the list implementing the queue; the results are likely to be undesired. The <code>qlist</code> operation should be used to access the contents of the queue.
<pre class="repl">
arc> (do (= q (queue)) (enq 1 q) (enq 2 q))
(1 2)
arc> (apply + q)
Error: "+: expects type <number> as 1st argument, given: (1 2); other arguments were: (2) 2"
arc> (apply + (qlist q))
3
</pre>
<h2>Queue operations</h2>
<p><table class='arc'>
<tr>
<td class='arc'><a name='queue'></a>
<img src='proc.gif' title='Procedure'/>
<span class='op'>queue</span> <span class='args'></span>
<div class='desc'>Creates a queue.</div>
</td>
<td class='arc'><pre>
>(queue)
<span class="return">(nil nil 0)
</span></pre>
<pre>
>(type (queue))
<span class="return">cons
</span></pre>
</td></tr>
<tr>
<td class='arc'><a name='enq'></a>
<img src='proc.gif' title='Procedure'/>
<img src='destructive.gif' title='Destructive'/>
<span class='op'>enq</span> <span class='args'>obj q</span>
<div class='desc'>Adds obj to the end of queue q. Returns the queue as a list. The operation is wrapped in <code>atomic</code>.</div>
</td>
<td class='arc'><pre>
>(let q (queue) (enq 'a q) (enq '(1 2) q))
<span class="return">(a (1 2))
</span></pre>
</td></tr>
<tr>
<td class='arc'><a name='enq-limit'></a>
<img src='proc.gif' title='Procedure'/>
<img src='destructive.gif' title='Destructive'/>
<span class='op'>enq-limit</span> <span class='args'>obj q [limit]</span>
<div class='desc'>Adds obj to the queue q. If the new length would exceed the limit, the first element is dequeued. The new contents of the queue is returned as a list. Note that the length of the queue will either grow by one or remain constant; the queue will not be shortened to the limit. The operation is wrapped in <code>atomic</code>.</div>
</td>
<td class='arc'><pre>
>(let q (queue)
(enq-limit 'a q 2)
(enq-limit 'b q 2)
(enq-limit 'c q 2))
<span class="return">(b c)
</span></pre>
</td></tr>
<tr>
<td class='arc'><a name='deq'></a>
<img src='proc.gif' title='Procedure'/>
<img src='destructive.gif' title='Destructive'/>
<span class='op'>deq</span> <span class='args'>q</span>
<div class='desc'>Removes the first element from the queue q and returns the removed element. The operation is wrapped in <code>atomic</code>.</div>
</td>
<td class='arc'><pre>
>(let q (queue) (enq 'a q) (enq 4 q) (deq q))
<span class="return">a
</span></pre>
</td></tr>
<tr>
<td class='arc'><a name='qlen'></a>
<img src='proc.gif' title='Procedure'/>
<span class='op'>qlen</span> <span class='args'>q</span>
<div class='desc'>Returns the length of queue q.</div>
</td>
<td class='arc'><pre>
>(let q (queue) (enq 'a q) (enq 4 q) (deq q) (qlen q))
<span class="return">1
</span></pre>
</td></tr>
<tr>
<td class='arc'><a name='qlist'></a>
<img src='proc.gif' title='Procedure'/>
<span class='op'>qlist</span> <span class='args'>q</span>
<div class='desc'>Returns the contents of queue q as a list.</div>
</td>
<td class='arc'><pre>
>(let q (queue) (enq 'a q) (enq '(1 2) q) (qlist q))
<span class="return">(a (1 2))
</span></pre>
</td></tr>
</table>
<p>
Copyright 2008 Ken Shirriff.
</body>
</html>