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
|
The ti(queue) class implements a i(queue data structure). Before using a
tt(queue) container the header file tthi(queue) must be included.
A queue is depicted in figure ref(queueFig).
figure(containers/queue)(A queue data-structure)(queueFig)
In figure ref(queueFig) it is shown that a queue has one point (the
em(back)) where items can be added to the queue, and one point (the em(front))
where items can be removed (read) from the queue. A tt(queue) is therefore
also called a emi(FIFO) data structure, for emi(first in, first out). It is
most often used in situations where events should be handled in the same order
as they are generated.
The following constructors, operators, and member functions are available
for the tt(queue) container:
itemization(
it() hi(queue) Constructors:
itemization(
it() The copy and move constructors are available;
it() A tt(queue) may be constructed empty:
verb(
queue<string> object;
)
As with the tt(vector), it is an error to refer to an element of an
empty queue.
)
it() The tt(queue) container only supports the basic container operators.
it() The following hi(member function)member functions are available for
queues:
itemization(
ithtq(back)(Type &back())(returns a
reference to the last element in the queue. It is the
i(responsibility of the programmer) to use the member only if the queue is
not empty.)
ithtq(empty)(bool empty())(returns
tt(true) if the queue contains no elements.)
ithtq(front)(Type &front())(returns a
reference to the first element in the queue. It is the responsibility of the
programmer to use the member only if the queue is not empty.)
COMMENT(verbinclude(-a queue/front.cc))
ithtq(pop)(void pop())(removes the element at the front of
the queue. Note that the element is em(not) returned by this member. Nothing
happens if the member is called for an empty queue. One might wonder why
tt(pop) returns tt(void), instead of a value of type tt(Type)
(cf. tt(front)). One reason is found in the principles of good software
design: functions should perform one task. Combining the removal and return of
the removed element breaks this principle. Moreover, when this principle is
abandoned tt(pop)'s implementation is always flawed. Consider the
prototypical implementation of a tt(pop) member that is supposed to return the
just popped value:
verb(
Type queue::pop()
{
Type ret(front());
erase_front();
return ret;
}
)
The venom, as usual, is in the tail: since tt(queue) has no control over
tt(Type)'s behavior the final statement (tt(return ret)) might throw. By that
time the queue's front element has already been removed from the queue and
so it is lost. Thus, a tt(Type) returning tt(pop) member cannot offer the
em(strong guarantee) and consequently tt(pop) should not return the former
tt(front) element. Because of all this, we must first use tt(front) and
then tt(pop) to obtain and remove the queue's front element.)
ithtq(push)(void push(value))(this member
adds tt(value) to the back of the queue.)
ithtq(size)(size_t size())(returns the
number of elements in the queue.)
)
)
Note that the queue does not support iterators or a subscript
operator. The only elements that can be accessed are its front and back
element. A queue can be emptied by:
itemization(
it() repeatedly removing its front element;
it() assigning an empty queue using the same data type to it;
it() having its destructor called.
)
|
