数据结构 队列的操作

队列：一种先进先出的数据结构，一端插入一端删除。

存储方式：分为顺序队列、链式队列

队列顺序存储：

头文件：

#pragma once


#include<stdlib.h>

//顺序队列
struct SQueue{
    void *data[1024]; //保存数据的内存
    int size;
};

typedef void *SeqQueue;

#ifdef __cplusplus
extern "C"{
#endif

    //初始化
    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);

#ifdef __cplusplus
}
#endif

头文件实现：

#include"SeqQueue.h"


//初始化
SeqQueue Init_SeqQueue(){

    struct SQueue *queue = malloc(sizeof(struct SQueue));
    if (NULL == queue){
        return NULL;
    }
    queue->size = 0;
    for (int i = 0; i < 1024; i ++){
        queue->data[i] = NULL;
    }

    return queue;
}
//入队
void Push_SeqQueue(SeqQueue queue, void *data){

    if (NULL == queue){
        return;
    }

    if (NULL == data){
        return;
    }

    struct SQueue *q = (struct SQueue *)queue;

    if (q->size == 1024){
        return;
    }


    //移动元素，把0号位置空出来
    for (int i = q->size - 1; i >= 0; i--){
        q->data[i + 1] = q->data[i];
    }

    q->data[0] = data;
    q->size++;

}
//出队
void Pop_SeqQueue(SeqQueue queue){
    if (NULL == queue){
        return;
    }

    struct SQueue *q = (struct SQueue *)queue;
    if (q->size == 0){
        return;
    }
    q->size--;

}
//获得队头元素
void *Front_SeqQueue(SeqQueue queue){
    if (NULL == queue){
        return NULL;
    }

    struct SQueue *q = (struct SQueue *)queue;
    return q->data[q->size - 1];
}
//获得队尾元素
void *Back_SeqQueue(SeqQueue queue){
    if (NULL == queue){
        return NULL;
    }

    struct SQueue *q = (struct SQueue *)queue;
    return q->data[0];
}
//获得队列大小
int Size_SeqQueue(SeqQueue queue){
    if (NULL == queue){
        return -1;
    }

    struct SQueue *q = (struct SQueue *)queue;
    return q->size;
}
//销毁队列
void Destroy_SeqQueue(SeqQueue queue){
    if (NULL == queue){
        return;
    }
    free(queue);
    queue = NULL;
}

测试文件：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"SeqQueue.h"

struct Person{
    char name[64];
    int age;
};

void test(){

    //创建数据
    struct Person p1 = { "aaa", 10 };
    struct Person p2 = { "bbb", 20 };
    struct Person p3 = { "ccc", 30 };
    struct Person p4 = { "ddd", 40 };
    struct Person p5 = { "eee", 50 };

    //初始化队列
    SeqQueue queue = Init_SeqQueue();
    //数据入队列
    Push_SeqQueue(queue, &p1);
    Push_SeqQueue(queue, &p2);
    Push_SeqQueue(queue, &p3);
    Push_SeqQueue(queue, &p4);
    Push_SeqQueue(queue, &p5);

    //输出队头 队尾元素
    struct Person *front =  (struct Person *)Front_SeqQueue(queue);
    struct Person *back = (struct Person *)Back_SeqQueue(queue);
    printf("队头元素: Name:%s Age:%d
",front->name,front->age);
    printf("队尾元素: Name:%s Age:%d
", back->name, back->age);
    printf("-----------------------------
");

    //输出队列中元素
    while (Size_SeqQueue(queue) > 0){
        //获得对头元素
        front = (struct Person *)Front_SeqQueue(queue);
        printf("Name:%s Age:%d
", front->name, front->age);
        //弹出队头元素
        Pop_SeqQueue(queue);
    }

    //打印大小
    printf("Size:%d
",Size_SeqQueue(queue));

    //销毁队列
    Destroy_SeqQueue(queue);

}

int main(){

    test();

    system("pause");
    return EXIT_SUCCESS;
}

队列的链式存储：

头文件：

#pragma once

#include"LinkList.h"

struct QueueNode{
	struct LinkNode node;
};

#ifdef __cplusplus
extern "C"{
#endif

	//初始化链式队列
	void *Init_LinkQueue();
	//入队列
	void Push_LinkQueue(void *queue, void *data);
	//出队
	void Pop_LinkQueue(void *queue);
	//大小
	int Size_LinkQueue(void *queue);
	//获得队头元素
	void *Front_LinkQueue(void *queue);
	//获得队尾元素
	void *Back_LinkQueue(void *queue);
	//销毁队列
	void Destroy_LinkQueue(void *queue);


#ifdef __cplusplus
}
#endif

　

#pragma once

#include<stdlib.h>

//链表小节点

//目的 ： 第一，让用户数据包含 第二，我需要把用户指针类型转换成struct LinkNode*类型
struct LinkNode{
    struct LinkNode *next;
};

//链表结构体
struct LList{
    struct LinkNode header;
    int size;
};

typedef void *LinkList;

//初始化
LinkList Init_LinkList();

//指定位置插入
void Insert_LinkList(LinkList list, int pos, struct LinkNode *data);
//位置删除
void RemoveByPos_LinkList(LinkList list, int pos);
//遍历
void Foreach_LinkList(LinkList list, void(*foreach)(void *));
//根据位置获得值
void *Get_LinkList(LinkList list,int pos);
int Size_LinkList(LinkList list);


//销毁
void Destroy_LinkList(LinkList list);

　

头文件实现：

#include"LinkQueue.h"

//初始化链式队列
void *Init_LinkQueue(){
    return Init_LinkList();
}
//入队列
void Push_LinkQueue(void *queue, void *data){
    Insert_LinkList(queue, 0, data);
}
//出队
void Pop_LinkQueue(void *queue){
    RemoveByPos_LinkList(queue, Size_LinkList(queue) - 1);
}
//大小
int Size_LinkQueue(void *queue){
    return Size_LinkList(queue);
}
//获得队头元素
void *Front_LinkQueue(void *queue){
    return Get_LinkList(queue , Size_LinkList(queue) - 1);
}
//获得队尾元素
void *Back_LinkQueue(void *queue){
    return Get_LinkList(queue, 0);
}
//销毁队列
void Destroy_LinkQueue(void *queue){
    Destroy_LinkList(queue);
}

#include"LinkList.h"


//初始化
LinkList Init_LinkList(){

    struct LList *list = malloc(sizeof(struct LList));
    if (NULL == list){
        return NULL;
    }
    list->header.next = NULL;
    list->size = 0;

    return list;
}
//指定位置插入
void Insert_LinkList(LinkList list, int pos, struct LinkNode *data){
    
    if (NULL == list){
        return;
    }

    if (NULL == data){
        return;
    }
    
    struct LList *llist = (struct LList *)list;

    if (pos < 0 || pos >llist->size){
        pos = llist->size;
    }

    //查找pos位置前一个位置的节点
    struct LinkNode *pCurrent = &(llist->header);
    for (int i = 0; i < pos;i ++){
        pCurrent = pCurrent->next;
    }

    //将新节点插入到链表
    data->next = pCurrent->next;
    pCurrent->next = data;

    llist->size++;
}

//位置删除
void RemoveByPos_LinkList(LinkList list, int pos){

    if (NULL ==list){
        return;
    }

    struct LList *llist = (struct LList *)list;


    if (llist->size == 0){
        return;
    }

    if (pos < 0 || pos > llist->size - 1){
        return;
    }


    //找到pos位置的前一个节点
    struct LinkNode *pCurrent = &(llist->header);
    for (int i = 0; i < pos; i ++){
        pCurrent = pCurrent->next;
    }

    //缓存下待删除节点
    struct LinkNode *pDel = pCurrent->next;
    //重新建立待删除的节点前驱后继节点关系
    pCurrent->next = pDel->next;

    llist->size--;
}


//根据位置获得值
void *Get_LinkList(LinkList list, int pos){
    if (NULL == list){
        return NULL;
    }

    struct LList *llist = (struct LList *)list;
    if (pos < 0 || pos > llist->size - 1){
        return NULL;
    }

    //辅助指针变量
    struct LinkNode *pCurrent = &(llist->header);
    for (int i = 0; i < pos; i++){
        pCurrent = pCurrent->next;
    }


    return pCurrent->next;
}

int Size_LinkList(LinkList list){
    if (NULL == list){
        return -1;
    }

    struct LList *llist = (struct LList *)list;
    return llist->size;
}


//遍历
void Foreach_LinkList(LinkList list, void(*foreach)(void *)){
    if (NULL == list){
        return;
    }

    struct LList *llist = (struct LList *)list;
    //辅助指针变量
    struct LinkNode *pCurrent = llist->header.next;
    while (pCurrent != NULL){
        foreach(pCurrent);
        pCurrent = pCurrent->next;
    }
}

//销毁
void Destroy_LinkList(LinkList list){
    if (NULL == list){
        return;
    }

    free(list);
    list = NULL;
}

测试代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"LinkQueue.h"

struct Person{
    struct QueueNode node;
    char name[64];
    int age;
};

void test(){

    //创建测试数据
    struct Person p1 = { NULL ,"aaa", 10 };
    struct Person p2 = { NULL ,"bbb", 20 };
    struct Person p3 = { NULL ,"ccc", 30 };
    struct Person p4 = { NULL ,"ddd", 40 };
    struct Person p5 = { NULL ,"eee", 50 };
    
    void *queue = Init_LinkQueue();

    //数据入队
    Push_LinkQueue(queue, &p1);
    Push_LinkQueue(queue, &p2);
    Push_LinkQueue(queue, &p3);
    Push_LinkQueue(queue, &p4);
    Push_LinkQueue(queue, &p5);

    struct Person *front = (struct Person *)Front_LinkQueue(queue);
    struct Person *back = (struct Person *)Back_LinkQueue(queue);
    printf("Front: Name:%s Age:%d
",front->name,front->age);
    printf("Back: Name:%s Age:%d
", back->name, back->age);
    printf("-------------------------------
");
    //输出队列中的元素
    while (Size_LinkQueue(queue) > 0){
        
        front = (struct Person *)Front_LinkQueue(queue);
        printf("Name:%s Age:%d
", front->name, front->age);
        //弹出队头元素
        Pop_LinkQueue(queue);
    }

    //销毁队列
    Destroy_LinkQueue(queue);

}

int main(){

    test();

    system("pause");
    return EXIT_SUCCESS;
}