队列以及循环队列及其基本操作

和栈相反，队列是一种先进先出的数据结构，他在表尾插入元素，表头删除元素。队列也分为链队列以及顺序队列两种，链队列动态分配空间，不用担心空间不足，顺序队列简单易懂，操作方便,但是空间利用率低，所以我们一般使用链式队列结构。

• 链式队列

对顺序队列进行初始化，顺序队列分配空间类似于数组

typedef char QElemType
typedef int Status;

typedef struct QNode{  //创建链队列
    QElemType data;    //存储队列数据
    QNode *next;       //存储下一个结点指针
}QNode,QPtr*;

typedef struct{
    QNode *front;      //首结点指针
    QNode *rear;       //尾结点指针
}LinkQueue;

Status InitQueue(LinkQueue &q){
    s.front=(SElemType *)malloc(INIT_STACK_SIZE*sizeof(SElemType)); //为尾结点分配空间
    if(!s.front)exit(OVERFLOW);
    s.front=s.rear;
    return OK;
}

获取队列头部数据

Status GetTop(SqStack q,ElemType &e){
    if(s.front==s.rear)return ERROR;
    e=s.front->next.data
    return OK;
}

在队尾插入元素

Status Enqueue(LinkQueue &q,QElemType e){
    QPtr q=(QPtr)malloc(sizeof(QNode));
    if(!q)exit(OVERFLOW);
    q->data=e;
    q->next=NULL;
    Q.rear->next=q;
    Q.rear=q;
}
    

在队首删除元素

Status Dequeue(LinkQueue &q,QElemType &e){
    if(q.front==q.rear)return ERROR;
    QNode *temp;
    temp=q.front->next;    
    e=temp->data;
    q.front->next=temp->next;
    if(q.rear==temp)    //如果队首元素下一个元素是尾结点，则删除后队列为空队列
        q.rear=q.front;
    free(temp);
    return OK;
}

计算队列元素个数

Status QueLength(LinkQueue &q){
    QNode p=q.front->next;    //建立p指针从首元素结点向后遍历并且计数
    int len=0;
    while(p!=NULL){            //p指针不指向空时向后遍历
        len++;
        p=p->next;
    }
    return len;
}

• ---

  循环队列

循环队列与普通队列的区别在于循环队列首尾相接，其首尾相接的特性可以使得他大大减少了空间的浪费，队列存储到末端时，由于其首尾相接的特性，可以在队首前面未存储数据的空间存储。

循环队列用类似线性表存储，需要预先分配循环队列存储空间，值得注意的点时循环队列由于队列可能存储在超出队列长度的位置，所以在Q.rear+1时需要对maxsize取模，得到实际的存储位置

//–––––循环队列──队列的顺序存储结构–––––
#define MAXQSIZE   100                 //最大队列长度
typedef  struct
{
QElemType *    base;        //初始化的动态分配存储空间
    int front;                //头指针,若队列不空,指向队列头元素
    int rear;   //尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;
Status InitQueue(SqQueue &Q)
{//  构造一个空队列Q
    Q.base =(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
    if (!Q.base)  exit(OVERFLOW);  //存储分配失败
    Q.front =0;
    Q.rear =Q.front;
    return OK;
}

 返回队列长度

int QueueLength(SqQueue Q)
{//返回Q的元素个数,即队列的长度
  return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

• 插入数据

在队尾即Q.rear的位置存入新的数据e，Q. rear后移。

Status EnQueue(SqQueue &Q,QElemType e)
{// 插入元素e为Q的新的队尾元素
   if((Q.rear+1)%MAXQSIZE==Q.front)   //队列满
        return ERROR;                                      
   Q.base[Q.rear]=e;
   Q.rear=(Q.rear+1)%MAXQSIZE;
   return OK;
}

• 删除数据

Status DeQueue(SqQueue &Q, QElemType &e)
{// 删除队头元素，送给变量e
    if(Q.rear==Q.front) return ERROR;   //队列空
    e= Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE; //队头指针后移，队首元素出队
    return OK;
}

• 检验是否队列为空 

Status QueueEmpty(SqQueue Q)
{ 
    if( Q.rear==Q.front) return TRUE;
    return FALSE;
}