队列（Queue）（数据结构与算法基础）_queue的结构体怎么定义

目录

队列（queue）

顺序队列

顺序队列的定义

循环队列的几个问题

循环顺序队列的初始化

求循环队列长度

循环队列入队

循环队列出队

循环顺序队列取队头元素

链队列

链队列的定义

链队列的初始化

链队列的销毁

链队列的入队

链队列出队

链队列的取队头元素

---

队列（queue）

特点

• 是一个特殊的线性表，在表一端插入（表尾），在另一端（表头）删除。

• 队列 又称为 先进先出（First In First Out）的线性表，简称FIFO结构。

• 表尾称为 队尾 Top，表头称为 队头 Base。

• 插入元素到 队尾 的操作，称为 入队。

• 从 队头 删除第一个元素的操作，称为 出队。

逻辑结构

• 与线性表相同，仍为一对一关系。

存储结构

• 顺序队 或 链队，以循环顺序队列更常见。

实现方式

• 主要是入队和出队函数，链队和顺序队不同。

顺序队列

队列的顺序存储：同一般线性表的顺序存储结构完全相同。

和栈不太一样的是，队列的头，尾指针都需要移动，以循环顺序队列为常见。

顺序队列的定义

 #define MAXQSIZE 100    //最大队列长度
 typedef struct {
     QElemType *base;//初始化的动态分配存储空间
     int front;      //头“指针”
     int rear;       //尾“指针”
 }SqQueue;

这里的头尾指针存放的不是真正意义上的指针，而是数组下标，是一个整数，目的是为了方便操作。

循环队列的几个问题

溢出：

• 加溢出：当rear = MAXQSIZE但front不为0时，是假溢出。

• 真溢出：当rear = MAXQSIZE且front为0时，还要入队，是真溢出。

解决假溢出的方法是引入 循环队列。

将b[0]接在b[MAXQSIZE-1]之后。

方法：用%运算。

所以当我们入队时，不再是

 Q.base[Q.rear] = x;
 Q.rear++;

而是

 Q.base[Q.rear] = x;
 Q.rear = (Q.rear+1)%MAXQSIZE;

同样，出队时，不再是

 x = Q.base[Q.front];
 Q.front++;

而是

 x = Q.base[Q.front];
 Q.front = (Q.front+1)%MAXQSIZE;

但此时又出现了一个新的问题——队空和队满的条件都为

Q.rear == Q.front;

那么如何分辨是队空还是队满呢？

有三种方案：

1. 另设一个标志以区别队空、队满。

2. 另设一个变量，记录元素个数。（设置一个计数器）

3. 少用一个元素空间。（常用）

用了第三种方案后：

• 队空：Q.front == Q.rear;

• 队满：(Qrear+1)%MAXSIZE == Q.front;

于是解决。

循环顺序队列的初始化

算法描述：

 Status InitQueue(SqQueue &Q) {
     Q.base = new QElemType[MAXQSIZE];//分配空间
     if(!Q.base) exit(OVERFLOW); //存储分配失败
     Q.front = Q.rear = 0;   //头尾指针置为0，队列为空
     return OK;
 }

求循环队列长度

算法描述：

 int QueueLength(SqQueue Q) {
     return (Q.rear - Q.front + MAXQSIZE)%MAXQSIZE;
 }

循环队列入队

算法思路：

1. 判断是否栈满

2. 元素插入队尾

3. 尾指针+1

算法描述：

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

循环队列出队

算法思路：

1. 判断是否栈空

2. 元素出队

3. 头指针+1

算法描述：

 Status DeQueue(SqQueue &Q, QElemType &e) {
     if(Q.front == Q.rear) return ERROR; //队空
     e = Q.base[Q.front];    //保存头元素
     Q.front = (Q.front+1)%MAXQSIZE; //队头指针+1
     return OK;
 }

循环顺序队列取队头元素

算法描述：

 SElemType GetHead(SqQueue Q) {
     if(Q.front != Q.rear)   //队列不为空
         return Q.base[Q.front]; //返回队头指针元素的值，队头指针不变
 }

链队列

链栈不需要头结点，链队列需要头结点。

链队列的定义

• 结点的定义：

 #define MAXQSIZE 100 //最大队列长度
 typedef struct Qnode {
     QElemType data;
     struct Qnode *next;
 } QNode, *QueuePtr;

• 头尾指针的定义：

 typedef struct {
     QueuePtr front;//队头指针
     QueuePtr rear;//队尾指针
 } LinkQueue;

当 LinkQueue Q; 后就可以和之前一样用Q.front，Q.rear进行操作了。

链队列的初始化

算法描述：

 Status InitQueue(LinkQueue &Q) {
     Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
     if(!Q.front) exit(OVERFLOW); //一般不用判断
     Q.front->next = NULL;
     return OK;
 }

链队列的销毁

算法思路：从头开始依次释放。

算法描述：

 Status DestroyQueue(LinkQueue &Q) {
     while(Q.front) {
         p = Q.front->next;
         free(Q.front);
         Q.front = p;
     }//Q.rear = Q.front->next; free(Q.front) ; Q.front = Q.rear;
     return OK;
 }

链队列的入队

算法思路：

1. 生成新节点p

2. e存进p->data

3. 修改队尾指针

算法描述：

 Status EnQueue(LinkQueue &Q, QElemType e) {
     p = (QueuePtr)malloc(sizeof(QNode));
     if(!p) exit(OVERFLOW);
     p->data = e; p->next = NULL;
     Q.rear->next = p;
     Q.rear = p;
     return OK;
 }

链队列出队

算法思路：

1. 保存首元结点地址（可以顺便把data用e返回）

2. 修改队头指针

3. 释放之前的首元结点

算法描述：

 Status DeQueue(LinkQueue &Q, QElemType &e) {
     if(Q.front == Q.rear) return ERROR;
     p = Q.front->next;
     e = p->data;
     Q.front->next = p->next;
     if(Q.rear == p) Q.rear = Q.front;
     delete p;
     return OK;
 }

链队列的取队头元素

算法描述：

 Status GetHead(LinkQueue Q, QElemType &e) {
     if(Q.front == Q.rear) return ERROR;
     e = Q.front->next->data;
     return OK;
 }