数据结构之队列（C语言）基础

拼搏现实的明天。 2022-04-03 01:56 310阅读 0赞

队列（Queue）:

是一种先进先出的线性表（FIFO）,也分为两种，链队列和循环队列（好像还有其他的类型，忘了。。）

这里就介绍这两种的一些简单函数。

1、链队列

毋庸置疑，就是链式存储队列，有两个指针front和rear，其中front负责进队，rear负责出队

代码如下

/*
        数据结构之链队列
        实现函数：
        初始化；入队；出队；判断是否队空，销毁；输出
    */
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int ElemType;
    typedef int Status;
    typedef struct Node{
        ElemType data;
        struct Node *next;
    }QNode,*QueuePtr;
    typedef struct{
        QueuePtr front;
        QueuePtr rear;
    }LinkQueue;
    
    Status InitQueue(LinkQueue &Q){
        Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
        if(!Q.front)
            exit(OVERFLOW);
        Q.front->next = NULL;
        return OK;
    }
    
    Status EnQueue(LinkQueue &Q,ElemType e){
        QueuePtr p;
        p = (QueuePtr)malloc(sizeof(QNode));
        if(!p)
            exit(OVERFLOW);
        p->data = e;
        p->next = NULL;
        Q.rear->next = p;
        Q.rear = p;
        return OK;
    }
    
    Status DeQueue(LinkQueue &Q,ElemType &e){
        if(Q.front == Q.rear)
            return ERROR;
        QueuePtr p =  Q.front->next;
        e = p->data;
        Q.front->next = p->next;
        if(Q.rear == p)
        {
            Q.rear = Q.front;
        }
        free(p);
        return OK;
    }
    
    bool isEmpty(LinkQueue &Q){
        if(Q.front == Q.rear)
            return true;
        else
            return false;
    }
    
    Status DestroyQueue(LinkQueue &Q){
        while(Q.front){
            Q.rear = Q.front->next;
            free(Q.front);
            Q.front = Q.rear;
        }
        return OK;
    }
    void PutQueue(LinkQueue &Q){
        QueuePtr p = Q.front->next;
        while(p){
            printf("%d ",p->data);
            p = p->next;
        }
        printf("\n");
    }
    
    //测试用例可自行举例
    int main(){
        LinkQueue Q;
        InitQueue(Q);
        int num,i,tmp;
        printf("请输入要入队的个数：\n");
        scanf("%d",&num);
        for(i = 0; i < num; i++){
            scanf("%d",&tmp);
            EnQueue(Q,tmp);
        }
        PutQueue(Q);
        DeQueue(Q,tmp);
        PutQueue(Q);
        return 0;
    }

2、循环队列

循环队列，意思就是队尾和对头相连，想象成一个环状，可以防止数组越界而破坏代码。

细节在代码中

代码如下

/*
        数据结构之循环队列
        实现函数：
        初始化；入队；出队；求队长；输出
    */
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    #define MAXQSIZE 10 //实际存放的数字比这个数小 1，原因是留下一个不用，用来判断是否队满
    typedef int ElemType;
    typedef int Status;
    typedef struct {
        ElemType *data;
        int front;
        int rear;
    }SqQueue;
    
    Status InitQueue(SqQueue &Q){
        Q.data = (ElemType *)malloc(sizeof(ElemType));
        if(!Q.data){
            exit(OVERFLOW);
        }
        Q.front = Q.rear = 0;
        return OK;
    }
    
    Status EnQueue(SqQueue &Q,ElemType e){
        if((Q.rear + 1) % MAXQSIZE == Q.front){
           return ERROR;
        }
        Q.data[Q.rear] = e;
        Q.rear = (Q.rear + 1) % MAXQSIZE;
        return OK;
    }
    Status DeQueue(SqQueue &Q,ElemType &e){
        if(Q.front == Q.rear)
            return ERROR;
        e = Q.data[Q.front];
        Q.front = (Q.front+1) % MAXQSIZE;
        return OK;
    }
    
    int QueueLength(SqQueue &Q){
        return ((Q.rear - Q.front) % MAXQSIZE);
    }
    void PutQueue(SqQueue &Q){
        int len = QueueLength(Q);
        int i;
        for(i = 0; i < len; i++){
            if(i == 0)
                printf("%d",Q.data[i]);
            else
                printf(" %d",Q.data[i]);
        }
        printf("\n");
    }
    
    //测试用例可以自行更改
    int main(){
        SqQueue Q;
        InitQueue(Q);
        int num,i,tmp;
        printf("请输入要插入的个数：\n");
        scanf("%d",&num);
        for(i = 0 ;i < num; i++){
            scanf("%d",&tmp);
            EnQueue(Q,tmp);
        }
        PutQueue(Q);
        DeQueue(Q,tmp);
        PutQueue(Q);
    }