数组、链表、队列和栈----队列，C语言实现

Dear 丶 2023-03-01 05:55 153阅读 0赞

队列，顾名思义就是很多个数据在排队。既然是排队，那就不能从最前面或者中间插进去，新来的数据只能排在队伍的最后。另外，我们另外规定只有队伍最前面的数据才能出去。当然，其实也只有队伍最前面的数据能被外界查看。能满足这种功能的数据结构称之为队列。  
我们可以用数组、链表实现队列。这里用数组实现简单队列。

## 3.1 数组实现简单队列 ##

申请10个位置的数组，用数组实现简单队列

int queue[10];  
    int capacity = 10; //队列的总容量为10 
    
    //队列的范围是head ~ tail
    int head = 0; //队列的头的index为0
    int tail = 0; //队列的尾的index为0

我们需要实现几个方法：

0、依次显示所有数据 (当作数组看待，其实队列不需要这个功能)
    void show() 
    {
        
    	for(int i = head; i < tail; i++)
    	{
        
    		printf("%d, ", queue[i]);  
    	}
    	printf("\r\n");  
    }
    
    1、读取队列的首元素，(不出列)
    void peek()
    {
        
    	if(head >= tail) //队列为空
    	{
        
    		printf("队列中没有数据\r\n"); 
    		return;
    	}
    	printf("队列的首元素: %d \r\n", queue[head]); //数组方式访问数据 
    }
    
    2、入列：在队列最后面插入一个数
    void enqueue(int n) 
    {
        
    	if(tail >= capacity) //队列满了
    	{
        
    		printf("队列满了，无法添加数据\r\n");
    		return;
    	}
    	//tail的位置是空的，所以直接对queue[tail]赋值就是在队列最后插入数据 
    	queue[tail] = n; 
    	tail++; //入列之后tail + 1，保持tail的位置是空的 
    }
    
    3、出列：队列首元素离开队列 
    int dequeue()
    {
        
    	if(head >= tail) //队列为空
    	{
        
    		printf("队列中没有数据，无法出列\r\n"); 
    		return -1;
    	}
    	
    	int num = queue[head]; //记录队列的首元素 
    	head++; //出列: 队列的head不再包含原先的首元素，即删除了队列首元素 
    	return num; //返回数据 
    }
    
    4、计算队列现有多少个元素 
    int getSize()
    {
        
    	//队列的范围是head ~ tail，所以队列中的元素个数是tail - head
    	return tail - head;  
    }

实现了这些功能之后，简单队列的功能就实现了。下面是完整的代码：

#include <stdio.h>
    #include <stdlib.h>
    
    //申请了10个位置的数组，用数组实现简单队列 
    int queue[10];  
    int capacity = 10; //队列的总容量为10 
    
    //队列的范围是head ~ tail
    int head = 0; //队列的头的index为0
    int tail = 0; //队列的尾的index为0
    
    //0、依次显示所有数据 (当作数组看待，其实队列不需要这个功能)
    void show() 
    {
        
    	for(int i = head; i < tail; i++)
    	{
        
    		printf("%d, ", queue[i]);  
    	}
    	printf("\r\n");  
    }
    
    //1、读取队列的首元素，(不出列)
    void peek()
    {
        
    	if(head >= tail) //队列为空
    	{
        
    		printf("队列中没有数据\r\n"); 
    		return;
    	}
    	printf("队列的首元素: %d \r\n", queue[head]); //数组方式访问数据 
    }
    
    //2、入列：在队列最后面插入一个数
    void enqueue(int n) 
    {
        
    	if(tail >= capacity) //队列满了
    	{
        
    		printf("队列满了，无法添加数据\r\n");
    		return;
    	}
    	//tail的位置是空的，所以直接对queue[tail]赋值就是在队列最后插入数据 
    	queue[tail] = n; 
    	tail++; //入列之后tail + 1，保持tail的位置是空的 
    }
    
    //3、出列：队列首元素离开队列 
    int dequeue()
    {
        
    	if(head >= tail) //队列为空
    	{
        
    		printf("队列中没有数据，无法出列\r\n"); 
    		return -1;
    	}
    	
    	int num = queue[head]; //记录队列的首元素 
    	head++; //出列: 队列的head不再包含原先的首元素，即删除了队列首元素 
    	return num; //返回数据 
    }
    
    //4、计算队列现有多少个元素 
    int getSize()
    {
        
    	//队列的范围是head ~ tail，所以队列中的元素个数是tail - head
    	return tail - head;  
    }
    
    int main()
    {
        
    	printf("入列1~5\r\n");
    	for(int i = 1; i <= 5; i++)
    	{
        
    		enqueue(i); //入列
    	}
    	
    	printf("显示所有数据：");
    	show(); //依次显示所有数据
    		
    	printf("出列: %d\r\n", dequeue());
    	printf("出列: %d\r\n", dequeue());
    	peek(); //查看当前首元素 
    	
    	
    	enqueue(6); //入列
    	printf("入列6, 显示所有数据：");
    	show(); 
    	
    	printf("一共有几个元素: %d\r\n", getSize());
    	
    	printf("显示所有数据: ");
    	show(); //依次显示所有数据
    	return 0;
    }

运行结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]如果我们一次性入列15个元素，看看会发生什么情况：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1][]

1、添加10个数据之后，队列就满了。后面5个数据就无法添加进去了。(正确)  
2、出列了2个元素，剩余8个元素，首元素为3 。(正确)  
3、希望入列一个元素6。结果显示队列满了，无法添加数据。但实际上这个队列的容量是10，现有8个元素，容量没有满。这是为什么呢？  
原因是我们在添加数据的时候，tail只会不停地往后移动 (++)，如果tail == 10，tail就再也不能往后移动了。软件就认为是队列满了。但其实队列没有满，队列最前面两个位置已经空出来了，我们可以把数据放在数组的最前面。这部分内容属于“循环队列”，请读者自行实现吧。

最后说明一下，用数组实现的队列，入列、出列的时间复杂度都是O(1)。用数组实现队列最大的问题是如何保证空间够用。如果申请很大的数组，那就会浪费空间。

下一节：链表实现的队列

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/397a62b0c4f14b9eae8566ab2a9589dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: /images/20230209/68941e95210f41398e13342f1d0a97f4.png