数据结构————循环队列讲解

队列的基本概念

队列与栈的不同之处就在于栈是FILO(first in last out)即先进后出，而队列是FIFO(first in first out)即先进先出。队列可应用于银行取号，先取号的要排在后取号的前面来先办理业务，符合先进先出的原则；而栈可应用于QQ消息界面，即最顶层消息栏是最近一次的消息，越往下消息的发布时间越晚，符合先进后出的原则。

对于栈来说，栈一般只有一个栈顶指针top来控制元素的进栈和出栈，因为栈只有一个栈顶一个地方来进出；而队列有队头和队尾两个指针来控制元素的入队和出队，因为队列有两个地方来控制元素进出，即队头出元素，队尾进元素（尾入头出）。

队列如果是类似于栈的存储方式的话，即不是循环就是这个样子的：

那么我们一开始放入元素就是图一的样子，如果我们这是从队头将元素出队，那么慢慢的当元素都出队后就会发生图三看到的样子：“假溢出”。

这时我们就使用循环队列来避免这个问题：

 可以看出这是一个容量为8的循环队列：

图一是循环队列为NULL的时候，我们说此时rear=front

图二是循环队列满的时候，我们说此时front=（rear+1）%MAXSIZE（MAXSIZE=8）

队列的基本操作

1.头文件

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define MAXSIZE 100
typedef int QElemType;
typedef struct{
    QElemType*base;
    int front;
    int rear;
}SqQueue;
void InitQueue(SqQueue &Q);//初始化
void EnQueue(SqQueue &Q,QElemType e);//入队
void DeQueue(SqQueue &Q,QElemType e);//出队
QElemType GetHead(SqQueue Q);//取队头元素
int GetLength(SqQueue Q);//求队列长度

2.源文件

void InitSqQueue(SqQueue &Q){
    Q.base=new QElemType[MAXSIZE];
    if(!Q.base)
        exit(0);
    Q.front=Q.rear=0;
}
void EnSqQueue(SqQueue &Q,QElemType e){
    if((Q.rear+1)%MAXSIZE==Q.front){
        printf("队列已满！\n");
        exit(0);
    }
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXSIZE;
}
void DeSqQueue(SqQueue &Q,QElemType e){
    if(Q.rear==Q.front){
        printf("队列是空的！\n");
        exit(0);
    }
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXSIZE;
}
QElemType GetHead(SqQueue Q){
    if(Q.rear!=Q.front)
        return Q.base[q.front];
}
int SqQueueLength(SqQueue Q){
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}//以防rear-front是负的