【数据结构---队列】一篇文章搞懂队列的设计与相关操作

谁践踏了优雅 2023-03-03 11:24 64阅读 0赞

# 队列 #

> **队列**（queue）是一种**先进先出**（first in first out）的线性表。  
> 它只允许在一端进行插入，而在另一端进行删除元素  
> 允许插入的一端叫做**队尾**（rear），允许删除的一端叫做**对头**（front）  
> 队列的实现有两种：①顺序队列 ②链式队列  
> 例如：我们在排队时，就可以看做一个队列

队列示意图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]

## 顺序队列 ##

### 一、概念 ###

> 顺序队列存储数据采用的是动态分配的一块额定的空间

### 二、图解 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 1]

### 三、参考源码 ###

> 头文件

#include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>

> 顺序队列结构定义

//定义常量
    #define DEFAULT_QUEUE_CAPACITY 8
    #define DEFAULT_CAPACITY_GROW_MULTIPLE 2
    typedef int ET;
    
    //顺序队列
    typedef struct SeqQueue
    { 
    	ET *base;			//存储空间
    	size_t	capacity;	//当前最大容量
    	size_t	head;		//头结点索引
    	size_t tail;		//尾节点索引
    }SeqQueue;

> 方法声明

void SeqQueueInitial(SeqQueue *psq, size_t cap);		//初始化顺序队列
    bool IsEmpty(SeqQueue *psq);							//判断队列是否为空
    bool IsFull(SeqQueue *psq);								//判断队列是否为满
    void CapacityGrow(SeqQueue *psq);						//队列扩容
    void SeqQueueIn(SeqQueue *psq, ET x);					//入队
    void SeqQueueOut(SeqQueue *psq);						//出队
    ET SeqQueueGetHead(SeqQueue *psq);						//获取头元素
    ET SeqQueueGetTail(SeqQueue *psq);						//获取尾元素
    size_t SeqQueueGetLength(SeqQueue *psq);				//获取当前队列长度
    void SeqQueueShowData(SeqQueue *psq);					//展示队列中的数据
    void SeqQueueDestroy(SeqQueue *psq);					//摧毁队列结构

> 方法定义

void SeqQueueInitial(SeqQueue *psq, size_t cap){ 
    	assert(psq != NULL);
    	psq->capacity = cap > DEFAULT_QUEUE_CAPACITY ? cap : DEFAULT_QUEUE_CAPACITY;
    	psq->head = psq->tail = 0;
    	psq->base = (ET*)malloc(sizeof(ET)* psq->capacity);
    }
    bool IsEmpty(SeqQueue *psq){ 
    	assert(psq != NULL);
    	if (psq->tail == 0){ 
    		return true;
    	}
    	return false;
    }
    bool IsFull(SeqQueue *psq){ 
    	assert(psq != NULL);
    	if (psq->tail == psq->capacity){ 
    		return true;
    	}
    	return false;
    }
    void CapacityGrow(SeqQueue *psq){ 
    	assert(psq != NULL);
    	psq->capacity *= DEFAULT_CAPACITY_GROW_MULTIPLE;
    	ET* new_base = (ET*)realloc(psq->base, psq->capacity);
    	psq->base = new_base;
    }
    void SeqQueueIn(SeqQueue *psq, ET x){ 
    	assert(psq != NULL);
    	if (IsFull(psq)){ 
    		CapacityGrow(psq);
    	}
    	psq->base[psq->tail++] = x;
    }
    void SeqQueueOut(SeqQueue *psq){ 
    	assert(psq != NULL);
    	if (psq->tail == psq->head){ 	//空队列 
    		return;
    	}
    	else{ 
    		if (psq->tail == 1){ 
    			psq->tail--;
    		}
    		else{ 
    			int i = psq->head;
    			for (; i < psq->tail - 1; i++){ 
    				psq->base[i] = psq->base[i + 1];
    			}
    			psq->tail--;
    		}
    	}
    }
    ET SeqQueueGetHead(SeqQueue *psq){ 
    	assert(psq != NULL);
    	if (IsEmpty(psq)){ 
    		return;
    	}
    	return psq->base[psq->head];
    }
    ET SeqQueueGetTail(SeqQueue *psq){ 
    	assert(psq != NULL);
    	if (IsEmpty(psq)){ 
    		return;
    	}
    	return psq->base[psq->tail - 1];
    }
    size_t SeqQueueGetLength(SeqQueue *psq){ 
    	assert(psq != NULL);
    	return psq->tail;
    }
    void SeqQueueShowData(SeqQueue *psq){ 
    	assert(psq != NULL);
    	int i = psq->head;
    	printf("Head <- ");
    	for (; i < psq->tail; i++){ 
    		printf("%d <- ", psq->base[i]);
    	}
    	printf("Tail.\n");
    }
    void SeqQueueDestroy(SeqQueue *psq){ 
    	assert(psq != NULL);
    	psq->head = psq->tail = psq->capacity = 0;
    	free(psq->base);
    	psq = NULL;
    }

## 链式队列 ##

### 一、概念 ###

> 链式队列中存储数据是用动态分配的结点来存储的，这个结点由两部分组成：数据域和指针域，通过指针将结点与结点之间相连

### 二、图解 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 2]

### 三、参考源码 ###

> 头文件

#include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>

> 链式队列结构定义

//定义常量
    typedef int ET;
    //链队列
    typedef struct Node
    { 
    	ET data;
    	Node* next;
    }Node;
    typedef struct LinkedQueue
    { 
    	Node* head;
    	Node* tail;
    }LinkedQueue;

> 方法声明

Node* CreateNode(ET val);						//创建并返回一个结点
    bool IsEmpty(LinkedQueue *pq);					//判断队列是否为空
    void LinkedQueueInit(LinkedQueue *pq);			//初始化队列
    void LinkedQueueIn(LinkedQueue *pq, ET val);	//入队
    void LinkedQueueOut(LinkedQueue *pq);			//出队
    ET LinkedQueueGetFront(LinkedQueue *pq);		//获取头结点
    int LinkedQueueSize(LinkedQueue *pq);			//获取队列长度
    void LinkedQueueShow(LinkedQueue *pq);			//展示队列中的数据
    void LinkedQueueDestroy(LinkedQueue *pq);		//摧毁队列结构

> 方法实现

Node* CreateNode(ET val){ 
    	Node* s = (Node*)malloc(sizeof(Node));
    	assert(s != NULL);
    	s->data = val;
    	s->next = NULL;
    	return s;
    }
    bool IsEmpty(LinkedQueue *pq){ 
    	assert(pq != NULL);
    	return pq->head == NULL;
    }
    void LinkedQueueInit(LinkedQueue *pq){ 
    	assert(pq != NULL);
    	pq->head = pq->tail = NULL;
    }
    void LinkedQueueIn(LinkedQueue *pq, ET val){ 
    	assert(pq != NULL);
    	Node* s = CreateNode(val);
    	if (pq->head == NULL){ 	//空队列 
    		pq->head = pq->tail = s;
    	}
    	else{ 	//队列非空 
    		pq->tail->next = s;
    		pq->tail = s;
    	}
    }
    void LinkedQueueOut(LinkedQueue *pq){ 
    	assert(pq != NULL);
    	Node* s = pq->head;
    	if (pq->head == NULL){ 	//空队列 
    		return;
    	}
    	else{ 	//队列非空 
    		if (pq->head->next == pq->tail){ 	//只有一个元素 
    			pq->head = pq->tail = NULL;
    			free(s);
    		}
    		else{ 	//多个元素 
    			pq->head = s->next;
    			free(s);
    		}
    	}
    }
    ET LinkedQueueGetFront(LinkedQueue *pq){ 
    	assert(pq != NULL);
    	if (pq->head == NULL)	//空队列 
    		return -1;
    	return pq->tail->data;
    }
    int LinkedQueueSize(LinkedQueue *pq){ 
    	assert(pq != NULL);
    	size_t len = 0;
    	if (pq->head == NULL){ 
    		return len;
    	}
    	else{ 
    		Node* p = pq->head;
    		while (p != NULL){ 
    			p = p->next;
    			len++;
    		}
    	}
    	return len;
    }
    void LinkedQueueShow(LinkedQueue *pq){ 
    	assert(pq != NULL);
    	Node* p = pq->head;
    	printf("Head->");
    	while (p != NULL){ 
    		printf("%d->", p->data);
    		p = p->next;
    	}
    	printf("Tail.\n");
    }
    void LinkedQueueDestroy(LinkedQueue *pq){ 
    	assert(pq != NULL);
    	if (pq->head == NULL){ 
    		return;
    	}
    	else{ 
    		Node* p = pq->head;
    		Node* q = pq->head;
    		while (q != NULL){ 
    			q = q->next;
    			free(p);
    			p = q;
    		}
    		pq->head = pq->tail = NULL;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]: /images/20230208/724a54ec3b92431fb416934f04670178.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 1]: /images/20230208/3435f1d705294b11abbc7d85e44ac6ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 2]: /images/20230208/3e024e3050e8429d84cb463d9360ffc7.png