数据结构队列的操作-白红宇

数据结构队列的操作

阅读量：6500 次

发布时间：2019-06-24

本文共 8497 字，大约阅读时间需要 28 分钟。

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

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

队列顺序存储：

头文件：

#pragma once#include
     
      //顺序队列struct SQueue{    void *data[1024]; //保存数据的内存    int size;};typedef void *SeqQueue;#ifdef __cplusplusextern "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
     
      #include
      
       #include
       
        #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\n",front->name,front->age);    printf("队尾元素: Name:%s Age:%d\n", back->name, back->age);    printf("-----------------------------\n");    //输出队列中元素    while (Size_SeqQueue(queue) > 0){        //获得对头元素        front = (struct Person *)Front_SeqQueue(queue);        printf("Name:%s Age:%d\n", front->name, front->age);        //弹出队头元素        Pop_SeqQueue(queue);    }    //打印大小    printf("Size:%d\n",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 __cplusplusextern "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
     
      //链表小节点//目的 ： 第一，让用户数据包含 第二，我需要把用户指针类型转换成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
     
      #include
      
       #include
       
        #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\n",front->name,front->age);    printf("Back: Name:%s Age:%d\n", back->name, back->age);    printf("-------------------------------\n");    //输出队列中的元素    while (Size_LinkQueue(queue) > 0){                front = (struct Person *)Front_LinkQueue(queue);        printf("Name:%s Age:%d\n", front->name, front->age);        //弹出队头元素        Pop_LinkQueue(queue);    }    //销毁队列    Destroy_LinkQueue(queue);}int main(){    test();    system("pause");    return EXIT_SUCCESS;}