数据结构系列－队列的基本操作

红太狼 2022-05-29 07:16 232阅读 0赞

队列(Queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的端是队尾，允许删除的端是队头。

所以说队列是一个先进先出的线性表，相应的也有顺序存储和链式存储两种方式。

顺序存储就是用数组实现，比如有一个ｎ个元素的队列，数组下标0的一端是队头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除队头元素，后面的元素就要往前移动，对应的时间复杂度就是O(n)，性能自然不高。

为了提高出队的性能，就有了循环队列，什么是循环队列呢？就是有两个指针，front指向队头，rear指向对尾元素的下一个位置，元素出队时front往后移动，如果到了对尾则转到头部，同理入队时rear后移，如果到了对尾则转到头部，这样通过下标front出队时，就不需要移动元素了。

![Image 1][]

同时规定，当队列为空时，front和rear相等，那么队列什么时候判断为满呢？按照循环操作rear依次后移，然后再从头开始，也是出现rear和front相等时，队列满。这样跟队列空的情况就相同了，为了区分这种情况，规定数组还有一个空闲单元时，就表示队列已满，因为rear 可能在front后面，也可能循环到front前面，所以队列满的条件就变成了(rear+1)%maxsize = front ,同时队列元素个数的计算就是(rear -front+maxsize)%maxsize。

如下是循环队列的数据结构及基本操作实现：

#include "stdio.h"    
    #include "stdlib.h"   
    #include "io.h"  
    #include "math.h"  
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 11 //初始容量
    
    typedef int Status;
    typedef int QElemType;//定义数据类型
    
    //循环队列的顺序存储结构
    typedef struct{
    	QElemType data[MAXSIZE];
    	int front; //头指针
    	int rear;//尾指针，队列非空时，指向队尾元素的下一个位置
    }SqQueue;
    
    Status visit(QElemType item){
    	printf("%d",item);
    	return OK;
    }
    
    //初始化空队列
    Status InitQueue(SqQueue *sQ){
    	sQ->front =0;
    	sQ->rear =0;
    	return OK;
    }
    
    //将队列清空
    Status ClearQueue(SqQueue *Q){
    	Q->front = Q->rear =0;
    	return OK;
    }
    
    //判断队列是否为null
    Status QueueEmpty(SqQueue Q){
    	if(Q.front == Q.rear)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    //返回队列中的元素个数
    int QueueLength(SqQueue Q){
    	return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
    }
    
    //返回队头元素
    Status GetHead(SqQueue Q, QElemType *e){
    	if(Q.front == Q.rear)//是否为空队列
    		return ERROR;
    	*e = Q.data[Q.front];
    	return OK;
    }
    
    //在队尾插入元素
    Status EnQueue(SqQueue *Q, QElemType e){
    	if((Q->rear+1)%MAXSIZE == Q->front)//队列已满
    		return ERROR;
    
    	Q->data[Q->rear] =e;//插入队尾
    	Q->rear = (Q->rear +1)%MAXSIZE;//尾部指针后移，如果到最后则转到头部
    	return OK;
    }
    
    //元素出队
    Status DeQueue(SqQueue *Q, QElemType *e){
    	if(Q->front == Q->rear)//队列空
    		return ERROR;
    	*e = Q->data[Q->front];//返回队头元素
    	Q->front = (Q->front+1)%MAXSIZE;//队头指针后移，如到最后转到头部
    	return OK;
    }
    
    //遍历队列元素
    Status QueueTraverse(SqQueue Q){
    	int i = Q.front;
    	while((i+Q.front) != Q.rear){
    		visit(Q.data[i]);
    		i=(i+1)%MAXSIZE;
    	}
    	printf("\n");
    	return OK;
    }
    
    int main(){
    
    	Status j;
    	int i=0,l;
    	QElemType d;
    	SqQueue Q;
    	InitQueue(&Q);
    
    	//入队１０个元素
    	for(int i =0;i< MAXSIZE-1; i++){
    		EnQueue(&Q,i);
    	}
    	QueueTraverse(Q);
    
    	printf("依次出队:");
    	for(l=1;l<=MAXSIZE;l++)
    	{
    		DeQueue(&Q,&d);
    		printf("d= %d,",d);
    	}
    
    	return 0;	
    }

循环队列要事先申请好空间，整个过程都不能释放，而且要有固定的长度，如果长度事先无法估计，这种方式显然不够灵活；所以就引入了链式存储队列，其实就是线性表的单链表，只是它只能对尾进，队头出。并且规定队头指针指向链队列的头结点，对尾指针指向终端节点，当队列为空时，front和rear都指向头结点。

入队操作，就是在链表尾部插入结点；出队操作就是头结点的后继结点出队，然后将头结点的后继后移。如果最后除了头结点外，只剩一个元素了，就把rear也指向头结点。

![Image 1][]

数据结构及基本操作：

#include "stdio.h"    
    #include "stdlib.h"   
    #include "io.h"  
    #include "math.h"  
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 20 
    
    typedef int Status; 
    typedef int QElemType; 
    
    //结点结构
    typedef struct QNode{
    	QElemType data;
    	struct QNode *next;
    }QNode,*QueuePtr;
    
    //队列的链表结构
    typedef struct{
    	QueuePtr front;//队头
    	QueuePtr rear;//对尾
    }LinkQueue;
    
    Status visit(QElemType e)
    {
    	printf("%d ",e);
    	return OK;
    }
    
    //初始化空的队列
    Status InitQueue(LinkQueue *Q){
    	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    	if(!Q->front)
    		exit(OVERFLOW);
    	Q->front->next =NULL;
    	return OK;
    }
    
    //销毁队列
    Status DestroyQueue(LinkQueue *Q){
    	while(Q->front){
    		Q->rear=Q->front->next;//从队头开始销毁
    		free(Q->front);
    		Q->front = Q->rear;
    	}
    	return OK;
    }
    
    //清空队列，队头指针还在
    Status ClearQueue(LinkQueue *Q){
    	QueuePtr p,q;
    	Q->rear =Q->front;//跟初始状态相同，Q->rear指向头结点
    	p=Q->front->next;//开始销毁队头元素，队头，对尾依然保留
    	Q->front->next =NULL;
    	while(p){
    		q=p;
    		p=p->next;
    		free(q);
    	}	
    	return OK;
    }
    
    //队列是否空
    Status QueueEmpty(LinkQueue Q){
    	if(Q.front == Q.rear)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    //取队列长度
    int QueueLength(LinkQueue Q){
    	int i=0;
    	QueuePtr p = Q.front;
    	while(Q.rear != p){
    		i++;
    		p = p->next;
    	}
    	return i;
    }
    
    //获取队头元素
    Status GetHead(LinkQueue Q,QElemType *e){
    	QueuePtr p;
    	if(Q.front == Q.rear)//队空
    		return ERROR;
    	p=Q.front->next;
    	*e = p->data;
    	return OK;
    }
    
    //对尾插入元素
    Status EnQueue(LinkQueue *Q,QElemType e){
    	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    	if(!s)
    		exit(OVERFLOW);
    	s->data = e;
    	s->next =NULL;
    	Q->rear->next =s;//原来对尾的next指向新的元素
    	Q->rear =s;//将新元素变为对尾
    	return OK;
    }
    
    //队头元素出队
    Status DeQueue(LinkQueue *Q,QElemType *e){
    	QueuePtr p;
    	if(Q->front == Q->rear)
    		return ERROR;
    	p=Q->front->next;//ｐ指向队头元素
    	*e = p->data;
    	Q->front->next = p->next;//头结点的后继指向队头的下一个元素
    	if(Q->rear == p){//队头等于对尾了
    		Q->rear = Q->front;//对尾指向头结点
    	}	
    	free(p);
    	return OK;
    }
    
    //遍历元素
    Status QueueTraverse(LinkQueue Q){
    	QueuePtr p;
    	p=Q.front->next;
    	while(p){
    		visit(p->data);
    		p=p->next;
    	}
    	printf("\n");
    	return OK;
    }
    
    int main(){
    	int i;
    	QElemType d;
    	LinkQueue q;
    	i=InitQueue(&q);
    	
    	//入队１０个元素
    	for(int index=0;index<MAXSIZE;index++){
    		EnQueue(&q,index);
    	}
    	QueueTraverse(q);
    
    	DestroyQueue(&q);
    	printf("队列已经销毁,q.front=%p q.rear=%p\n",q.front, q.rear);
    	
    	return 0;
    }

[Image 1]: