您的位置: 首页  >  文章  >  漫谈数据结构(三)——队列

漫谈数据结构(三)——队列

分类: 文章 • 2025-05-08 13:46:28

漫谈数据结构(三)——队列

1、什么是队列

  队列是一个先进先出的线性表，它只允许在一端进行插入，在另一端进行删除操作。允许删除的称为队头，允许插入的称为队尾，分别由队头指针和队尾指针来维护队列。

  队头指针指向第一个元素。当有元素出队（删除）时，队头指针向后移动一位，指向下一个元素。

  队尾指针指向最后一个元素的之后的空指针，当有元素入队（插入）时，添加完元素后，队尾指针往后移动一位。

  如图所示：
漫谈数据结构(三)——队列

2、顺序队列的实现

  使用顺序表实现的队列被称为顺序队列。它的实现和顺序表的实现比较相似，只是只能一端删除，一端插入。如图所示，是一个顺序队列图。

漫谈数据结构(三)——队列

顺序队列的溢出：

真溢出：顺序表分配的空间已满，无法再入队。

假溢出：顺序表分配的空间未满，有出队元素，指针rear已经到达内存的最后一个空间(已经达到了最大下标)，无法再入队。

顺序队列的溢出可以用循环队列来解决，下面会讲到。

2.1 创建

typedef struct Queue{
	int front;      //队头指针 
	int rear;		//队尾指针 
	int data[MAXSIZE]; 
}SeqQueue;

//创建队列 
SeqQueue* createSeqQueue(){
	SeqQueue * queue = (SeqQueue*)malloc(sizeof(SeqQueue));
	queue->front = queue->rear = -1;
	memset(queue->data,0,MAXSIZE*sizeof(int));
	return queue;
}

2.2 判断是否为空

//判断是否为空 
int isEmpty(SeqQueue *queue){
	if(queue==NULL){
		printf("not init queue");
		return;
	}
	if(queue->front == queue->rear){
		return 1;
	}
	return 0;
}

2.3 获取长度

//获取长度 
int getLength(SeqQueue * queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	if(!isEmpty(queue)){
		return queue->rear - queue->front; 
	}
	return 0;
}

2.4 入队

//入队列
int pushQueue(SeqQueue *queue,int data){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	//已满 
	if(queue->rear == MAXSIZE -1){
		printf("the queue already full ,not push!\n");
		return;
	}
	if(!isEmpty(queue)){
		queue->data[queue->rear] = data;
		queue->rear++;
	}else{
		queue->front = queue->rear = 0;
		queue->data[queue->rear] = data;
		queue->rear++;
	}
	return 1;
}

2.5 出队

//出队列
int outQueue(SeqQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	if(!isEmpty(queue)){
		int temp = queue->data[queue->front];
		queue->front++;
		return temp;
	}else{
		printf("queue is null!");
		return;
	}
}

2.6 获取队头

//获取队头 
int getHead(SeqQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	if(!isEmpty(queue)){
		return queue->data[queue->front];
	}else{
		printf("queue is null!");
		return;
	}
}

2.7 其他

//清空队列
int clearQueue(SeqQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	if(!isEmpty(queue)){
		queue->front = queue->rear = -1;
	}
	return 1;
} 

//销毁队列 
int destoryQueue(SeqQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	free(queue);
	return 1;
} 

//打印
void print(SeqQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	printf("队头-----------队尾\n"); 
	int i;
	for(i=queue->front;i<queue->rear;i++){
		printf("%d ",queue->data[i]); 
	} 
	printf("     length = %d",getLength(queue));
	printf("\n");
}

2.8 测试

//顺序表实现队列
#include <stdio.h>
#include <stdlib.h> 
#include <string.h>

#define MAXSIZE 1024 

int main(){
	printf("Create Seq Queue：\n"); 
	SeqQueue * queue = createSeqQueue();
	printf("%d\n\n",queue);
	 
	printf("Push Seq Queue：\n"); 
	int i;
	for(i=0;i<10;i++){
		pushQueue(queue,i);
	}
	print(queue);
	printf("\n");
	
	printf("Out Seq Queue：\n"); 
	outQueue(queue);
	print(queue);
	printf("\n");
	
	printf("Get Head from Queue：\n"); 
	printf("%d\n",getHead(queue));
	printf("\n");
	
	printf("clear Queue：\n"); 
	clearQueue(queue);
	print(queue);
	
	printf("Destory Queue：\n"); 
	int flag = destoryQueue(queue);
	if(flag){
		printf("Destory Success!\n");
	}
	return 0;
}

输出结果：
漫谈数据结构(三)——队列

3、链式队列的实现

  用链表来实现的队列称为链式队列，它也是通过队头指针和队尾指针来操作结点。不用出现溢出问题。如图所示：
漫谈数据结构(三)——队列

3.1 实现

实现步骤同顺序队列，这里只给出实现代码和测试代码。

//链式队列 
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
	int data;
	struct node *next;
}Node; 

typedef struct queue{
	Node * front;
	Node * rear;
	int length;
}LinkQueue;

//创建队列 
LinkQueue* createLinkQueue(){
	LinkQueue * queue = (LinkQueue*)malloc(sizeof(LinkQueue));
	queue->front = NULL;
	queue->rear = NULL;
	queue->length = 0;
	return queue;
}

//判断是否为空 
int isEmpty(LinkQueue *queue){
	if(queue==NULL){
		printf("not init queue");
		return;
	}
	if(queue->length==0 ){
		return 1;
	}
	return 0;
}

//获取长度 
int getLength(LinkQueue * queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	if(!isEmpty(queue)){
		return queue->length; 
	}
	return 0;
}


//入队列
int pushQueue(LinkQueue *queue,int data){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	 
	 
	if(!isEmpty(queue)){
		queue->rear->next = newNode;
		queue->rear = newNode;
		queue->length++;
	}else{
		queue->front = newNode;
		queue->rear = newNode;
		queue->length++;
	}
	return 1;
} 
//出队列
Node * outQueue(LinkQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	if(!isEmpty(queue)){
		Node * node = queue->front;
		queue->front = queue->front->next;
		queue->length--;
		return node;
	}else{
		printf("queue is null!");
		return;
	}
} 

//获取队头 
Node *  getHead(LinkQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	if(!isEmpty(queue)){
		return queue->front;
	}else{
		printf("queue is null!");
		return;
	}
}

//清空队列
int clearQueue(LinkQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	if(!isEmpty(queue)){
		queue->front = NULL;
		queue->rear = NULL;
		queue->length = 0;
	}
	return 1;
} 

//销毁队列 
int destoryQueue(LinkQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	free(queue);
	return 1; 
} 

//打印
void print(LinkQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	printf("队头-----------队尾\n"); 
	int i;
	if(!isEmpty(queue)){
		Node *curNode = queue->front; 
		for(i=0;i<queue->length;i++){
			printf("%d ",curNode->data); 
			curNode = curNode->next;
		}
	}
	printf("     length = %d",getLength(queue));
	printf("\n");
}

3.2 测试

int main(){
	printf("Create Link Queue：\n"); 
	LinkQueue * queue = createLinkQueue();
	printf("%d\n\n",queue);
	 
	printf("Push Link Queue：\n"); 
	int i;
	for(i=0;i<10;i++){
		pushQueue(queue,i);
	}
	print(queue);
	printf("\n");
	
	printf("Out Link Queue：\n"); 
	outQueue(queue);
	print(queue);
	printf("\n");
	
	printf("Get Head from Link Queue：\n"); 
	printf("%d\n",getHead(queue)->data);
	printf("\n");
	
	printf("clear Queue：\n"); 
	clearQueue(queue);
	print(queue);
	
	printf("Destory Queue：\n"); 
	int flag = destoryQueue(queue);
	if(flag){
		printf("Destory Success!\n");
	}
	return 0;
}

输出结果：
漫谈数据结构(三)——队列

4、循环队列的实现

  为了解决顺序队列的假溢出问题，充分利用数组的空间，可以将队列首尾相连，构成一个循环队列。如图所示：

漫谈数据结构(三)——队列
注意点:

  1. front==rear时会出现两种情况，队列空和队列满，所以规定最后一个位置不存储数据，当rear在front前一个位置，判断队列已满。
  2. 判断空： front==rear
  3. 判断已满： (rear+1) % MAXSIZE == front
  4. 求队列长度：(rear + MAXSIZE - front) % MAXSIZE 因为rear可能会出现在front前面，导致它们相减可能为负。

由于循环队列其他操作与顺序队列基本一致，故不再贴出相同的代码，如需要完整代码，点击这里。

4.1 部分代码:

//入队列
int pushQueue(CircleQueue *queue,int data){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	
	//已满 
	int rear = queue->rear;
	int front  = queue->front;
	if((rear+1) % MAXSIZE == front){
		printf("the queue already full ,not push!\n");
		return;
	}
	if(!isEmpty(queue)){
		queue->data[queue->rear] = data;
		queue->rear = (queue->rear+1) % MAXSIZE;
	}else{
		queue->front = queue->rear = 0;
		queue->data[queue->rear] = data;
		queue->rear++;
	}
	return 1;
} 
//出队列
int outQueue(CircleQueue *queue){
	if(queue==NULL){
		printf("not init queue!\n");
		return;
	}
	if(!isEmpty(queue)){
		int temp = queue->data[queue->front];
		queue->front = (queue->front+1) % MAXSIZE;
		return temp;
	}else{
		printf("queue is null!");
		return;
	}
}

4.2 测试:

int main(){
	printf("Create Circle Queue：\n"); 
	CircleQueue * queue = createCircleQueue();
	printf("%d\n\n",queue);
	 
	printf("Push Circle Queue：\n"); 
	int i;
	for(i=0;i<10;i++){
		pushQueue(queue,i);
	}
	print(queue);
	printf("\n");
	
	printf("Out Circle Queue：\n"); 
	outQueue(queue);
	print(queue);
	printf("\n");
	
	printf("Get Head from Queue：\n"); 
	printf("%d\n",getHead(queue));
	printf("\n");
	
	printf("clear Queue：\n"); 
	clearQueue(queue);
	print(queue);
	
	printf("Destory Queue：\n"); 
	int flag = destoryQueue(queue);
	if(flag){
		printf("Destory Success!\n");
	}
	return 0;
}

输出结果：
漫谈数据结构(三)——队列

作者个人博客 https://www.you3xuan.top/ 查看原文。

源码地址: https://github.com/ThinkingXuan/DataStructure

如果对您有帮助，随手一个Star吧。

相关推荐