循环队列模型

淩亂°似流年 2022-05-28 03:09 50阅读 0赞

# 循环队列模型:  #

循环队列存在一个问题：队头=队尾时，队列的情况可能为空也可能为满。决绝问题的方法为重新定义队列的满和空：头和尾之间始终空出一个不用的数据空间，队列为**空**的时候，头在尾前一个位置，**满**的时候头尾之间相差一个空的数据，即头在尾部前两个位置。

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

/************************************* * 文件名：CircleQueue.c * 文件描述：实现循环队列模型 * 编辑人：王廷云 * 编辑日期：2017-11-21 * 修改日期：2018-2-1 *************************************/
    #include <stdio.h>
    
    #define QUEUE_LEN (10+1) // 其中一个是不使用的 
    
    /* 队列模型函数 */
    void inQueue(int data);         // 入队
    int outQueue(void);             // 出队
    int isEmptyQueue(void);         // 队空
    int isFullQueue(void);          // 队满
    
    static int queue[QUEUE_LEN];    // 队列长度
    int head = 0;                   // 队头
    int tail = -1;                  // 队尾
    
    int main(void)
    { 
    	int num;
    	int ret;
    	int i;
    
    	/* 获取数据并入队 */
    	printf("\033[32m=== Input 10 num ===\033[0m\n");
    	while (1)
    	{ 
    		/* 只有队列不为空才能入队 */
    		if (isFullQueue())
    		{ 
    			printf("Queue is full!\n");
    			while (getchar() != '\n'); // 去掉多余的字符
    			break;
    		}
    		
    		/* 获取并检查输入 */
    		ret = scanf("%d", &num);
    		if (ret != 1)
    		{ 
    			printf("\033[31m===Input Error===\033[0m\n");
    			return -1;
    		}
    		
    		inQueue(num);       // 入队数据
    	}
    	
    	/* 出队三个数 */
    	for (i = 0; i < 3; i++)
    	{ 
    	    if (!isEmptyQueue())
    	    { 
    		    printf("Out Queue %d: %d\n", head, outQueue());
    	    }
    	}
    	
        /* 再次入队三个 */
        for (i = 0; i < 3; i++)
        { 
            printf("Input Data: ");
    	    scanf("%d", &num);
    	    if (!isFullQueue())
    	    { 
    		    inQueue(num);
    	    }
        }
        
        /* 把剩余没有出队的数出队来检查是否为循环队列 */
    	while (!isEmptyQueue())
    	{ 
    		printf("Out Queue %d: %d\n", head, outQueue());
    	}
    
    	return 0;
    }
    
    /** * 函数名：inQueue * 函数功能：把数据入队 * 参数：data: 需要入队的数据 * 返回值：void */
    void inQueue(int data)
    { 
    	tail = (tail+1) % QUEUE_LEN;    // 先改变队尾
    	queue[tail] = data;	            // 再入队
    }
    
    /** * 函数名：outQueue * 函数功能：把数据出队 * 参数：void * 返回值：队头的数据 */
    int outQueue(void)
    { 
    	int temp;
    	
    	temp = queue[head];             // 先出队
    	head = (head+1) % QUEUE_LEN;    // 再改变队尾
    	
    	return temp;                    // 返回队头数据
    }
    
    /** * 函数名：isEmptyQueue * 函数功能：判断队列是否为空 * 参数：void * 返回值：队列为空返回1，不为空返回0 */
    int isEmptyQueue(void)
    { 
    	return head == tail+1;                // 队头在队尾前一个位置为空
    }
    
    /** * 函数名：isFullQueue * 函数功能：判断队列是否为满 * 参数：void * 返回值：队列为满返回1，不为满返回0 */
    int isFullQueue(void)
    { 
    	return (tail+2) % QUEUE_LEN == head;  // 队头在队尾前两个位置为满
    }