队列

【1】队列的概念

（1）队列（Queue）是运算受到限制的一种线性表。

　　只允许在表的一端进行插入，而在另一端进行删除元素的线性表。

　　队尾（rear）是允许插入的一端。队头（front）是允许删除的一端。

（2）空队列是不含元素的空表。

（3）队列是先进先出的线性表。

【2】循环队列

关于循环队列请看下图分析：

以上分析过程摘录于《大话数据结构》，强烈推荐。

【3】循环队列的实现

  1 // Queue.h
  2 // 循环队列的实现
  3 #pragma  once
  4 
  5 #include <iostream>
  6 using namespace std;
  7 
  8 #define  QUEUESIZE   100
  9 
 10 template <class Type>
 11 class  SeqQueue
 12 {
 13 private:
 14     Type  data[QUEUESIZE];
 15     int   front, tail;
 16     int   size;
 17 
 18 public:
 19     SeqQueue();
 20     ~SeqQueue();
 21     bool EnQueue(const Type& item);
 22     bool DeQueue(Type& item);
 23     bool GetTop(Type& item);
 24     bool IsEmpty() const;
 25     bool IsFull() const;
 26     void MakeEmpty();
 27 
 28 public:
 29     template <class Type>
 30     friend  ostream & operator<<(ostream & out, const SeqQueue<Type> &sq);
 31     template <class Type>
 32     friend  istream & operator>>(istream & in, SeqQueue<Type> &sq);
 33 };
 34 
 35 template <class Type>
 36 SeqQueue<Type>::SeqQueue(): front(0), tail(0), size(0)
 37 {}
 38 
 39 template <class Type>
 40 SeqQueue<Type>::~SeqQueue()
 41 {}
 42 
 43 template <class Type>
 44 bool SeqQueue<Type>::EnQueue(const Type &item)
 45 {
 46     if (size < QUEUESIZE)
 47     {
 48         data[tail] = item;
 49         tail = (tail + 1) % QUEUESIZE;
 50         ++size;
 51         return  true;
 52     }
 53     return  false;
 54 }
 55 
 56 template <class Type>
 57 bool SeqQueue<Type>::DeQueue(Type& item)
 58 {
 59     if (size > 0)
 60     {
 61         item = data[front];
 62         front = (front + 1) % QUEUESIZE;
 63         --size;
 64         return true;
 65     }
 66     return  false;
 67 }
 68 
 69 template <class Type>
 70 bool SeqQueue<Type>::GetTop(Type& item)
 71 {
 72     if (size > 0)
 73     {
 74         item = data[front];
 75         return true;
 76     }
 77     return false;
 78 }
 79 
 80 template <class Type>
 81 bool SeqQueue<Type>::IsEmpty() const
 82 {
 83     return  0 == size;
 84 }
 85 
 86 template <class Type>
 87 bool SeqQueue<Type>::IsFull() const
 88 {
 89     return  QUEUESIZE == size;
 90 }
 91 
 92 template <class Type>
 93 void  SeqQueue<Type>::MakeEmpty()
 94 {
 95     front = tail = size = 0;
 96 }
 97 template <class Type>
 98 ostream & operator<<(ostream &out, const SeqQueue<Type> &sq)
 99 {
100     cout << "队列的数据元素(按照进入顺序)如下：" << endl;
101     for (int i = sq.tail-1; i >= 0; i--)
102     {
103         out << sq.data[i] << "  ";
104     }
105     out << endl;
106     out << "front: " << sq.front << endl;
107     out << "tail : " << sq.tail << endl;
108     out << "size : " << sq.size << endl;
109     return out;
110 }
111 
112 template <class Type>
113 istream & operator>>(istream & in, SeqQueue<Type> &sq)
114 {
115     Type temp = Type();
116     while (temp != -1)
117     {
118         in >> temp;
119         if (temp != -1)
120             sq.EnQueue(temp);
121     }
122     return in;
123 }

View Code

以上循环队列实现代码在随后相关代码中会被引用。

Good Good Study, Day Day Up.

顺序选择循环总结