blob: d08c1cba9aa13ae74af9efd414b7db7d62e3d05c (
plain) (
blame)
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
|
// FILE: queue2.template
// TEMPLATE CLASS IMPLEMENTED: Queue<Item> (see queue2.h for documentation)
// This file is included in the header file, and not compiled separately.
// INVARIANT for the Queue class:
// 1. The number of items in the queue is stored in the member variable
// count.
// 2. The items in the queue are stored in a linked list, with the front of
// the queue stored at the head node, and the rear of the queue stored at
// the final node.
// 3. The member variable front_ptr is the head pointer of the linked list of
// items. For a non-empty queue, the member variable rear_ptr is the
// tail pointer of the linked list; for an empty list, we don't care
// what's stored in rear_ptr.
#include <cassert> // Provides assert
#include "node2.h" // Node template class
namespace main_savitch_8C
{
template <class Item>
queue<Item>::queue( )
{
count = 0;
front_ptr = NULL;
rear_ptr = NULL;
}
template <class Item>
queue<Item>::queue(const queue<Item>& source)
// Library facilities used: node2.h
{
count = source.count;
list_copy(source.front_ptr, front_ptr, rear_ptr);
}
template <class Item>
queue<Item>::~queue( )
{
list_clear(front_ptr);
}
template <class Item>
void queue<Item>::operator =(const queue<Item>& source)
// Library facilities used: node2.h
{
if (this == &source) // Handle self-assignment
return;
list_clear(front_ptr);
list_copy(source.front_ptr, front_ptr, rear_ptr);
count = source.count;
}
template <class Item>
Item queue<Item>::front( ) const
// Library facilities used: cassert
{
assert(!empty( ));
return front_ptr->data( );
}
template <class Item>
void queue<Item>::pop( )
// Library facilities used: cassert, node2.h
{
assert(!empty( ));
list_head_remove(front_ptr);
--count;
}
template <class Item>
void queue<Item>::push(const Item& entry)
// Library facilities used: node2.h
{
if (empty( ))
{ // Insert first entry.
list_head_insert(front_ptr, entry);
rear_ptr = front_ptr;
}
else
{ // Insert an entry that is not the first.
list_insert(rear_ptr, entry);
rear_ptr = rear_ptr->link( );
}
++count;
}
}
|