做网站用是内网穿透好/一个完整的产品运营方案

数据结构笔记3.3
顺序队列是用顺序表实现的（即依托于数组），这里实现的是循环队列，其实也可以不用循环，但是那样的话，空间的利用效率就太低了，这就是”假溢出”问题，因为在数组的前端可能还有空闲的位置（因为队列中的数据是在动态变化的，可能出队也可能入对）。
为了能够充分利空间，所以用循环队列，即在逻辑上把数组的队结构看成一个环。具体实现：实现的方式还是十分巧妙地，运用两个指针和钟运算(就是取模或是取余运算)。
队头指针进1：front = (front + 1) % maxSize;
队尾指针进1 : rear = (rear + 1) % maxSize;
上面两个式子就是钟运算在队列数据操作时候的实现原理。
另外，在判断队列NULL与队列FULL的时候会遇到混淆的问题，NULL的时候，在即rear == front ，但是由于是循环表，当表FULL的时候，两者也是相等的，一种区分方式就是当rear检测到其下一个就是front的时候作为队列满的依据，这样就相当于队列满的时候也会有一个节点是空闲的。
好了，在编写这个类的过程中，需要强调的就这几个地方，下面贴出代码：
虚基类代码（此代码段放入queue.h当中，并在模板类代码中包含）

template<class T>
class Queue {
public:Queue(){}                               //构造函数~Queue(){}                             //析构函数virtual bool EnQueue(const T & x) = 0;  //新元素x进入队列virtual bool DelQueue(T & x) = 0;       //队头元素出队列virtual bool getFront(T & x) = 0;       //读取队头元素的值virtual bool IsEmpty()const = 0;        //判断队列是否为NULLvirtual bool IsFull() const = 0;        //判断队列是否已满virtual int getSize() const = 0;            //求队列元素的个数
};

模板class代码：

#include <iostream>
#include <cassert>
#include <cmath>
#include "queue.h"
using namespace std;
//顺序队列模板类定义(循环队列)
template<class T>
class SeqQueue : public Queue<T> {
public:SeqQueue(int sz = 10);              //构造函数~SeqQueue();                       //析构函数//若队列不满则将x进入队列，否则溢出处理bool EnQueue(const T & x);//若队列不空则删除队头元素x，并返回true，否则返回falsebool DelQueue(T & x);//若队列不空则函数返回队头元素并返回true，否则返回falsebool getFront(T & x);//置空操作，队头指针与队尾指针置0void makeEmpty();//判断队列是否为空，是则返回true否则返回falsebool IsEmpty() const;//判断队列是否已满，是返回true否则返回falsebool IsFull() const;//求队列元素的个数int getSize() const;//输出队列元素,运算符重载函数调用void output(ostream & out);
protected:int rear, front;                    //队尾与队头指针T *elements;                        //存放队列元素的数组int maxSize;                        //队列最大可容纳的元素个数
};
//函数定义
template<class T>
SeqQueue<T>::SeqQueue(int sz) {//建立一个最大就有maxSzie个元素的空队列maxSize = sz;elements = new T[sz];               //开辟内存assert(elements != NULL);           //内存分配不成功的中断处理rear = front = 0;                   //初始化队头与队尾指
}template<class T>
SeqQueue<T>::~SeqQueue() {//析构函数，释放程序中相应的资源delete[] elements;
}template<class T>
bool SeqQueue<T>::EnQueue(const T & x) {//若队列不满则将x进入队列，否则溢出处理if (IsFull()) {//如果队列已经满，则返回falsereturn false;}elements[rear] = x;rear = (rear + 1) % maxSize;    //通过钟运算实现元素的循环填充return true;
}template<class T>
bool SeqQueue<T>::DelQueue(T & x) {//若队列不空则删除队头元素x，并返回true，否则返回falseif (IsEmpty()) {return false;}x = elements[front];front = (front + 1) % maxSize;return true;
}template<class T>
bool SeqQueue<T>::getFront(T & x)  {//若队列不空则函数返回队头元素并返回true，否则返回falseif (IsEmpty()) {return false;}x = elements[front];return true;
}template<class T>
bool SeqQueue<T>::IsEmpty() const {if (rear == front) {return true;}else {return false;}
}template<class T>
bool SeqQueue<T>::IsFull() const {if (fmod((rear + 1), maxSize) == front) {//如果rear的下一个节点与front相同则定义为队列已满//从而区分队列为NULL，即rear==front的情况return true;//注意这个时候队列中会有一个NULL的节点}else {return false;}
}template<class T>
void SeqQueue<T>::makeEmpty() {//置NULL操作rear = front = 0;
}template<class T>
int SeqQueue<T>::getSize() const {//求队列元素的个数return (rear - front + maxSize) % maxSize;
}template<class T>
void SeqQueue<T>::output(ostream & out) {for (int i = front; i != rear; i = (i + 1) % maxSize) {out << elements[i] << ' ';}cout << endl;
}template<class T>
ostream & operator << (ostream & out, SeqQueue<T> & SQ) {//重载插入运算符SQ.output(out);return out;
}

Main测试代码：

int main()
{SeqQueue<int> squeue;               //定义循环队列对象squeue.EnQueue(1);                  //进队与出队测试squeue.EnQueue(2);squeue.EnQueue(3);squeue.EnQueue(4);squeue.EnQueue(5);cout << squeue;int outQueVal_1, outQueVal_2;squeue.DelQueue(outQueVal_1);squeue.DelQueue(outQueVal_2);cout << squeue;int quFrontVal = 0;squeue.getFront(quFrontVal);        //提取队头数据测试cout << quFrontVal << endl;squeue.makeEmpty();                 //设置NULL与测试NULL测试if (squeue.IsEmpty()) {cout << "队列为NULL" << endl;}else {cout << "队列非空" << endl;}squeue.EnQueue(2);                  //取队列大小测试squeue.EnQueue(3);squeue.EnQueue(4);cout << squeue.getSize() << endl;system("pause");return 0;
}

运行结果：