数据结构之栈与队列（二）

谁践踏了优雅 2023-06-20 06:18 4阅读 0赞

# 什么是队列 #

队列和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构。与栈不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出。即“先进先出”

> 通常称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。

# 队列的实现 #

队列存储结构的实现有以下两种方式：

*  顺序队列：在顺序表的基础上实现的队列结构；
 *  链队列：在链表的基础上实现的队列结构；

> 两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。

## 顺序队列的简单实现： ##

由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（top 和 rear）分别用于指向顺序队列中的队头元素和队尾元素

由于顺序队列初始状态没有存储任何元素，因此 top 指针和 rear 指针重合，且由于顺序队列底层实现靠的是数组，因此 top 和 rear 实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。

#include <stdio.h>
    int enQueue(int *a,int rear,int data){ 
        a[rear]=data;
        rear++;
        return rear;
    }
    void deQueue(int *a,int front,int rear){ 
        //如果 front==rear，表示队列为空
        while (front!=rear) { 
            printf("出队元素：%d\n",a[front]);
            front++;
        }
    }
    int main() { 
        int a[100];
        int front,rear;
        //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址
        front=rear=0;
        //入队
        rear=enQueue(a, rear, 1);
        rear=enQueue(a, rear, 2);
        rear=enQueue(a, rear, 3);
        rear=enQueue(a, rear, 4);
        //出队
        deQueue(a, front, rear);
        return 0;
    }

这种方法是数列最简单的实现，但是有它的缺陷：

*  顺序队列之前的数组存储空间将无法再被使用，造成了空间浪费；
 *  如果顺序表申请的空间不足够大，则直接造成程序中数组 a 溢出，产生溢出错误；  
    所以建议使用环状队列  
    代码如下：

#include <stdio.h>
    #define max 5//表示顺序表申请的空间大小
    int enQueue(int *a,int front,int rear,int data){ 
        //添加判断语句，如果rear超过max，则直接将其从a[0]重新开始存储，如果rear+1和front重合，则表示数组已满
        if ((rear+1)%max==front) { 
            printf("空间已满");
            return rear;
        }
        a[rear%max]=data;
        rear++;
        return rear;
    }
    int  deQueue(int *a,int front,int rear){ 
        //如果front==rear，表示队列为空
        if(front==rear%max) { 
            printf("队列为空");
            return front;
        }
        printf("%d ",a[front]);
        //front不再直接 +1，而是+1后同max进行比较，如果=max，则直接跳转到 a[0]
        front=(front+1)%max;
        return front;
    }
    int main() { 
        int a[max];
        int front,rear;
        //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址
        front=rear=0;
        //入队
        rear=enQueue(a,front,rear, 1);
        rear=enQueue(a,front,rear, 2);
        rear=enQueue(a,front,rear, 3);
        rear=enQueue(a,front,rear, 4);
        //出队
        front=deQueue(a, front, rear);
        //再入队
        rear=enQueue(a,front,rear, 5);
        //再出队
        front=deQueue(a, front, rear);
        //再入队
        rear=enQueue(a,front,rear, 6);
        //再出队
        front=deQueue(a, front, rear);
        front=deQueue(a, front, rear);
        front=deQueue(a, front, rear);
        front=deQueue(a, front, rear);
        return 0;
    }

使用此方法需要注意的是，顺序队列在判断数组是否已满时，出现下面情况：

*  当队列为空时，队列的头指针等于队列的尾指针；
 *  当数组已满时，队列的头指针等于队列的尾指针；

## 链式队列 ##

使用链表实现的队列存储结构。  
链式队列的实现思想同顺序队列类似，只需创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素

//链表中的节点结构
    typedef struct QNode{ 
        int data;
        struct QNode * next;
    }QNode;
    //创建链式队列的函数
    QNode * initQueue(){ 
        //创建一个头节点
        QNode * queue=(QNode*)malloc(sizeof(QNode));
        //对头节点进行初始化
        queue->next=NULL;
        return queue;
    }

### 数据入队: ###

链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：

*  将该数据元素用节点包裹，例如新节点名称为 elem；
 *  与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
 *  最后移动 rear 指针指向该新节点，即 rear=elem；

QNode* enQueue(QNode * rear,int data){ 
        //1、用节点包裹入队元素
        QNode * enElem=(QNode*)malloc(sizeof(QNode));
        enElem->data=data;
        enElem->next=NULL;
        //2、新节点与rear节点建立逻辑关系
        rear->next=enElem;
        //3、rear指向新节点
        rear=enElem;
        //返回新的rear，为后续新元素入队做准备
        return rear;
    }

### 数据出队: ###

链式队列中队头元素出队，需要做以下 3 步操作：

*  通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
 *  将 p 节点（即要出队的队头节点）从链表中摘除；
 *  释放节点 p，回收其所占的内存空间；

void DeQueue(QNode * top,QNode * rear){ 
        if (top->next==NULL) { 
            printf("队列为空");
            return ;
        }
        // 1、
        QNode * p=top->next;
        printf("%d",p->data);
        top->next=p->next;
        if (rear==p) { 
            rear=top;
        }
        free(p);
    }