当前位置：首页 > article >正文

数据结构 ——链式队列

article 2025/2/1 8:58:09

数据结构 ——链式队列

一、链式队列的定义
链式队列是通过链表实现的一种队列，它将队列的元素通过指针连接起来。链式队列不需要预先分配固定大小的存储空间，因此可以动态增长，更加灵活。
二、基本操作实现
下面是基于变长结构体的双循环链表库进行封装实现链式队列的基本操作，以工程的形式记录

//queueList.h
#ifndef QUEUELIST_H_
#define QUEUELIST_H_
#include "../change/llist_change.h"

typedef LLIST QUEUELIST;
QUEUELIST *queueList_create(int );
int queueList_en(QUEUELIST *,const void *);
int queueList_de(QUEUELIST *,void *);
void queueList_destroy(QUEUELIST *);

#endif

//queueList.c
#include<stdio.h>
#include<stdlib.h>
#include "queueList.h"
//创建
QUEUELIST *queueList_create(int size)
{
    return llist_create(size);
}
//入队
int queueList_en(QUEUELIST *ptr,const void *data)
{
    //尾插方式入队，达到先进先出效果
    return llist_insert(ptr,data,LLIST_BACKWARD);
}
static int always_match(const void *p1,const void *p2)
{
    //返回0表示永远匹配，即拿到删除的该节点
    return 0;
}
//出队
int queueList_de(QUEUELIST *ptr,void *data)
{
    //头删方式出队
    return llist_fetch(ptr,(void *)8,always_match,data);
}
//销毁
void queueList_destroy(QUEUELIST *ptr)
{
    llist_destroy(ptr);
}

//main.c
#include<stdio.h>
#include<stdlib.h>
#include "queueList.h"
#define NAMESIZE 32
struct score_st
{
    int id;
    char name[NAMESIZE];
    int math;
    int chinese;
};
static void  printf_s2(void *record)
{
    struct score_st *r=record;
    printf("%d %s %d %d\n",r->id,r->name,r->math,r->chinese);
}
int main()
{
    QUEUELIST *qu;
    struct score_st tmp;
    qu=queueList_create(sizeof(struct score_st));
    if(qu==NULL)
      return -1;
      //入队测试
    for(int i=0;i<6;i++)
    {
        tmp.id=i;
        sprintf(tmp.name,"stu%d",i);
        tmp.math=rand()%100;
        tmp.chinese=rand()%100;
        if(queueList_en(qu,&tmp)!=0)
          break;
    }
    //出队测试
    while (1)
    {
        int ret=queueList_de(qu,&tmp);
        if(ret!=0)
          break;
        printf_s2(&tmp);
    }
    queueList_destroy(qu);
    return 0;
}