队列

一.概念

1.前front 后rear

• 出队，从头出

• 入队，从尾入

2.分类

链式队列，静态队列，循环队列

• 链式队列—用链表实现
• 静态队列—用数组实现，通常都必须是循环队列

3.问题

①静态队列为什么必须是循环队列

r→ r→

​ d d

​ c f→ c

​ b ==> b

f→ a a

👆a和b出队之后，对于数组a来说，a[0]、a[1]这两个空间就被浪费了，因为f和r一直在往上移动，所以相当于a[0]、a[1]不能再使用了。用传统数组来实现队列，无论是入队还是出队，参数都只能增不能减

②循环队列需要几个参数及各个参数的含义

• 需要2个参数来确定 front rear

• 2个参数在不同场合有不同的的定义

  • 场合：

    1）队列初始化

    ​ front和rear的值都是零

    2）队列非空

    ​ front代表的是队列的第一个元素

    ​ rear代表的是队列的最后一个有效元素的下一个

    3）队列空

    ​ front和rear的值相等，但不一定是零

③循环队列出、入队伪算法讲解

1.入队

• 将值存入r所代表的位置

• r=(r+1)%数组的长度

2.出队

• f=(f+1)%数组的长度

④如何判断循环队列是否为空、已满

1.空

• f=r

2.满

• Ⅰ多增加一个标识参数(通常不用这个)

• Ⅱ少用一个元素。本来可以放n个元素，定义n-1个是满的(通常使用这种方式)

  • 如何判断队列已满：r和f的值紧挨着，则队列已满

  • ```c
    if((r+1)%数组的长度==f)

    //已满
    

    else

    //不满
    

    
    
    # 二.代码
    
    ```c
    #include<stdio.h>
    #include<stdbool.h>
    #include<malloc.h>
    #include<stdlib.h>
    
    typedef struct Queue{
    	int *pBase;
    	int front;
    	int rear;
    }QUEUE,*PQUEUE;
    
    void init(PQUEUE);			//初始化 
    bool fullQueue(PQUEUE);		//判断队列是否满 
    bool enQueue(PQUEUE,int);	//入队 
    bool emptyQueue(PQUEUE);	//判断队列是否为空
    void traverse(PQUEUE);		//遍历
    bool outQueue(PQUEUE,int*);	//出队 
    
    int main()
    {
    	//int val;
    	int *pVal=(int*)malloc(sizeof(int)*4);
    	 
    	
    	QUEUE Q;
    	init(&Q);
    	enQueue(&Q,1);
    	enQueue(&Q,2);
    	enQueue(&Q,3);
    	enQueue(&Q,4);
    	enQueue(&Q,5);
    	enQueue(&Q,6);
    	enQueue(&Q,7);
    	
    	traverse(&Q);
    	
    	if(outQueue(&Q,pVal))
    		printf("出队的数字是:%d\n",*pVal);
    	//if (outQueue(&Q,&val))
    		//printf("出队的数字是%d\n",val);
    	else
    		printf("出队失败！\n"); 
    	
    	traverse(&Q);
    	free(pVal);
    	pVal=NULL;
    	
    	return 0;
    }
    
    void init(PQUEUE pQ)
    {
    	pQ->pBase=(int*)malloc(sizeof(int)*6);
    	pQ->front=0;
    	pQ->rear=0;
    }
    
    bool fullQueue(PQUEUE pQ)
    {
    	if((pQ->rear+1)%6==pQ->front)
    		return true;
    	else
    		return false;
    }
    
    bool enQueue(PQUEUE pQ,int val)
    {
    	if(fullQueue(pQ))
    		return false;
    	else
    	{
    		pQ->pBase[pQ->rear]=val;
    		pQ->rear=(pQ->rear+1)%6;
    	}
    }
    
    bool emptyQueue(PQUEUE pQ)
    {
    	if(pQ->rear==pQ->front)
    		return true;
    	else
    		return false;
    }
    
    void traverse(PQUEUE pQ)
    {
    	if(emptyQueue(pQ))
    	{
    		printf("队列为空\n");
    		exit(-1);
    	}
    	else
    	{
    		int i=pQ->front;
    		while(pQ->rear!=i)
    		{
    			printf("%d",pQ->pBase[i]); 
    			i=(i+1)%6;
    		}
    		printf("\n");
    	}
    	return;
    }
    
    bool outQueue(PQUEUE pQ,int *pVal)
    {
    	if(emptyQueue(pQ))
    		return false;
    	else
    	{
    		*pVal=pQ->pBase[pQ->front];
    		pQ->front=(pQ->front+1)%6;
    		return true;
    	}
    }