类模板Queue的实现

时间:2021-07-31 17:40:05
类模板Queue的实现类模板Queue的实现
  1 #include <iostream>
  2 #include <vector>
  3 using namespace std;
  4 
  5 template <class Type> class Queue;
  6 template <class T > ostream & operator << (ostream &os, const Queue<T> &);
  7 
  8 template <class Type> class QueueItem {
  9     friend class Queue<Type >;
 10     friend ostream & operator << <Type> (ostream &os, const Queue<Type> &);
 11     //private class
 12     QueueItem(const Type &val) : Item(val), next(0) {}
 13     Type Item;
 14     QueueItem<Type > *next;
 15 };
 16 
 17 template <class Type> class Queue {
 18     friend ostream & operator << <Type> (ostream &os, const Queue<Type> &);
 19 
 20 public:
 21     Queue() : head(0), tail(0) {}
 22     template <class It> Queue(It _beg, It _end) : head(0), tail(0) { copy_elems(_beg, _end); }
 23     Queue(const Queue<Type> &Q) : head(0), tail(0) { copy_elems(Q); }
 24     Queue& operator = (const Queue &Q);
 25     ~Queue() { Destroy(); }
 26     template <class Iter> void _assign(Iter, Iter);
 27     Type &_front() { return head->Item; }
 28     const Type &_front() const { return head->Item; }
 29     void _push(const Type&);
 30     void _pop();
 31     bool _empty() const { return head == 0; }
 32 
 33 private:
 34     QueueItem<Type> *head;
 35     QueueItem<Type> *tail;
 36     void Destroy();
 37     void copy_elems(const Queue<Type> &);
 38     template <class Iter> void copy_elems(Iter, Iter);
 39 };
 40 
 41 template <class Type> Queue<Type>& Queue<Type>::operator = (const Queue<Type> &q)
 42 {
 43     if (this != &q) {
 44         head = tail = 0;
 45         for (QueueItem<Type> *pt = q.head; pt; pt= pt->next) {
 46             _push(pt->Item);
 47         }
 48     }
 49     return *this;
 50 }
 51 
 52 template <class Type> void Queue<Type>::copy_elems(const Queue<Type> &q)
 53 {
 54     for (QueueItem<Type> *pt = q.head; pt; pt = pt->next) {
 55         _push(pt->Item);
 56     }
 57 }
 58 template <class Type> template <class Iter> void Queue<Type>::copy_elems(Iter _beg, Iter _end)
 59 {
 60     while (_beg != _end) {
 61         _push(*_beg);
 62         ++_beg;
 63     }
 64 }
 65 
 66 template <class Type> template <class Iter> void Queue<Type>::_assign(Iter _beg, Iter _end)
 67 {
 68     head = tail = 0;
 69     copy_elems(_beg, _end);
 70 }
 71 
 72 template <class Type> void Queue<Type>::_push(const Type& val)
 73 {
 74     QueueItem<Type> *p = new QueueItem<Type>(val);
 75     if (_empty()) {
 76         head = tail = p;
 77     } else {
 78         tail->next = p;
 79         tail = p;
 80     }
 81 }
 82 
 83 template <class Type> void Queue<Type>::_pop()
 84 {
 85     QueueItem<Type> *p = head;
 86     head = head->next;
 87     delete p;
 88 }
 89 
 90 template <class Type> ostream & operator << (ostream &os, const Queue<Type> &q)
 91 {
 92     for (QueueItem<Type> *pt = q.head; pt; pt = pt->next) {
 93         os << pt->Item << " ";
 94     }
 95     os << endl;
 96     return os;
 97 }
 98 
 99 template <class Type> void Queue<Type>::Destroy()
100 {
101     while (!_empty()) _pop();
102 }
103 
104 
105 int main()
106 {
107     Queue<int >que;
108     que._push(1);
109     que._push(2);
110     que._push(3);
111     que._push(4);
112     cout << que;
113     que._pop();
114     cout << que;
115     Queue<int >q2, q1(que);
116     cout << q1;
117     cout << q2._empty() << endl;
118     q2 = q1;
119     cout << q2;
120     while (!que._empty()) {
121         cout << que._front() << endl;
122         que._pop();
123     }
124     vector<int > vet(10, 7);
125     for (int i = 0; i < (int)vet.size(); i++) {
126         cout << vet[i] << ' ';
127     }
128     cout << endl;
129     que._assign(vet.begin(), vet.end());
130     cout << que;
131     return 0;
132 }
View Code

类模板Queue的实现