[C++知识库]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);
}

• 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
  

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

运行结果

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

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

}

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

运行结果