队列

  1 #include<iostream>
  2 
  3 using namespace std;
  4 
  5 typedef int QueueElement;
  6 
  7 struct Node
  8 
  9 {
 10 
 11  Node *next;
 12 
 13  QueueElement data;
 14 
 15  Node(QueueElement value, Node *link = NULL) :data(value), next(link){}
 16 
 17 };
 18 
 19 class Queue
 20 
 21 {
 22 
 23 public:
 24 
 25      Queue() :myFront(NULL),myBack(NULL) {}
 26 
 27      ~Queue()
 28 
 29     {
 30 
 31       　　 Nodeptr ptr = myFront, nextptr;
 32 
 33        　　while (ptr != 0)
 34 
 35        　　{
 36 
 37            　　  nextptr = ptr->next;
 38 
 39  　　　　　　delete ptr;
 40 
 41 　　　　 　　ptr = nextptr;
 42 
 43  　　　　}
 44 
 45    }
 46 
 47  
 48 
 49  Queue(const Queue& original)
 50 
 51  {
 52 
 53  　　myFront = myBack = 0;
 54 
 55  　　if (!original.empty())
 56 
 57  　　{
 58 
 59  　　　　myFront=myBack= new Node(original.Front());
 60 
 61  　　　　Nodeptr origPtr = original.myFront->next;
 62 
 63  　　　　while (origPtr != 0)
 64 
 65  　　　　{
 66 
 67  　　　　　　myBack->next = new Node(origPtr->data);
 68 
 69 　　　　　　 myBack = myBack->next;
 70 
 71  　　　　　　origPtr = origPtr->next;
 72 
 73  　　　　}
 74 
 75 　　 }
 76 
 77  }
 78 
 79  
 80 
 81  Queue& operator=(const Queue& rhs)
 82 
 83  {
 84 
 85 　　 if (this != &rhs)
 86 
 87  　　{
 88 
 89  　　　　this->~Queue();
 90 
 91  　　　　if (rhs.empty())
 92 
 93  　　　　myFront = myBack = 0;
 94 
 95  　　　　else
 96 
 97  　　　　{
 98 
 99  　　　　　　myFront = myBack = new Node(rhs.Front());
100 
101  　　　　　　Nodeptr rhsPtr = rhs.myFront->next;
102 
103  　　　　　　while (rhsPtr != 0)
104 
105  　　　　　　{
106 
107 　　　　　　　　 myBack->next = new Node(rhsPtr->data);
108 
109  　　　　　　　　myBack = myBack->next;
110 
111 　　　　　　　　 rhsPtr = rhsPtr->next;
112 
113  　　　　　　}
114 
115  　　　　}
116 
117  　　}
118 
119  　　　　return *this;
120 
121  }
122 
123  
124 
125  QueueElement Front() const
126 
127  {
128 
129  　　　　if (!empty())
130 
131  　　　　{
132 
133  　　　　　　return (myFront->data);
134 
135 　　　　 }
136 
137  　　　　else
138 
139  　　　　{
140 
141  　　　　　　cout << "The Stack is empty!" << endl;
142 
143  　　　　}
144 
145  }
146 
147  
148 
149  bool empty() const
150 
151  {
152 
153  　　　　return myFront == 0;
154 
155  }
156 
157  void enqueue(const QueueElement& value)
158 
159  {
160 
161  　　　　Nodeptr newptr= new Node(value);
162 
163  　　　　if (empty())
164 
165  　　　　{
166 
167  　　　　　　myFront = myBack = newptr;
168 
169  　　　　}
170 
171  　　　　else
172 
173  　　　　{
174 
175  　　　　　　myBack->next = newptr;
176 
177  　　　　　　myBack = newptr;
178 
179  　　　　}
180 
181  }
182 
183  
184 
185  void Display()
186 
187  {
188 
189  　　　　　　Nodeptr ptr;
190 
191  　　　　　　for (ptr = myFront; ptr != 0; ptr = ptr->next)
192 
193  　　　　　　cout << ptr->data << " ";
194 
195  　　　　　　cout << endl;
196 
197  }
198 
199  void dequeue()
200 
201  {
202 
203  　　　　if (!empty())
204 
205  　　　　{
206 
207  　　　　　　Nodeptr ptr = myFront;
208 
209  　　　　　　myFront = myFront->next;
210 
211  　　　　　　delete ptr;
212 
213  　　　　　　if (myFront == 0)
214 
215  　　　　　　myBack == 0;
216 
217  　　　　}
218 
219 　　　　 else
220 
221  　　　　{
222 
223  　　　　　　cout << "Stack is empty" << endl;
224 
225  　　　　}
226 
227  }
228 
229  private:
230 
231  typedef Node* Nodeptr;
232 
233  Nodeptr myFront;
234 
235  Nodeptr myBack;
236 
237  };
238 
239  void main()
240 
241  {
242 
243  　　　　Queue s;
244 
245  　　　　cout<<s.empty()<<endl;
246 
247  　　　　for (QueueElement i = 1; i < 6; ++i)
248 
249  　　　　{
250 
251    　　　　　　 s.enqueue(i);
252 
253  　　　　}
254 
255  　　　　cout << s.empty() << endl;
256 
257 　　　　 cout << s.Front() << endl;
258 
259  　　　　s.Display();
260 
261 　　　　 s.dequeue();
262 
263  
264 
265  　　　　s.Display();
266 
267 　　　　 Queue s1;
268 
269  　　　　s1 = s;
270 
271  　　　　s.Display();
272 
273  　　　　Queue s2(s);
274 
275  　　　　s2.Display();
276 
277  　　　　system("pause");
278 
279  }