使用标志量消除循环链表“假溢出”的入队和出队算法

短命女 2022-05-24 08:26 127阅读 0赞

**问题：**要求循环变量不损失一个空间全部都能利用，设置一个标志量tag，以tag为0或为1来区分头尾指针相同时的队列状态。请编写出此结构相应的入队与出队算法。

--------------------

设标志位tag，初始化时将tag置为0，当入队成功时tag = 1；出队成功时tag = 0；队列为空的判断条件为：`(SCQ->front == SCQ->rear) && (SCQ->tag == 0)` 队列为满的判断条件为：`(SCQ->front == SCQ->rear) && (SCQ->tag == 1)`。

**入队算法**

void EnterQueue(SeqCirQueue* SCQ,DataType data)
    {
        //判断队列是否已满
        if (IsFull(SCQ))
        {
            printf("队列已满，不能入队");
            return;
        }
        //在队尾插入元素data
        SCQ->Queue[SCQ->rear] = data; 
        //队尾指针后移一个位置
        SCQ->rear = (SCQ->rear + 1)%MaxSize;
        //入队成功令tag =1
        SCQ->tag = 1;
    }

**出队算法**

int DeleteQueue(SeqCirQueue* SCQ, DataType* data)
    {
        if (IsEmpty(SCQ))
        {
            printf("队列为空,不能出队！\n");
            return 0;
        }
        //将出队元素值赋给打他
        *data = SCQ->Queue[SCQ->front];
        //队头指针后移
        SCQ->front = (SCQ->front + 1)%MaxSize;
        //将tag置0
        SCQ->tag = 0;
        //返回出队元素值
        return *data;
    }

--------------------

**源代码**

#include <stdio.h>
    #include <stdlib.h>
    #include <Windows.h>
    #include <assert.h>
    
    #define MaxSize 10
    typedef int DataType;
    
    typedef struct SCQueue
    {
        DataType Queue[MaxSize];
        int front;
        int rear;
        int tag;
    }SeqCirQueue ;
    
    //队列的初始化
    void InitQueue(SeqCirQueue* SCQ)
    {
        SCQ->front = SCQ->rear = 0;
        SCQ->tag = 0;
    }
    
    //判断队列是否为空
    
    int IsEmpty(SeqCirQueue* SCQ)
    {
        if ((SCQ->front == SCQ->rear) && (SCQ->tag == 0))
        {
            return 1;
        }
        return 0;
    }
    
    //判断队列是否为满
    
    int IsFull(SeqCirQueue* SCQ)
    {
        if ((SCQ->front == SCQ->rear) && (SCQ->tag == 1))
        {
            return 1;
        }
        return 0;
    }
    
    
    //入队操作
    
    void EnterQueue(SeqCirQueue* SCQ,DataType data)
    {
        //判断队列是否已满
        if (IsFull(SCQ))
        {
            printf("队列已满，不能入队");
            return;
        }
        //在队尾插入元素data
        SCQ->Queue[SCQ->rear] = data;    
        //队尾指针后移一个位置
        SCQ->rear = (SCQ->rear + 1)%MaxSize;
        //入队成功令tag =1
        SCQ->tag = 1;
    }
    
    int DeleteQueue(SeqCirQueue* SCQ, DataType* data)
    {
        if (IsEmpty(SCQ))
        {
            printf("队列为空,不能出队！\n");
            return 0;
        }
        //将出队元素值赋给打他
        *data = SCQ->Queue[SCQ->front];
        //队头指针后移
        SCQ->front = (SCQ->front + 1)%MaxSize;
        //将tag置0
        SCQ->tag = 0;
        //返回出队元素值
        return *data;
    }
    
    // 打印队列元素
    void PrintQueue(SeqCirQueue* SCQ)
    {
        assert(SCQ);   //断言SCQ不为空
        int i = SCQ->front;
        if (SCQ->front < SCQ->rear)
        {
            for (; i < SCQ->rear; i++)
            {
                printf("%-3d", SCQ->Queue[i]);
            }
        }
        else
        {
            for (i; i <SCQ->rear + MaxSize; i++)
            {
                printf("%-3d", SCQ->Queue[i%MaxSize]);
            }
        }
        printf("\n");
    }
    
    
    int main()
    {
        SeqCirQueue SCQ;
        DataType data;
        InitQueue(&SCQ);
        printf("1-10依次入队:\n");
        EnterQueue(&SCQ, 1);
        EnterQueue(&SCQ, 2);
        EnterQueue(&SCQ, 3);
        EnterQueue(&SCQ, 4);
        EnterQueue(&SCQ, 5);
        EnterQueue(&SCQ, 6);
        EnterQueue(&SCQ, 7);
        EnterQueue(&SCQ, 8);
        EnterQueue(&SCQ, 9);
        EnterQueue(&SCQ, 10);
        printf("队列中的元素为:");
        PrintQueue(&SCQ);
        printf("第一次出队!\n");
        data = DeleteQueue(&SCQ, &data);
        printf("出队的元素为：%d\n",data);
        printf("第二次出队!\n");
        data = DeleteQueue(&SCQ, &data);
        printf("出队的元素为：%d\n", data);
        PrintQueue(&SCQ);
        printf("20入队\n");
        EnterQueue(&SCQ, 20);
        printf("30入队\n");
        EnterQueue(&SCQ, 30);
        printf("队列中的元素为:");
        PrintQueue(&SCQ);
        system("pause");
        return 0;
    }

--------------------

**运行结果**  
![这里写图片描述][70]

[70]: /images/20220524/76e2050aeaac45f89cc8f23fea143785.png