|
对于队列（Queue）是什么，再次不再赘述，与链表、栈的实现一样，队列作为一种特殊的线性表，也存在顺序存储以及链式存储两种方式。
顺序存储的队列
采用顺序存储的方式来存储队列，最简单的方式是对于n个元素的队列，开辟一个n大小的数组，入队操作即是在数组的尾部直接添加元素，出队操作即将0方向的元素移除，并将所有的后边元素全部前移一个，这与顺序表操作是一致的，但是自然会很麻烦，因此，又出现了另一种方式，在“移除”队首的元素之后，不进行前移操作，这样出队操作是简化了，但是又引发了另一个问题，也就是如果不断的进行出队操作，那么队列首与队列尾都指向了队列中较为靠后的一部分，那么队列前边的空间就浪费了，如果首尾指针重合了，虽然实际上空间是有的，但是也无法操作了，这被称作假溢出，而解决的方式就是采用循环队列的形式。
循环队列的基本操作：
#include
#include
#include
using namespace std;
#define OK 1
#define ERROR -1
#define Status
#define MAXSIZE 100
typedef int QElemType;
typedef struct{
QElemType data[MAXSIZE];
int front;
int rear;
}SqQueue;
Status InitQueue(SqQueue &Q){
Q.front = 0;
Q.rear = 0;
return OK;
}
Status Length(SqQueue Q){
return (Q.rear+MAXSIZE-Q.front)%MAXSIZE; //注意不要忘了加MAXSIZE，因为循环队列有的时候rear会在front的前面（重用了前面的空闲空间）
}
Status EnQueue(SqQueue &Q, int n){
if((Q.rear+1)==Q.front)
return ERROR;
Q.data[Q.rear] = n;
Q.rear = (Q.rear+1)%MAXSIZE; //无论是入队，还是出队操作，都要对MAXSIZE取模，以便于重用空闲的空间，
return OK; //其实循环队列的最重要的方法就是通过对MAXSIZE的取模实现了“循环”
}
Status DeQueue(SqQueue &Q, int &e){
if(Q.front == Q.rear)
return ERROR;
e = Q.data[Q.front];
Q.front = (Q.front+1)%MAXSIZE;
return OK;
}
int main(){
SqQueue Q;
InitQueue(Q);
int n;
cout |