循环队列ADT_SeqQueue
最后更新于：2022-04-01 20:51:17
队列的顺序表示中，可能会出现队列有空位却产生溢出，这就是"假溢出"现象。解决方法是把队列从逻辑上看成是一个头尾相连的环，
再有新元素需要入队时，就可以将新元素存入下标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 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 SeqQueue:public Queue
{
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
SeqQueue::SeqQueue(int mSize)
{
maxSize = mSize;
q = new T[maxSize];
front = rear = 0;
}
template
bool SeqQueue::Front(T &x) const
{
if(IsEmpty()) { // 空队列处理
cout << "SeqQueue is empty" << endl;
return false;
}
x = q[(front + 1) % maxSize];
return true;
}
template
bool SeqQueue::EnQueue(T x)
{
if(IsFull()) { // 溢出处理
cout << "SeqQueue is full" << endl;
return false;
}
q[(rear = (rear + 1) % maxSize)] = x;
return true;
}
template
bool SeqQueue::DeQueue()
{
if(IsEmpty()) { // 空队列处理
cout << "SeqQueue is empty" << endl;
return false;
}
front = (front + 1) % maxSize;
return true;
}
int main(int argc, char const *argv[])
{
SeqQueue 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;
}
~~~
';