单端队列---->循环队列

拼搏现实的明天。 2022-06-05 23:49 229阅读 0赞

*  队列
 *  队列是有序表的特殊情形，插入和删除只能够限定在表的两端进行操作，队列的插入使用`put`操作，  
    队列的弹出使用`pop`操作，插入端称为对尾`rear`，删除端称为队头`front`；
 *  对于队列来说常见的操作包括以下几种：  
    
    
     *  1.创建队列`CreateQueue()`;
     *  2.判断队列是否为满`IsFull()`；
     *  3.判断队列是否为空`IsEmpty()`;
     *  4.在对尾添加元素`Add()`；
     *  5.在队首删除元素`Delete()`；
 *  对于队列首先使用一维数组来进行实现；
 *  使用数组实现，应为数组的大小是固定的，可以通过将数组完全初始化为特殊值， 然后通过两个下标来进行元素的访问操作；
 *  通过上面的方式，将数组的任意端作为`rear`都是不影响的；
 *  对于队列来说可以简单的通过数组来实现简单说一下思路，因为单纯使用配普通数组实现缺点很明显  
    
    
     *  1.首先使用`front`和`rear`下标指向`-1`，然后如果添加元素`++rear`；
     *  2.删除元素`++front`这样的过程是先很是简单，判断`rear==MAX_SIZE`就不能够在数组里面添加元素，同样的`rear==MAX_SIZE`就不能够删除元素；
     *  通过上述的分析缺点立马就出现的，首先对于空间很浪费，其次数组空间没有办法重复使用；
 *  接下来分析通过循环数组的方式来实现队列：
    
     *  1.取余运算符`%`可以将超出范围的数字限定在数组大小`MAX_SIZE`里面，所以在`rear`,`front`在自加超过`MAX_SZIE`进行取余运算；
        
            rear=(rear+1)%MAX_SIZE;
            front=(front+1)%MAX_SIZE;
     *  2.在循环队列的实现过程中，添加元素需要进行判断是否为满的操作，在删除元素时，需要判断队列是否为空的操作；
     *  ![循环队列的示意图][SouthEast]  
        
        
         *  在循环队列里面，可以使用`rear`是否等于`front`来判断队列为空或者是为满，为了区分这两种情况，通过不讲循环队列里面的元素填充满的方式来进行区分；
         *  首先让`front`和`rear`都指向数组的下标`0`，在进行元素填充时，`＋＋rear`进行移动，这样下标`0`的位置是没有填充元素的，在进行删除时，也是不会删除下标为`0`位置的值的，这是在第一轮，在对列的循环过程中，这个位置仍然会被使用，但是在循环队列里面总有一个位置是没有元素的；  
            **这里对于`front`表示的含义是添加元素的一段，`rear`表示的是删除元素的一端**
    
        //判断是否为空的操作
        int IsEmpty()
        {
            if(QueueIntoo[0].rear!=QueueIntoo[0].front)
                return false;
            else
                return true;
        }
        //判断队列是否为满的操作；
        int  IsFull()
        {
            if((QueueIntoo[0].front+1)%MAX_SIZE==QueueIntoo[0].rear)
                return true;
            else
                return false;
        }
 *  实现队列的源码是

//
    #include<stdio.h>
    #include<stdlib.h>
    #define MAX_SIZE 5
    #define true 1
    #define false 0
    typedef struct
    {
        int key;
    } elements;
    typedef struct
    {
        int rear;
        int front;
    } QueueInto;
    
    //Queue by array
    //定义数组用来模拟队列
    elements Queue[MAX_SIZE];
    //使用一个结构体用来保存rear,front等信息，这里是用数组主要是
    //为了能够定义多个队列；
    QueueInto QueueIntoo[1];
    //队列的初始化函数
    void QueueInit()
    {
        QueueIntoo[0].rear = 0;
        QueueIntoo[0].front = 0;
    }
    //用来判断队列是否为空
    int IsEmpty()
    {
        if(QueueIntoo[0].rear!=QueueIntoo[0].front)
            return false;
        else
            return true;
    }
    //用来判断队列是否为满
    int  IsFull()
    {
        if((QueueIntoo[0].front+1)%MAX_SIZE==QueueIntoo[0].rear)
            return true;
        else
            return false;
    }
    //在添加元素的过程中，判断是否为满的情况；
    void AddQueue(int data)
    {
        //添加元素判断是否为满的位置
        QueueIntoo[0].front = (QueueIntoo[0].front+1)%MAX_SIZE;
        if(QueueIntoo[0].front==QueueIntoo[0].rear){
            fprintf(stderr,"The Queue is Full\n");
            exit(EXIT_FAILURE);
        }
        Queue[QueueIntoo[0].front].key = data;
    }
    
    int DeleQ()
    {
        //删除元素判断是否为空的位置是不同的；
        if(QueueIntoo[0].rear==QueueIntoo[0].front){
            fprintf(stderr,"The Queue Is empty\n");
            exit(EXIT_FAILURE);
        }
        QueueIntoo[0].rear=(QueueIntoo[0].rear+1)%MAX_SIZE;
        return Queue[QueueIntoo[0].rear].key;
        printf("\n");
    }
    int main()
    {
    
        QueueInit();
        AddQueue(5);
        AddQueue(4);
        AddQueue(3);
        AddQueue(2);
    // printf("%d \n",IsFull());
    
    // AddQueue(1);
    // AddQueue(5);
        printf("MyQueue contains:\n");
        printf("%d ",DeleQ());
        printf("%d ",DeleQ());
        printf("%d ",DeleQ());
        printf("%d\n",DeleQ());
    // DeleQ();
    //
        AddQueue(7);
        AddQueue(8);
        AddQueue(9);
        printf("MyQueue contains:\n");
        printf("%d ",DeleQ());
        printf("%d ",DeleQ());
        printf("%d\n",DeleQ());
        printf("The Queue contains:\n");
        int8_t i;
        for (i = 0; i <MAX_SIZE; i++)
        {
            printf("%d ", Queue[i].key);
        }
        return 0;
    }

[SouthEast]: /images/20220606/71da7d681bfa4b79a6664939f65026ae.png