devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：菜鸟追梦旅行 | 2024-06-12 06:47:00

赞

踩

队列数据结构代码
C/C++数据结构-完整代码（一）数据结构的理论，线性表（动态数组，链表）（完整的算法代码-增删改查-代码解析+运行结果解析）
C/C++数据结构-完整代码（二）栈（栈的顺序存储，栈的链式存储，就近匹配,中缀表达式和后缀表达式）
C/C++数据结构-完整代码（三）队列【Queue】（顺序存储，链式存储）增删改查
C/C++数据结构-完整代码（四）队列【Queue】（树和二叉树）（二叉树代码实现）

队列

1、队列的基本概念

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

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

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

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

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

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

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

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

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

在这里插入图片描述

2、队列的顺序存储

基本概念

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

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

在这里插入图片描述

  • 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);
}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 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();




  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 创建seqQueue.h
    在这里插入图片描述
#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);

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 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);

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 在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;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

运行结果

在这里插入图片描述

3、队列的链式存储

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

在这里插入图片描述

分文件编写
目录结构
在这里插入图片描述

（1）linkQueue.h

在这里插入图片描述

#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);


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
（2）linkQueue.c

在这里插入图片描述

#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;

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
（2）main.c

在这里插入图片描述

#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;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

运行结果
在这里插入图片描述

C/C++数据结构-完整代码（一）数据结构的理论，线性表（动态数组，链表）（完整的算法代码-增删改查-代码解析+运行结果解析）
C/C++数据结构-完整代码（二）栈（栈的顺序存储，栈的链式存储，就近匹配,中缀表达式和后缀表达式）
C/C++数据结构-完整代码（三）队列【Queue】（顺序存储，链式存储）增删改查
C/C++数据结构-完整代码（四）队列【Queue】（树和二叉树）（二叉树代码实现）
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/706847
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号