循环队列

港控/mmm° 2022-07-16 13:29 227阅读 0赞

2016年7月31日15:35:10
        队列是一种操作受限的线性表,队列是一种只允许在表头删除,在表尾进行插入的线性表,
        允许插入的一端称为队尾,允许删除的一端称为队头,队列中的数据元素也是一对一的关系
        除第一个元素之外,每个元素只有一个直接前驱元素,除最后一个元素之外,每个元素只有一个后继元素,
        队列的存贮结构有两种:顺序存贮和链式存贮结构,
        顺序队列的表示:通常采用一维数组来存放队头到队尾的所有元素,同时使用两个指针分别指示数组中的第一个元素的位置
        和最后一个元素的位置,指向第一个元素的指针为队头指针front,指向最后一个元素的指针称为队尾指针rear,
        在使用队列前,需要对队列进行初始化,需要达到的效果是使得队列中为空,就是说队列中没有一个元素,也称空队列,
        堆满是指所分配给存放队列的一维数组的空间全部都被占用,没有空闲的内存空间来插入元素,
            1>为什么顺序队列一定是循环队列?
        这是因为顺序队列在进行入队和出队的时候,可能会发生假溢出的情况,[0][1][2][3][4][5][6][7][8][9]对这个队列来说
        front = 0,rear = 10,front指向队列的第一个元素的位置,即队头,rear指向的的是队列的最后一个元素的位置的下一个位置,
        此时队列已满,如果此时进行出队操作,将0,1出队,front = 2,此时如果进行入队操作时,就会出现假溢出的现象
            2>什么是假溢出?
        在对队列进行多次的入队和出队操作时,实际上保存队列元素的一维数组还有存贮空间,但是我们由无法向队列中插入元素.
            3>顺序队列除了假溢出还存在的问题?
        上面的情况,如果我们不插入元素,一直进行元素的删除,那么最后当元素删除完后,front = MAXSIZE时,rear = MAXSIZE;
        这时为数组分配的一维数组的存贮空间将无法继续得到试用,
            4>如何解决这个问题?
        为了避免假溢出的现象,为了充分的利用存贮空间,当队尾指针或队尾指针达到存贮空间的最大值时,让队尾指针和队头指针
        转化为0,这样就可以继续利用没用使用的存贮空间了,一旦当rear == MAXSIZE时,如果还有剩余的可用的内存空间时,令rear = 0;
        就可以继续的向其中插入元素,这样就把顺序队列使用的存贮空间构造成了一个逻辑上首尾相连的循环队列,
            5>我们发现,如果是这样的话,那么当队列空时会有rear == front,当队列满时,这时也有rear = front那么我们如何进行区分呢?
        有两种解决方法:1>增加一个标志位flag,初始时,flag = 0;,当入队成功时flag= 1;,出队列成功有flag = 0;那么空时:
        rear == front && flag ==0;满时 :rear == front && flag = 1;这时因为,队列满的前一个状态是不满,然后进行了入队列的操纵
        使得flag = 1;2>第二中方式:少用一个存贮空间,空时:rear = front;满时:(1)front = 0,rear = MAXSIZE-1;(MAXSIZE位置不使用)
        有效元素的位置为:0->MAXSIZE-2,rear指示的是最后一个元素位置的下一个位置(2)front = 1,rear = 0;(3)front = 2,rear = 1;
        rear所指向的位置永远是未使用的位置,因此满时:(rear+1)%MAXSIZE==front;
        (1)front >rear时,满:front = rear+1;(2)front<rear时,front = (rear+1)%MAXSIZE;综上:(rear+1)%MAXSIZE==front
            6>;这时我们会发现,顺序队列是循环队列,front=或<或>rear;那么我们如何来确定队列中元素的个数呢?
        (1)front == rear时队列无为空:长度为0;(2)front<rear时,长度为:rear-front;(3)front>rear时,长度为:MAXSIZE-1-front+1+rear;
            即为MAXSIZE+rear-front;综上:(rear-front+MAXSIZE)%MAXSIZE

#include<stdio.h>
    #define MAXSIZE 100
    
    typedef int DataType;
    //顺序队列的结构体类型
    typedef struct 
    {
        DataType queue[MAXSIZE];//存贮队列元素的一维数组
        int front;//队头指针指示的是队头元素的位置
        int rear;//队尾指针指示的是队尾元素位置的下一个位置
    }SeqQueue;
    
    //函数前置声明
    void initSeqQueue(SeqQueue * Q );
    void traverseSeqQueue(SeqQueue * Q);
    int isEmpty(SeqQueue * Q);
    int isFull(SeqQueue * Q);
    int enSeqQueue(SeqQueue * Q,DataType element);
    int deSeqQueue(SeqQueue * Q,DataType * element);
    int getLength(SeqQueue * Q);
    int getHead(SeqQueue * Q);
    
    
    //初始化顺序队列
    void initSeqQueue(SeqQueue * Q)
    {
        Q->front = 0;
        Q->rear = Q->front;
        return;
    }
    
    //判断队列是否为空
    int isEmpty(SeqQueue * Q)
    {
        if(Q->front == Q->rear)
            return 1;
        else
            return 0;
    }
    
    //判断队列是否为满
    int isFull(SeqQueue * Q)
    {
        if(Q->front == (Q->rear+1) % MAXSIZE)
            return 1;
        else
            return 0;
    }
    
    //循环队列的入队列操作,入队成功返回1,入队失败返回0;
    int enSeqQueue(SeqQueue * Q,DataType element)
    {
        if( isFull(Q) )
        {
            //printf("队列已满,无法继续进队!\n");
            return 0;
        }
        else
        {
            Q->queue[Q->rear] = element;
            Q->rear = (Q->rear+1)%MAXSIZE;
            return 1;
        }
    }
    
    
    //循环队列出队列操作,出队成功返回1,出队失败返回0;
    int deSeqQueue(SeqQueue * Q,DataType * element)
    {
        if( isEmpty(Q) )
        {
            //printf("队列已空,无法继续出队!\n");
            return 0;
        }
        else
        {
            *element = Q->queue[Q->front];
            Q->front = (Q->front+1)%MAXSIZE;
            return 1;
        }   
    }
    
    //获取队列的长度
    int getLength(SeqQueue * Q)
    {
        return (Q->rear-Q->front+MAXSIZE)%MAXSIZE;
    }
    
    //获取队头元素
    int getHead(SeqQueue * Q,DataType * element)
    {
        if( isEmpty(Q) )
        {
            return 0;
        }
        else
        {
            *element = Q->queue[Q->front];
            return 1;
        }
    }
    
    //遍历循环队列
    void traverseSeqQueue(SeqQueue * Q)
    {
        int i;
    
        if(isEmpty(Q))
            return;
        else if(Q->front<Q->rear)
        {
            for(i = Q->front;i<Q->rear;i++)
            {
                printf("%d ",Q->queue[i]);
            }
        }
        else 
        {
            for( i = Q->front;i<MAXSIZE;i++)
            {
                printf("%d ",Q->queue[i]);          
            }
            for(i = 0;i<Q->rear;i++)
            {
                printf("%d ",Q->queue[i]);
            }
        }
        return ;
    }
    
    //主函数
    int main(void)
    {
        SeqQueue  Q;
        DataType  element;
        int i;
    
        initSeqQueue(&Q);
    
        enSeqQueue(&Q,1);
    
        deSeqQueue(&Q,&element);
        for(i = 0;i<100;i++)
        {
            enSeqQueue(&Q,i);
        }
        traverseSeqQueue(&Q);
        printf("\n");
        return 0;
    }