队列的实现与基本操作

古城微笑少年丶 2022-06-03 00:17 204阅读 0赞

## **1.链队列** ##

\*  
**存储结构：**

typedef struct LQNode
    {
        DataType info;
        struct LQNode *next;
    }LQNode;
    
    typedef struct
    {
        struct LQNode *front;
        struct LQNode *rear;
    }LinkQueue;

**基本操作的实现：**

//创建空队列
    LinkQueue *LQueueCreateEmpty()
    {
        LinkQueue *plq=(LinkQueue*)malloc(sizeof(LinkQueue));
        LQNode *p=(LQNode*)malloc(sizeof(LQNode));
        p->next=NULL;
        plq->front=plq->rear=p;
        return plq;
    }
    
    //判断队列是否空
    int LQueueIsEmpty(LinkQueue *plq)
    {
        if(plq->front==plq->rear)
        {
            return TRUE;
        }
        else
            return FALSE;
    }
    
    //入队
    void LQueueEnqueue(LinkQueue *plq,DataType x)
    {
        LQNode *p=(LQNode*)malloc(sizeof(LQNode));
        if(p==NULL)
            printf("内存分配失败\n");
        else
        {
            p->info=x;
            p->next=NULL;
            plq->rear->next=p;
            plq->rear=p;
        }
    }
    
    //出队
    int LQueueDeQueue(LinkQueue *plq,DataType *x)
    {
        LQNode *p;
        if(plq->front==plq->rear)
        {
            printf("队列空\n");
            return ERROR;
        }
        else
        {
            p=plq->front->next;
            *x=p->info;
            plq->front->next=p->next;
            free(p);
            return OK;
        }
    }
    
    //返回队首元素
    DataType LQueueFront(LinkQueue *plq)
    {
        if(plq->front==plq->rear)
        {
            printf("队列空\n");
            exit(0);
        }
        return (plq->front->next->info);
    }

# **2.循环队列** #

**存储结构：**

typedef struct
    {
        int front,rear;
        DataType data[MAXSIZE];
    }SeqQueue;

**基本操作的实现：**

//创建
    SeqQueue *SQueueCreate()
    {
        SeqQueue *sq=(SeqQueue*)malloc(sizeof(SeqQueue));
        if(sq==NULL)
            printf("溢出\n");
        else
            sq->front=sq->rear=0;
        return sq;
    }
    
    //判空
    int SQueueIsEmpty(SeqQueue *sq)
    {
        if(sq->front==sq->rear)
            return TRUE;
        else 
            return FALSE;
    }
    
    //入队
    void SQueueEnQueue(SeqQueue *sq,DataType x)
    {
        if((sq->rear+1)%MAXSIZE==sq->front)
            printf("队列满");
        else
        {
            sq->rear=(sq->rear+1)%MAXSIZE;
            sq->data[sq->rear]=x;
        }
    }
    
    //出队
    int SQueueDeQueue(SeqQueue *sq,DataType *e)
    {
        if(sq->front==sq->rear)
        {
            printf("队空\n");
            return ERROR;
        }
        else
        {
            sq->front=(sq->front+1)%MAXSIZE;
            *e=sq->data[sq->front];
            return OK;
        }
    }
    
    //取队首元素
    DataType SQueueFront(SeqQueue *sq)
    {
        if(sq->front==sq->rear)
        {
            printf("队空下溢\n");
            return ERROR;
        }
        else
            return (sq->data[(sq->front+1)%MAXSIZE]);
    }
    
    //输出循环队列
    void SQueuePrint(SeqQueue *sq)
    {
        int i=(sq->front+1)%MAXSIZE;
        while(i!=sq->rear+1)
        {
            printf("\t%d",sq->data[i]);
            i=(i+1)%MAXSIZE;
        }
    }