C/C++数据结构-完整代码（三）队列【Queue】（顺序存储，链式存储）增删改查

╰半夏微凉° 2022-09-10 11:18 171阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><a href="https://code100.blog.csdn.net/article/details/119809355" rel="nofollow">C/C++数据结构-完整代码（一）数据结构的理论，线性表（动态数组，链表）（完整的算法代码-增删改查-代码解析+运行结果解析）</a></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td><a href="https://code100.blog.csdn.net/article/details/119984925" rel="nofollow">C/C++数据结构-完整代码（二）栈（栈的顺序存储，栈的链式存储，就近匹配,中缀表达式和后缀表达式）</a></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td><a href="https://code100.blog.csdn.net/article/details/120165289" rel="nofollow">C/C++数据结构-完整代码（三）队列【Queue】（顺序存储，链式存储）增删改查</a></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td><a href="https://blog.csdn.net/qq_44757034/article/details/120254584" rel="nofollow">C/C++数据结构-完整代码（四）队列【Queue】（树和二叉树）（二叉树代码实现）</a></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

# 队列 #

## 1、队列的基本概念 ##

队列是一种特殊的线性表，

特殊之处在于它只允许在表的前端（front）进行删除操作，

而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。

进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列中没有元素时，称为空队列。  
队列的数据元素又称为队列元素。

在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。

因为队列只允许在一端插入，在另一端删除，

所以只有最早进入队列的元素才能最先从队列中删除，

故队列又称为先进先出（FIFO—first in first out）线性表。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_17_color_FFFFFF_t_70_g_se_x_16]

## 2、队列的顺序存储 ##

基本概念

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16]  
队列是在之前的动态数组的基础上实现的

先向项目当中导入以下两个文件

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_12_color_FFFFFF_t_70_g_se_x_16]

*  dynamaicArray.c

#include "dynamaicArray.h"
    
    //初始化数组
    struct dynamicAray * init_DynamicArray(int  capacity){
        
        //开辟到堆区
        if(capacity <= 0){
        
            return NULL;
        }
        struct dynamicAray * array = malloc(sizeof(struct dynamicAray ));
        //判断内存是否申请成功
        if(array == NULL){
        
            return NULL;
        }
        //设置容量
        array -> m_capacity = capacity;
        //设置大小
        array -> m_size = 0;
        //维护在堆区数组的指针
        array ->pAddr = malloc(sizeof(void*) * array-> m_capacity);
        return array;
    }
    //插入功能
    void insert_dynamicArray(struct dynamicAray * array,int pos,void *data){
        
        if(array == NULL){
        
            return;
        }
        if(data == NULL){
        
            return;
        }
        if(pos < 0 || pos > array->m_size){
        
            //无效的位置 进行尾插
            pos = array-> m_size;//插入到当前数组的最后一个位置
        }
        //先判断是否已经满载，如果满载的就动态的开辟
        if(array -> m_size >=array -> m_capacity){
        
            //1、申请一个更大的内存空间
            int newCapacity = array->m_capacity * 2;
            //2、创建新的空间
            void ** newSpace =  malloc(sizeof(void *) * newCapacity);
            //3、将原有的数据 拷贝到新空间下
            memcpy(newSpace,array->pAddr,sizeof(void  * ) * array->m_capacity);
            //4、释放原有的空间
            free(array->pAddr);
            //5、更改指针的指向
            array -> pAddr = newSpace;
            //6、更新新容量的大小
            array -> m_capacity = newCapacity;
        }
        //插入新的数据的元素
        //从最后一个位置开始依次往后移动数据  后移
        int i;
        for(i = array -> m_size -1 ;i >= pos;i--){
        
            array->pAddr[i+1] = array->pAddr[i];
        }
        //将新元素插入到指定的位置
        array -> pAddr[pos] = data;
    
        //更新一下大小
        array ->m_size++;
    }
    //遍历数组
    void foreach_DynamicArray(struct dynamicAray * array,void(*myForeach)(void *)){
        
    
        if(array == NULL){
        
            return;
        }
        if(myForeach == NULL){
        
            return;
        }
        int i;
        for(i = 0; i < array ->m_size; i++)
        {
        
            myForeach(array->pAddr[i]);
        }
    
    }
    //删除素质当中的元素
    void removeByPos_DynamicArray(struct dynamicAray * array, int pos){
        
    
        if(array == NULL)
        {
        
            return ;
        }
        if(pos < 0 || pos > array->m_size-1){
        
            //无效的位置 直接return
            return;
        }
        //从pos位置开始 到数组的尾，数据进行前移动
        int i;
        for(i = pos; i < array->m_size -1; i++){
        
            array->pAddr[i] = array->pAddr[i+1];
        }
        array->m_size--;
    
    }
    void myPrintPerson(void * data){
        
        struct Person * p = data;
        printf("姓名：%s,年龄%d\n",p->name,p->age);
    }
    //销毁数据
    void destroy_DynamicArray(struct dynamicAray * arr){
        
        if(arr == NULL)
        {
        
            return;
        }
        if(arr->pAddr != NULL)
        {
        
            free(arr->pAddr);
            arr->pAddr = NULL;
        }
        free(arr);
        arr = NULL;
    }
    
    void test01(){
        
        //创建 动态数组
        struct dynamicAray * arr = init_DynamicArray(5);
        //准备出5个person 数据
        struct Person p1 = {
        "亚瑟",28 };
        struct Person p2 = {
        "王昭君",18 };
        struct Person p3 = {
        "赵云",38 };
        struct Person p4 = {
        "张飞",38 };
        struct Person p5 = {
        "关羽",28 };
        struct Person p6 = {
        "宫本",88 };
        printf("当前的容量为：%d\n",arr->m_capacity);
        //将数据插入到动态数组当中
        insert_dynamicArray(arr,0,&p1);
        insert_dynamicArray(arr,0,&p2);
        insert_dynamicArray(arr,0,&p3);
        insert_dynamicArray(arr,2,&p4);
        insert_dynamicArray(arr,10,&p5);
        insert_dynamicArray(arr,1,&p6);
        printf("插入数据后的容量为：%d\n",arr->m_capacity);
        //赵云 宫本 王昭君 张飞  亚瑟 关羽
        //遍历动态数组
        printf("删除前\n");
        foreach_DynamicArray(arr,myPrintPerson);
        //删除数组当中的元素
        removeByPos_DynamicArray(arr,1);
        printf("删除后\n");
        foreach_DynamicArray(arr,myPrintPerson);
    }

*  dynamaicArray.h

#include "stdio.h"
    #include "string.h"
    #include "stdlib.h"
    //动态数组的结构
    struct dynamicAray{
        
        void ** pAddr;//维护在堆区真实的数组指针
        int m_capacity;//数组的容量
        int m_size;//数组的大小
    };
    //初始化数组
    struct dynamicAray * init_DynamicArray(int  capacity);
    //插入功能
    void insert_dynamicArray(struct dynamicAray * array,int pos,void *data);
    //遍历数组
    void foreach_DynamicArray(struct dynamicAray * array,void(*myForeach)(void *));
    //删除素质当中的元素
    void removeByPos_DynamicArray(struct dynamicAray * array, int pos);
    
    void destroy_DynamicArray(struct dynamicAray * arr);
    
    struct Person{
        
        char name[64];
        int age;
    };
    
    void myPrintPerson(void * data);
    
    void test01();

*  创建seqQueue.h  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_9_color_FFFFFF_t_70_g_se_x_16]

#pragma once
    #include "stdio.h"
    #include "string.h"
    #include "stdlib.h"
    #include "dynamaicArray.h"
    #define MAX 1024
    typedef void * seqQueue;
    
    //初始化队列
    seqQueue init_SeqQueue();
    //入队
    void push_SeqQueue(seqQueue queue, void * data);
    //出队
    void pop_SeqQueue(seqQueue queue);
    //返回队头元素
    void * front_SeqQueue(seqQueue queue);
    //返回队尾元素
    void * back_SeqQueue(seqQueue queue);
    //返回队尾大小
    int size_seqQueue(seqQueue queue);
    //销毁
    void destroy_SeqQueue(seqQueue queue);

*  seqQueue.c

#include "seqQueue.h"
    //初始化队列
    seqQueue init_SeqQueue()
    {
        
        struct dynamicAray * arr = init_DynamicArray (MAX);
        return arr;
    }
    //入队
    void push_SeqQueue(seqQueue queue, void * data){
        
        if(queue == NULL){
        
            return;
        }
        if(data == NULL){
        
            return;
        }
        struct dynamicAray * myQueue = queue;//将当前插入数据转换为原本的数据
        if(myQueue->m_size >= MAX){
        
            return;
        }
        //入队 === 尾插
        insert_dynamicArray (myQueue,myQueue->m_size,data);
    }
    //出队
    void pop_SeqQueue(seqQueue queue){
        
        if(queue == NULL){
        
            return;
        }
        struct dynamicAray * myQueue = queue;
        if(myQueue ->m_size <= 0){
        
            return;
        }
        removeByPos_DynamicArray (myQueue,0);
    }
    //返回队头元素
    void * front_SeqQueue(seqQueue queue){
        
        if(queue == NULL){
        
            return NULL;
        }
        struct dynamicAray * myQueue = queue;
        return myQueue->pAddr[0];
    }
    //返回队尾元素
    void * back_SeqQueue(seqQueue queue){
        
        if(queue == NULL){
        
            return NULL;
        }
        struct dynamicAray * myQueue = queue;
        return myQueue->pAddr[myQueue->m_size-1];
    }
    //返回队尾大小
    int size_seqQueue(seqQueue queue){
        
        if(queue == NULL){
        
            return -1;
        }
        struct dynamicAray * myQueue = queue;
        return myQueue->m_size;
    }
    //销毁
    void destroy_SeqQueue(seqQueue queue){
        
        if(queue == NULL){
        
            return;
        }
        destroy_DynamicArray (queue);
    
    }

*  在main.c当中

#include <stdio.h>
    #include "seqQueue.h"
    
    void test02(){
        
        //初始化队列
        seqQueue  queue = init_SeqQueue();
        
    
        while (size_seqQueue (queue) > 0 ){
        
            //获取对头元素
            struct Person * pFont =  front_SeqQueue (queue);
            //打印队尾元素
            printf ("Front element\tName:%s\t\tAge:%d\n",pFont->name ,pFont->age);
            //获取队尾元素
            struct Person * pBack =  back_SeqQueue(queue);
            //打印队尾元素
            printf ("Back element \tName:%s\t\tAge:%d\n",pBack->name ,pBack->age);
            //出队
            pop_SeqQueue (queue);
        }
        printf ("Queue\t size:%d\n", size_seqQueue (queue));
        //销毁
        destroy_SeqQueue (queue);
    }
    
    int main () {
        
        printf ("Hello, World!\n");
        test02();
        return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 3、队列的链式存储 ##

对外接口  
初始化  
入队  
出队  
返回对头  
返回队尾大小

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 2]

分文件编写  
目录结构  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_9_color_FFFFFF_t_70_g_se_x_16 1]

#### （1）linkQueue.h ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 3]

#pragma once
    #include "stdio.h"
    #include "string.h"
    #include "stdlib.h"
    
    //声明链表的节点
    struct QueueNode{
        
        struct QueueNode * next;//只维护指针域
    };
    //队列的结构体
    struct LQueue{
        
        //头节点
        struct QueueNode pHeader;
        //队列的大小
        int m_Size;
        //维护尾节点的指针
        struct QueueNode * pTail;
    };
    typedef void * LinkQueue;
    //初始化队列
    LinkQueue init_LinkQueue();
    //入队
    void  push_LinkQueue(LinkQueue queue,void * data);
    //出队
    void pop_LinkQueue(LinkQueue queue);
    //返回对头
    void * front_LinkQueue(LinkQueue queue);
    //返回队尾
    void * back_LinkQueue(LinkQueue queue);
    //返回队的大小
    int size_LinkQueue(LinkQueue queue);
    //销毁
    void destory_LinkQueue(LinkQueue queue);

#### （2）linkQueue.c ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 4]

#include "linkQueue.h"
    
    //初始化队列
    LinkQueue init_LinkQueue(){
        
        struct  LQueue * myQueue = malloc (sizeof(struct LQueue));
    
        if(myQueue == NULL){
        
            return NULL;
        }
        myQueue->pHeader.next = NULL;
        myQueue->m_Size = 0;
        myQueue->pTail = &(myQueue->pHeader);//尾结点的初始化，就是在头结点
        return myQueue;
    }
    //入队
    void  push_LinkQueue(LinkQueue queue,void * data){
        
        if(queue == NULL){
        
            return;
        }
        if(data == NULL){
        
            return;
        }
        //还原真实的队列的结构体
        struct LQueue * myQueue = queue;
        //取出用户数据的前四个字节
        struct  QueueNode * myNode = data;
        //插入新I节点-尾插，将队列的为节点的指针指向新节点（也就是尾结点的指针保存新节点的地址）
        myQueue->pTail->next = myNode;
        //将新节点的指针域置空
        myNode->next = NULL;
    
        myQueue->pTail = myNode;//移动尾节点的指针到新节点的位置
    
        //更新队列的长度
        myQueue->m_Size++;
    }
    //出队
    void pop_LinkQueue(LinkQueue queue){
        
        if(queue == NULL){
        
            return;
        }
        struct LQueue * myQueue = queue;
    
        if(myQueue->m_Size <= 0){
        
            return;
        }
        //获取链表当中第一个有数据的节点
        struct QueueNode * pFirst = myQueue->pHeader.next;
        //更新指针的指向
        myQueue->pHeader.next = pFirst->next;
    
        //更新队列的长度
        myQueue->m_Size--;
    
    }
    //返回对头
    void * front_LinkQueue(LinkQueue queue){
        
        if(queue == NULL){
        
            return NULL;
        }
        struct LQueue * myQueue = queue;
    
        return myQueue->pHeader.next;
    }
    //返回队尾
    void * back_LinkQueue(LinkQueue queue){
        
        if(queue == NULL){
        
            return NULL;
        }
        struct LQueue * myQueue = queue;
    
        return myQueue->pTail;
    }
    //返回队的大小
    int size_LinkQueue(LinkQueue queue){
        
        if(queue == NULL){
        
            return -1;
        }
        struct LQueue * myQueue = queue;
    
        return myQueue->m_Size;
    }
    //销毁
    void destory_LinkQueue(LinkQueue queue){
        
    
        if(queue == NULL){
        
            return;
        }
        free (queue);
        queue == NULL;
    
    }

#### （2）main.c ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 5]

#include "stdio.h"
    #include "linkQueue.h"
    
    struct Person{
        
        void * node;
        char name[64];
        int age;
    };
    void test01(){
        
    
        LinkQueue  queue =  init_LinkQueue();
    
        //准备数据
        struct Person p1 = {
        NULL,"aa",10};
        struct Person p2 = {
        NULL,"bb",20};
        struct Person p3 = {
        NULL,"cc",30};
        struct Person p4 = {
        NULL,"dd",40};
        struct Person p5 = {
        NULL,"ee",50};
        //入队
    
        push_LinkQueue (queue,&p1);
        push_LinkQueue (queue,&p2);
        push_LinkQueue (queue,&p3);
        push_LinkQueue (queue,&p4);
        push_LinkQueue (queue,&p5);
        printf ("LinkQueue size : %d \n", size_LinkQueue (queue));
        while (size_LinkQueue (queue) > 0){
        
            struct  Person * pFront = front_LinkQueue (queue);
            printf ("front_LinkQueue  Name = %s\tAge = %d\n",pFront->name,pFront->age);
    
            struct  Person * pBack = back_LinkQueue(queue);
            printf ("back_LinkQueue   Name = %s\tAge = %d\n",pBack->name,pBack->age);
            pop_LinkQueue(queue);
        }
    
        printf ("LinkQueue size : %d \n", size_LinkQueue (queue));
    
        destory_LinkQueue (queue);
    
    }
    
    int main () {
        
        test01();
        printf ("Hello, World!\n");
        return 0;
    }

运行结果  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 6]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/0b666c2b56294cb38312717dbe5dd41b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/c7555deca1df43b08fd8cccdb92d375a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/2726de46ba564201b35a62d78233346c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/ecd7c5fe79af4e2c82a17ba59528f7e3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/c86558b456d649aca43dff23292c4f42.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/77ce44905c854aaf9ae2bbdffbb356d1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_9_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/6cb854faa2a24b65a02934e2026dace4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/e2243d5798754b2c90c4f780e788f95b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/2f6a75cc40784584b4d0eb99d7423048.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220829/1f5c73a437c84138afadc021002f7124.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220829/3beffefe6eb44e9fb1cf29172608bbfc.png