队列的基本概念介绍以及典型应用示例

灰太狼 2023-02-22 08:29 27阅读 0赞

### 一、队列的概念介绍 ###

提到队列这个词，或许你不会感到陌生，在我们的生活中，应用到队列这个概念的场景非常之多。我们日常的排队买饭，总是第一个到达窗口的人先买到然后离开，后来的人总是后来离去；再有，去医院挂号排队，也总是遵循一般的先来先就医服务的原则。计算机中的队列数据结构的设计，也是为了更好地解决这类先来先服务问题的。(更好的阅读体验，请访问[程序员在旅途][Link 1])  
        队列是一种采用先来先服务(First in First Out,FIFO)思想的抽象数据结构。和栈一样，它也是一种受限制的线性表。队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列的插入操作称之为入队列或进队列，队列的删除操作称之为退队列或出队列。当线性表中没有元素的时称为空队列。示意图如下：  
  
![栈示意图][20200702194701893.png_pic_center]  
        在队列上的基本操作有：①队列初始化②判断队空③入队操作④出队操作⑤读取队头元素⑥销毁队列。根据在物理实现方式上的不同，分为顺序队列和链式队列，基于数组实现的顺序存储的队列叫作顺序队列，基于链表实现的队列叫作链式队列。

### 二、顺序队列的操作实现 ###

采用顺序存储的队列称为顺序队列，在使用队列前，要分配一块连续的存储空间来存放队列里面的元素。由于队列的头尾都是会变化移动的，因此，就有队头队尾两个指示变量，指向队列的头尾。顺序队列的类型定义如下：

> \#define MAXSIZE 100  
> typedef struct\{  
>     ElementType data\[MAXSIZE\];  
>     int front,rear;  
> \}SeqQuene,\* PSeqQueue;

定义一个指向队列的指针：

PSeqQueue queue = (PSeqQueue)malloc(sizeof(SeqQuene));

从队列的类型定义上可以看到，队列的数据区为 queue->data\[0\] ~ queue->data\[MAXSIZE-1\]。队头变量queue->front取值范围(0<= queue->front <=MAXSIZE-1),队尾变量queue->rear取值范围(0<= queue->rear <=MAXSIZE-1)。  
        队列是使用数组进行元素的存储，它在内存分配上是静态分配，一旦初始化之后，内存空间的大小就确定了。而队列的操作是一个动态的过程，随着入队的进行，queue->rear的值会超过MAXSIZE，随着出队的进行，queue->front也会逐渐增加，就会导致数组空间实际上还有空闲的空间，但是不能进行元素的入队了，从而出现假溢出的现象。为了解决这种假溢出的问题，可以采用一种称为"循环队列"的特殊队列，循环队列是将队列的数据区data\[0…MAXSIZE-1\]看成头尾相接的循环结构，头尾的指示变量front、rear关系不变。循环队列的示意图如下：![循环队列示意图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NzU0MDYx_size_16_color_FFFFFF_t_70_pic_center]  
    对这种首尾相接的循环队列结构来说，进队出队的操作会有一些小的修改，以满足循环的需求。

> 入队： queue->rear = (queue->rear + 1) % MAXSIZE;  
> 出队： queue->front = (queue->front +1) % MAXSIZE;

了解了入队和出队的操作，我们需要判断，什么时候队列满了，什么时候队列为空。空的情况很好判断，只要 queue->front = queue->rear就可以认为队列为空。队满的情况的讨论，当队列中元素逐渐增多，queue->rear 会最终追上queue->front的，这时候两者也是相等，但此时队列非空，相反却是队满的情况，为了方便判断队列的队满队空情况，可以采用少用一个元素空间的方法，使得rear永远追不上front，也就是queue->front所指的位置不用，当 (rear+1)%MAXSIZE = front 的时候，队列是满的。

#### 2.1 队列初始化 ####

队列在使用之前需要进行初始化。初始化的过程包括分配队列需要占用的内存空间，以及给队头队尾变量赋初值。

> //初始化队列  
> PSeqQueue init\_seqqueue()\{  
> 　//申请队列需要的内存空间  
> 　PSeqQueue queue = (PSeqQueue)malloc(sizeof(SeqQueue));  
> 　if(queue)\{  
> 　　queue->front = 0;  
> 　　queue->rear = 0;  
> 　\}  
> 　return queue;  
> \}

#### 2.2 判断队列是否为空 ####

在出队或者获取队首元素的时候，都要进行队列非空判断

> //判断队列是否为空。1代表空，0代表非空  
> int empty\_seqqueue(PSeqQueue queue)\{  
> 　if(queue && (queue->front == queue->rear))\{  
> 　　return 1;  
> 　\}else\{  
> 　　return 0;  
> 　\}  
> \}

#### 2.3 入队列 ####

> int in\_seqqueue(PSeqQueue queue , ElementType x)\{  
> 　//判断队列是否满了  
> 　if((queue->rear+1)%MAXSIZE == queue->front)\{  
> 　　printf(“队列满了”);  
> 　　 return 0;  
> 　\}else\{  
> 　　//入队列.  
> 　　queue->rear = (queue->rear +1) % MAXSIZE;  
> 　　queue->data\[queue->rear\] = x;  
> 　　return 1;  
> 　\}  
> \}

#### 2.4 出队列 ####

> int out\_seqqueue(PSeqQueue queue , ElementType \*x)\{  
> 　//出队列的时候要判断队列是否为空  
> 　if(empty\_seqqueue(queue))\{  
> 　　printf(“队列为空，不可出队”);  
> 　　return 0;  
> 　\}else\{  
> 　　//由于是循环队列，queue->front指示位置的元素不用，因此要+1才是要出队的元素  
> 　　queue->front = (queue->front + 1) % MAXSIZE;  
> 　　\*x = queue->data\[queue->front\];  
> 　　return 1;  
> 　\}  
> \}

#### 2.5 读取队头元素 ####

> int getFront\_seqqueue(PSeqQueue queue , ElementType \*x)\{  
> 　//出队列的时候要判断队列是否为空  
> 　if(empty\_seqqueue(queue))\{  
> 　　printf(“队列为空，不可获取队头元素”);  
> 　　return 0;  
> 　\}else\{  
> 　　//由于是循环队列，queue->front指示位置的元素不用，因此要+1才是队头的元素  
> 　　\*x = queue->data\[(queue->front+1)%MAXSIZE\];  
> 　　return 1;  
> 　\}  
> \}

#### 2.6 销毁队列 ####

由于是动态申请的空间，因此，在使用完成之后，要进行内存的释放。

> void destory\_seqqueue(PSeqQueue \*queue)\{  
> 　if(\*queue)\{  
> 　　free(\*queue);  
> 　\}  
> 　\*queue = NULL;  
> \}

### 三、链式队列的操作实现 ###

队列是线性结构的一种，因此，也可以用链式结构的方式来实现。并且，链式结构的队列，由于节点空间都是在入队的时候动态申请的 ，因此，在计算机内存空间足够的情况下，一般不需要考虑队满的情况，也就不存在溢出的情况，所以不需要使用循环链式队列来处理假溢出的情况。 链式队列示意图如下：![链式队列示意图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NzU0MDYx_size_16_color_FFFFFF_t_70_pic_center 1]  
        链队节点的结构和单链表一样，同时为了操作上的方便，可以重新定义一个链队的结构体，包含有头尾指针指向队列的头部和尾部。链队的结构体描述如下：

> //节点结构  
> typedef struct node\{  
> 　ElementType data;  
> 　struct node \*next;  
> \}Qnode,\*PQnode;  
> //链栈结构  
> typedef struct \{  
> 　PQnode front,rear;  
> \}LinkQueue,\*PLinkqueue;

定义一个指向链队的指针

PLinkqueue queue = (PLinkqueue)malloc(sizeof(LinkQueue));

在使用链表来存储队列数据的时候，带不带头结点完全看我们的需求，如果在操作上需要使用头结点 来方便统一操作，就是用头结点 ，否则就可以不用加头结点。  
        queue->front指向链队的队头元素，queue->rear指向链队的队尾元素。出队的时候删除链表的首元结点，让后继节点成为首元节点，然后修改队头指针使其指向新的首元节点即可，入队是在链表末尾插入元素，然后修改队尾指针指向新的链尾即可。

#### 3.1 初始化链式队列 ####

队列的初始化就是为队列结构分配内存空间，同时给front、rear指针置空值，为入队列做准备。

> PLinkqueue init\_linkqueue()\{  
> PLinkqueue queue = (PLinkqueue)malloc(sizeof(LinkQueue));  
> 　if(queue)\{  
> 　　queue->front = NULL;  
> 　　queue->rear = NULL;  
> 　\}  
> 　return queue;  
> \}

#### 3.2 判断队列是否为空 ####

> //判断链队为空；1空队列，0非空。  
> int empty\_linkqueue(PLinkqueue queue)\{  
> 　if(queue && (queue->front == NULL) && (queue->rear ==NULL))\{  
> 　　return 1;  
> 　\}else\{  
> 　　return 0;  
> 　\}  
> \}

#### 3.3 入队 ####

链式队列的入队，就是在链表的链尾插入元素，然后让队尾指针指向链尾元素。

> int in\_linkqueue(PLinkqueue queue, ElementType x)\{  
> 　PQnode p = (PQnode)malloc(sizeof(Qnode));  
> 　if(!p)\{  
> 　　printf(“内存溢出，不能申请新的节点空间\\n”);  
> 　　return 0;  
> 　\}  
> 　p->data = x;  
> 　p->next = NULL;  
> 　//要先判断队列中是否有元素，两者的的入队是有一些差别的  
> 　if(empty\_linkqueue(queue))\{  
> 　　queue->rear = p;  
> 　　queue->front = p;  
> 　\}else\{  
> 　　//入队的时候，在队尾插入元素  
> 　　queue->rear->next = p;  
> 　　queue->rear = p;  
> 　\}  
> 　return 1;  
> \}

#### 3.4 出队 ####

链式队列的出队，就是将链表的首元节点从链表中删去，让其后继节点成为首元节点，然后让队头指针指针指向该节点。

> int out\_linkqueue(PLinkqueue queue, ElementType \*x)\{  
> 　if(empty\_linkqueue(queue))\{  
> 　　printf(“队空，无法出队\\n”);  
> 　　return 0;  
> 　\}  
> 　//出队首元素节点  
> 　\*x = queue->front->data;  
> 　PQnode temp\_front= queue->front;  
> 　//队首的下一个元素作为队首  
> 　queue->front = temp\_front->next;  
> 　//释放出队节点  
> 　free(temp\_front);  
> 　//如果队首为空，说明此时队列中没有元素节点了，则设置队尾也为空。  
> 　if(!queue->front)\{  
> 　　queue->rear = NULL;  
> 　\}  
> 　return 1;  
> \}

#### 3.5 获取队头元素 ####

即获取front指针指向的节点。

> int getFront\_linkqueue(PLinkqueue queue, ElementType \*x)\{  
> 　if(empty\_linkqueue(queue))\{  
> 　　printf(“队空，无法获取队首 元素\\n”);  
> 　　return 0;  
> 　\}  
> 　\*x = queue->front->data;  
> 　return 1;  
> \}

#### 3.6 销毁队列 ####

由于动态分配的内存空间 ，在使用完队列之后，要把申请的空间及时的释放掉。具体做法就是遍历单链表，释放每一个节点。

> //销毁队列。由于使用的是链表，因此，要释放每一个链表节点的空间  
> void destory\_linkqueue(PLinkqueue \*queue)\{  
> 　PQnode p;  
> 　if(\*queue)\{  
> 　　while((\*queue)->front)\{  
> 　　　　p = (\*queue)->front;  
> 　　　　(\*queue)->front = (\*queue)->front->next;  
> 　　　　free(p );  
> 　　\}  
> 　　free(\*queue);  
> 　\}  
> 　\*queue = NULL;  
> \}

### 四、典型应用示例 ###

有n个元素存储在数组A\[n\]中，设计一个算法，实现将这n个元素循环向左移动k(0<k<n)位。  
        **思路分析**：将数组的A\[0\] ~ A\[k-1\]元素先顺序放入一个队列中，然后再将数组A\[k\] ~A\[n-1\]元素依次左移k位，然后再将队列中保存的数组元素A\[0\] ~ A\[k-1\]顺序出队列，依次放入A\[n-k\] ~A\[n-1\]的位置。具体的算法如下：

> void array\_leftcircle\_move(int a\[\], int n, int k)\{  
> 　int i;  
> 　PLinkqueue queue = init\_linkqueue();  
> 　for(i=0;i<k;i++)\{  
> 　　in\_linkqueue(queue,a\[i\]);  
> 　\}  
> 　for(i=k;i<n;i++)\{  
> 　　a\[i-k\] = a\[i\];  
> 　\}  
> 　i = n-k;  
> 　while(!empty\_linkqueue(queue))\{  
> 　　out\_linkqueue(queue,&a\[i\]);  
> 　　i++;  
> 　\}  
> \}

**完整的程序源码如下：**

#include<stdio.h>
    #include<stdlib.h>
    
    typedef int ElementType;
    //节点结构
    typedef struct node{ 
           ElementType data;
           struct node *next;
    }Qnode,*PQnode;
    //链栈结构
    typedef struct { 
    
    	PQnode front, rear;
    }LinkQueue,*PLinkqueue;
    
    //链队初始化
    PLinkqueue init_linkqueue(){ 
    	PLinkqueue  queue = (PLinkqueue)malloc(sizeof(LinkQueue));
    	if(queue){ 
    		queue->front = NULL;
    		queue->rear = NULL;
    	}
    	return queue;
    }
    
    //判断链队为空；1空队列，0非空
    int empty_linkqueue(PLinkqueue queue){ 
    	if(queue && (queue->front==NULL) && (queue->rear==NULL)){ 
    		return 1;
    	}else{ 
    		return 0;
    	}
    }
    
    //入队列
    
    int in_linkqueue(PLinkqueue queue, ElementType x){ 
    	PQnode p = (PQnode)malloc(sizeof(Qnode));
    	if(!p){ 
    		printf("内存溢出，不能申请新的节点空间\n");
    		return 0;
    	}
    	p->data = x;
    	p->next = NULL;
    	//要先判断队列中是否有元素，两者的的入队是有一些差别的
    	if(empty_linkqueue(queue)){ 
    			queue->rear = p;
    			queue->front = p;
    	}else{ 
    		//入队的时候，在队尾插入元素
    			queue->rear->next = p;
            	queue->rear = p;
    	}
    	return 1;
    }
    
    //出队
    int out_linkqueue(PLinkqueue queue, ElementType *x){ 
    	if(empty_linkqueue(queue)){ 
    		printf("队空，无法出队\n");
    		return 0;
    	}
    
    	//出队首元素节点
    	*x = queue->front->data;
    	PQnode  temp_front= queue->front;
    
        //队首的下一个元素作为队首
    	queue->front = temp_front->next;
    	//释放出队节点
    	free(temp_front);
    	//如果队首为空，说明此时队列中没有元素节点了，则设置队尾也为空。
    	if(!queue->front){ 
    		queue->rear = NULL;
    	}
    	return 1;
    }
    
    //读取队首元素
    int getFront_linkqueue(PLinkqueue queue, ElementType *x){ 
    		if(empty_linkqueue(queue)){ 
    	     	printf("队空，无法获取队首 元素\n");
    		    return 0;
    		}
    		*x = queue->front->data;
    		return 1;
    }
    
    //销毁队列。由于使用的是链表，因此，要释放每一个链表节点的空间
    void destory_linkqueue(PLinkqueue *queue){ 
    	PQnode p;
    	if(*queue){ 
    		while((*queue)->front){ 
    			p = (*queue)->front;
    			(*queue)->front = (*queue)->front->next;
    			free(p);
    		}
    		free(*queue);
    	}
    	*queue = NULL;
    }
    
    void array_leftcircle_move(int a[], int n, int k){ 
    	int i;
        PLinkqueue  queue = init_linkqueue();
    
    	for(i=0;i<k;i++){ 
    
    		in_linkqueue(queue,a[i]);
    	}
    	for(i=k;i<n;i++){ 
    
    		a[i-k] = a[i];
    	}
    
    	i = n-k;
    	while(!empty_linkqueue(queue)){ 
    
    		out_linkqueue(queue,&a[i]);
    		i++;
    	}
    }
    
    int main(){ 
    
    	int a[10], i, k = 3;
    
    	for(i=0;i<10;i++){ 
    	
    		a[i] = i+1;
    	
    	}
    
    	array_leftcircle_move(a,10,k);
    
    	for(i=0;i<10;i++){ 
    	
    	    printf("%d ",a[i]);
    	
    	}
    	printf("\n");
    
    	return 0;
    
    }

[Link 1]: https://www.meijindong.top/posts/2450824891.html
[20200702194701893.png_pic_center]: https://img-blog.csdnimg.cn/20200702194701893.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NzU0MDYx_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200702205928319.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NzU0MDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NzU0MDYx_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200703110044872.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NzU0MDYx,size_16,color_FFFFFF,t_70#pic_center