设为首页收藏本站
切换到窄版

IE盒子

搜索
IE盒子»论坛 › IE盒子 › C语言 › 【C-20】C语言数据结构：队列
返回列表 发帖
查看: 120|回复: 1

【C-20】C语言数据结构：队列

[复制链接]
鱼德洛夫斯基

4

主题

11

帖子

17

积分

新手上路

Rank: 1

积分
17
发表于 2022-9-22 04:33:59 | 显示全部楼层 |阅读模式
1、队列  Queue

队列是一种特殊的受限制的线性表。  队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。


术语：

  • 入队  push
  • 出队  pop
  • 返回队列大小  size
  • 判断是否为空  isEmpty
  • 队头元素  front
  • 队尾元素  back
2、队列的顺序存储

队列也是一种特殊的线性表；可以用线性表顺序存储来模拟队列。
1 接口


  • 初始化队列  init
  • 入队  push
  • 出队  pop
  • 返回队列大小  size
  • 判断是否为空  isEmpty
  • 队头元素  front
  • 队尾元素  back
  • 销毁队列  destroy
2 实现

这里借用【C-18】C语言数据结构：动态数组和单向链表中的dynamicArray.c和dynamicArray.h两个文件进行处理。另外增加三个文件如下：
1 seqQueue.h
#pragma once
#pragma  once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include "dynamicArray.h"
#define  MAX  1024

typedef void* seqQueue;

//初始化队列
seqQueue init_SeqQueue();
//入队
void push_SeqQueue(seqQueue queue, void* data);
//出队
void pop_SeqQueue(seqQueue queue);
//返回队列大小
int size_SeqQueue(seqQueue queue);
//判断队列是否为空
int isEmpty_SeqQueue(seqQueue queue);
//返回队头元素
void* front_SeqQueue(seqQueue queue);
//返回队尾元素
void* back_SeqQueue(seqQueue queue);
//销毁队列
void destroy_SeqQueue(seqQueue queue);2 seqQueue.c
#include "seqQueue.h"

//初始化队列
seqQueue init_SeqQueue()
{
        struct dynamicArray* arr = init_DynamicArray(MAX);
        return arr;
}
//入队
void push_SeqQueue(seqQueue queue, void* data)
{
        //本质  尾插
        if (queue == NULL)
        {
                return;
        }
        if (data == NULL)
        {
                return;
        }
        struct dynamicArray* 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 dynamicArray* myQueue = queue;
        if (myQueue->m_size <= 0)
        {
                return;
        }
        removeByPos_DynamicArray(myQueue, 0);
}
//返回队列大小
int size_SeqQueue(seqQueue queue)
{
        if (queue == NULL)
        {
                return -1;
        }
        struct dynamicArray* myQueue = queue;
        return myQueue->m_size;
}
//判断队列是否为空
int isEmpty_SeqQueue(seqQueue queue)
{
        if (queue == NULL)
        {
                return -1;
        }
        struct dynamicArray* myQueue = queue;
        if (myQueue->m_size == 0)
        {
                return 1;
        }
        return 0;


}
//返回队头元素
void* front_SeqQueue(seqQueue queue)
{
        if (queue == NULL)
        {
                return NULL;
        }
        struct dynamicArray* myQueue = queue;

        return myQueue->pAarr[0];

}
//返回队尾元素
void* back_SeqQueue(seqQueue queue)
{
        if (queue == NULL)
        {
                return NULL;
        }
        struct dynamicArray* myQueue = queue;

        return myQueue->pAarr[myQueue->m_size - 1];
}
//销毁队列
void destroy_SeqQueue(seqQueue queue)
{
        if (queue == NULL)
        {
                return;
        }

        destroy_DynamicArray(queue);

}3 queue_test.c
#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 test02()
{
        //初始化队列
        seqQueue myQueue = init_SeqQueue();

        //准备数据
        struct Person p1 = { "孙悟空",1000 };
        struct Person p2 = { "猪八戒",600 };
        struct Person p3 = { "沙僧",500 };
        struct Person p4 = { "白龙马",400 };
        struct Person p5 = { "唐僧",28 };

        //入队
        push_SeqQueue(myQueue, &p1);
        push_SeqQueue(myQueue, &p2);
        push_SeqQueue(myQueue, &p3);
        push_SeqQueue(myQueue, &p4);
        push_SeqQueue(myQueue, &p5);
        printf("队列大小为：%d\n", size_SeqQueue(myQueue));

        while (isEmpty_SeqQueue(myQueue) == 0)
        {
                //访问队头
                struct Person* pFront = front_SeqQueue(myQueue);
                printf("队头元素 -- 姓名：%s  年龄： %d\n", pFront->name, pFront->age);
                //访问队尾
                struct Person* pBack = back_SeqQueue(myQueue);
                printf("队尾元素 -- 姓名：%s  年龄： %d\n", pBack->name, pBack->age);
                //出队
                pop_SeqQueue(myQueue);
        }

        printf("队列大小为：%d\n", size_SeqQueue(myQueue));

        //销毁队列
        destroy_SeqQueue(myQueue);

}

int main() {
        test02();
}


3、队列的链式存储

队列也是一种特殊的线性表；可以用线性表链式存储来模拟队列的链式存储。
1 设计


  • 节点  只维护指针域，也即是企业版本的实现形式
  • 队列结构体：
  • struct QueueNode pHeader; 头节点
  • int m_Size;  队列大小
  • struct QueueNode * pTail; 尾节点指针
2 接口


  • 初始化队列  init
  • 入队  push
  • 出队  pop
  • 返回队列大小  size
  • 判断是否为空  isEmpty
  • 队头元素  front
  • 队尾元素  back
  • 销毁队列  destroy
3 实现



1 linkQueue.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#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);
//返回队列大小
int size_LinkQueue(LinkQueue queue);
//判断是否为空
int isEmpty_LinkQueue(LinkQueue queue);
//返回队头
void* front_LinkQueue(LinkQueue queue);
//返回队尾
void* back_LinkQueue(LinkQueue queue);
//销毁队列
void destroy_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;
        //更改指针指向
        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 == NULL)
        {
                return;
        }
        if (myQueue->m_size == 0)
        {
                return;
        }
        if (myQueue->m_size == 1)
        {
                myQueue->pHeader.next = NULL;
                myQueue->pTail = &myQueue->pHeader;  //1个节点的时候，要将尾节点还原到头
                myQueue->m_size--;
                return;
        }
        //记录第一个有数据的节点
        struct QueueNode* pFirst = myQueue->pHeader.next;
        //更改指针
        myQueue->pHeader.next = pFirst->next;
        myQueue->m_size--;
}

//返回队列大小
int size_LinkQueue(LinkQueue queue)
{
        if (queue == NULL)
        {
                return -1;
        }

        struct LQueue* myQueue = queue;
        return myQueue->m_size;
}

//判断是否为空
int isEmpty_LinkQueue(LinkQueue queue)
{
        if (queue==NULL)
        {
                return -1;
        }
        struct LQueue* myQueue = queue;
        if (myQueue->m_size == 0)
        {
                return 1;
        }
        return 0;
}

//返回队头数据
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;
}

//销毁队列
void destroy_LinkQueue(LinkQueue queue)
{
        if (queue == NULL)
        {
                return;
        }

        free(queue);
        queue = NULL;
}3 linkQueue_test.c
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include "linkQueue.h"

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

void test01()
{
        //初始化
        LinkQueue myQueue = init_LinkQueue();
        //准备数据
        struct Person p1 = { NULL,"孙悟空",1000 };
        struct Person p2 = { NULL,"猪八戒",600 };
        struct Person p3 = { NULL,"沙僧",500 };
        struct Person p4 = { NULL,"白龙马",400 };
        struct Person p5 = { NULL,"唐僧",28 };

        //插入节点
        push_LinkQueue(myQueue, &p1);
        push_LinkQueue(myQueue, &p2);
        push_LinkQueue(myQueue, &p3);
        push_LinkQueue(myQueue, &p4);
        push_LinkQueue(myQueue, &p5);

        printf("队列大小为：%d\n", size_LinkQueue(myQueue));
        while (isEmpty_LinkQueue(myQueue) == 0)
        {
                //访问队头
                struct Person* pFront = front_LinkQueue(myQueue);
                printf("链式存储::队头元素 -- 姓名：%s  年龄： %d\n", pFront->name, pFront->age);
                //访问队尾
                struct Person* pBack = back_LinkQueue(myQueue);
                printf("链式存储::队尾元素 -- 姓名：%s  年龄： %d\n", pBack->name, pBack->age);
                //出队
                pop_LinkQueue(myQueue);
        }
        printf("队列大小为：%d\n", size_LinkQueue(myQueue));

        //销毁队列
        destroy_LinkQueue(myQueue);
}

int main() {
        test01();
        system("pause");
        return EXIT_SUCCESS;
}
回复

使用道具 举报

草帽海贼

3

主题

11

帖子

20

积分

新手上路

Rank: 1

积分
20
发表于 2025-2-6 16:58:01 | 显示全部楼层
为毛老子总也抢不到沙发？！！
回复

使用道具 举报

返回列表 发帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表