队列的基本操作(C/C++)

提示：以下是本篇文章正文内容

一、队列定义

队列：只允许在一端进行插入操作，而在另一端进行删除操作的线性表---->先进先出FIFO

允许插入（也称入队，进队）的一端称为队尾 允许删除（出队）的一端称为队头

二、顺序队列

顺序队列：利用数组实现队列的顺序存储

为了避免当只有一个元素时，队头和队尾重合引起麻烦，使用两个指针front（指向队头元素),rear（指向队尾元素）

假溢出：当元素被插入到数组的中下标的最大的位置上之后，队列的空间空间就用完了，尽管此时数组的低端还有空闲空间，这种现象称为假溢出。

三、循环队列

front（指向队头元素），rear（指向队尾元素），但是会导致队尾没位置但是队首有位置的情况（假溢出）：使用队列首尾相接的顺序存储结构,记为循环队列

如何判断队列是否为空，使用front ==rear，但是队列满时也满足该条件？ 当队列满，保留一个元素空间 1.队列满的条件:（rear+1）%QueueSize == front（rear可能在front右边，也可能在front左侧）

2.队列长度：(rear-front+QueueSize)%QueueSize 注：QueueSize为队列最大长度

1.循环队列的顺序存储结构

typedef int QElemType; 
typedef struct
{
    QElemType data[MAXSIZE];
    int front; /*头指针*/
    int rear; /*尾指针，若队列不空，指向队列元素的下一个位置*/
}SqQueue;

2.初始化空队列

/*初始化一个空队列*/
Status InitQueue(SqQueue *Q)
{
    Q->front= 0;
    Q->rear=0;
    return OK;
}

3.队列长度

/*返回Q的元素个数，也就是队列的当前长度*/
int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front+MAXSIZE)%MAXSIZE;
}

4.入队

Status EnQueue(SqQueue *Q,QElemType e) {
    if ((Q->rear + 1) % MAXSIZE == Q->front) /*队列满的判断*/
        return ERROR;
    Q->data[Q->rear] = e;  //将元素e赋值给队尾
    Q->rear = (Q->rear + 1) % MAXSIZE; //rear指针向后移一个位置，在末尾则转到数组头部
}

注：rear指针向后移一个位置：Q->rear = (Q->rear + 1) % MAXSIZE;

5.出队

Status DeQueue(SqQueue *Q,QElemType *e)
{
    if (Q->front == Q->rear)
        return ERROR;
    *e= Q->data[Q->front]; //将队头元素赋值给e
    Q->front=(Q->front+1)%MAXSIZE; //front指针向后移一位置，若到最后转到数组头部
}

注：front指针向后移一位置：Q->front=(Q->front+1)%MAXSIZE;

四、链式队列

队列的链式存储结构，本质上是线性表的单链表，只不过是它只能尾进头出，简称为链队列

队头指针指向链队列的头结点，队尾指针指向终端结点

空队列的时候，front指针和rear指针都指向头结点 队列的链式存储结构

typedef int QElemType;
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct  //队列的链表结构
{
    QueuePtr front,rear; //对头、队尾指针
}LinkQueue;

入队：

Status EnQueue(LinkQueue *Q,QElemType e)
{
    QueuePtr  s = (QueuePtr) malloc(sizeof(QNode));
    if (!s)  //存储分配失败
        exit(OVERFLOW);
    s->data=e;
    s->next=NULL;
    Q->rear->next=s; //把拥有yuansue新结点s赋值为原队尾结点的后继
    Q->rear=s; //把当前的s设置为队尾结点，rear指向s
    return OK;
}

出队：

Status DeQueue(LinkQueue *Q,QElemType *e)
{
    QueuePtr p;
    if (Q->front == Q->rear)
        return ERROR;
    p= Q->front->next; //将要删除的队头结点暂存给p
    *e = p->data; // 将要删除的队头结点的值赋值给*e
    Q->front->next = p->next; //将原队头结点后继赋值给头结点后继
    if (Q->rear == p)
        Q->rear = Q->front; //若队头是队尾，则删除后将rear指向头结点（只有头结点和一个元素）
    free(p);
    return OK;
}