队列的顺序表示中，可能会出现队列有空位却产生溢出，这就是"假溢出"现象。解决方法是把队列从逻辑上看成是一个头尾相连的环， 再有新元素需要入队时，就可以将新元素存入下标0的位置。 队头指针进1：front = (front + 1) % maxSize 队尾指针进1：rear = (rear + 1) % maxSize 空队列：front == rear 满队列：front == (rear + 1) % maxSize 满队列时还是有一个元素的空间没有使用的，如果不留这个元素的空间，那么队尾指针rear一定指向该元素空间，使得满队列时的判断 条件也是(front == rear)而无法区分。 包含的函数有IsEmpty(), IsFull(), Frong(), EnQueue(), DEQueue(), Clear()。 实现代码： ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" using namespace std; template <class T> class Queue { public: virtual bool IsEmpty() const = 0; // 队列为空返回true virtual bool IsFull() const = 0; // 队列满返回true virtual bool Front(T &x) const = 0; // 队头元素赋给x，操作成功返回true virtual bool EnQueue(T x) = 0; // 队尾插入元素x，操作成功返回true virtual bool DeQueue() = 0; // 删除队头元素，操作成功返回true virtual bool Clear() = 0; // 清除队列中所有元素 }; template <class T> class SeqQueue:public Queue<T> { public: SeqQueue(int mSize); ~SeqQueue() { delete []q; } bool IsEmpty() const { return front == rear; } // front与rear相等时循环队列为空 bool IsFull() const { return (rear + 1) % maxSize == front; } // front与(rear + 1) % maxSize相等时循环队列满 bool Front(T &x) const; bool EnQueue(T x); bool DeQueue(); bool Clear() { front = rear = 0; return true; } /* data */ private: int front, rear, maxSize; // 队头元素 队尾元素 数组最大长度 T *q; }; template <class T> SeqQueue<T>::SeqQueue(int mSize) { maxSize = mSize; q = new T[maxSize]; front = rear = 0; } template <class T> bool SeqQueue<T>::Front(T &x) const { if(IsEmpty()) { // 空队列处理 cout << "SeqQueue is empty" << endl; return false; } x = q[(front + 1) % maxSize]; return true; } template <class T> bool SeqQueue<T>::EnQueue(T x) { if(IsFull()) { // 溢出处理 cout << "SeqQueue is full" << endl; return false; } q[(rear = (rear + 1) % maxSize)] = x; return true; } template <class T> bool SeqQueue<T>::DeQueue() { if(IsEmpty()) { // 空队列处理 cout << "SeqQueue is empty" << endl; return false; } front = (front + 1) % maxSize; return true; } int main(int argc, char const *argv[]) { SeqQueue<int> sq(5); if(sq.IsEmpty()) cout << "SeqQueue is empty" << endl; for(int i = 0; i < 5; ++i) // sq(0, 1, 2, 3) if(sq.EnQueue(i)) cout << "EnQueue successfully" << endl; int x; if(sq.Front(x)) cout << "The front of sq is " << x << endl; if(sq.IsFull()) cout << "SeqQueue is full" << endl; if(sq.DeQueue()) cout << "Delete front successfully" << endl; if(sq.Front(x)) cout << "The front of sq is " << x << endl; if(sq.Clear()) cout << "Clear successfully" << endl; return 0; } ~~~