[数据结构与算法]队列 数据结构的实现

队列 实现的具体思路有两种：

1：第一种队列数据结构的实现，相信学过顺序表的同学对队列数据结构的实现也很容易理解，因为第一种实现方法和顺序表实现方法具体思路差不多，都是运用了数组的思想方法来实现的，但是不同的是队列的元素插入不能在随意位置插入，因为队列遵循的是（先进先出的原则）。

队列效果图的实现：

（1）跟据上图队列实现的效果图我们因该想到先定义一个结构体，结构体中的成员有指向对头的成员（front）指向对尾的成员（end）保存元素的数组（queue），跟据以上分析我们不难得到一个结构体。

代码具体实现：

//定义一个结构体来表示一个队列
typedef struct queue {
	int queue[MAXSIZE]; //存储数据数据域
	int front; //表示队列的队头
	int end;	//表示队列的队尾
}seqQueue;

（2）队列定义完成后我们应该对队列进行初始化，因为初始化时队列中还没有入队的元素，所以队头和队尾都尾0。
代码具体实现：

//初始化队列
bool initQueue(seqQueue*& queue) {
	queue->end = 0;
	queue->front = 0; //将队列的头和尾定义尾0
	return true;
}

（3）队列初始化完以后我们要做的就是将元素入队，因为队列讲究的是先进先出的原则，所以元素的插入不能像顺序表那样随便在哪个位置插入，而是要像日常生活中排队一样从开始一直往后排，跟据以上分析我们可以实现出以下代码。

代码具体实现：

//在队列中插入元素
bool insertQueue(seqQueue*& queue, int i) {
	if (!queue)return false;
	if (isOverQueue(queue)) {
		cout << "队列已经饱满!" << endl;
		return false;
	}
	queue->queue[queue->end] = i;
	queue->end++;
	return true;
}

精讲：

	queue->queue[queue->end] = i;
	queue->end++;

?因为初始化队列时queue->end=0，所以数组queue[queue->end] = queue[0]，所以我们进行队列元素入队时就是对数组进行赋值，每赋值一个元素queue->end加1，也就是queue->end++，以此可以实现循环赋值，也就是可以实现元素的不断入队。

在进行元素入队时我们应该先判断队列是否已经饱满，如果数组中入队的元素数量等于最大入队数量则不能进行入队操作。

//检验队列是否已经饱满
bool isOverQueue(seqQueue*& queue) {
	if (!queue)return false;
	if (queue->end == MAXSIZE)return true;
	return false;
}

?（4）在对队列进行元素入队以后我们，就可以进行元素的出队，出队时遵循先出的原则，也就是哪个元素先入队那个元素就先出队，出队的方式有两种。

第一种思路：第一个元素出队我们就将第二个元素的值赋值给第一个元素这样就可以实现队列元素的出队

//删除队列中的元素法一
bool deleteQueue(seqQueue*& queue) {
	if (!queue)return false;
	if (queue->front == queue->end) {
		cout << "队列已清空!" << endl;
		return false;
	}
	queue->queue[queue->front] = queue->queue[queue->front++];
	return true;
}

第二中思路：在初始化队列是我们将队列的队头赋值为0，在出队时每出队一个元素我们将对头往后移一个位置直到移到和队尾相同的位置时就不能再移动。

//删除队列中的元素法二
bool deleteQueue1(seqQueue*& queue) {
	if (!queue)return false;
	if (queue->front == queue->end) {
		cout << "队列已清空!" << endl;
		return false;
	}
	queue->front++;
	return true;
}

（4）进行以上操作后现在我们进行的是对队列元素的打印，其实打印的思路和数组元素打印的思路相似，就是遍历数组依次将数组中的元素打印出来就行。

//打印队列中的元素
void printQueue(seqQueue*& queue) {
	int i = 0;
	i += queue->front;
	if (!queue) {
		cout << "队列为空!" << endl;
		exit(1);
	}
	while (i < queue->end) {
		cout << queue->queue[i] << "  ";
		i++;
	}
}

在队列元素打印时我们因该先判断队列是否为空，如果队列为空我们就无法进行队列元素的打印，

判断队列是否为空其实非常简单，就是如果指向队头的（front）和指向队尾的（end）的状态和初始化时赋予的值相同也就是（queue->front == queue->end==0），我们就认为队列为空。

注意：在进行队列元素出队时我们都是对队头进行操作，所以在打印队列元素是我们也要从对头开始打印（假如对头指向数组第二个位置，我们就从第二个位置开始打印），所以才写出如下代码：

	int i = 0;
	i += queue->front;

（5）具体代码实现

头文件编写

#pragma once
#include<iostream>

using namespace std;

#define MAXSIZE 5

//定义一个结构体来表示一个队列
typedef struct queue {
	int queue[MAXSIZE]; //存储数据数据域
	int front; //表示队列的队头
	int end;	//表示队列的队尾
}seqQueue;

//初始化队列
bool initQueue(seqQueue*& queue) {
	queue->end = 0;
	queue->front = 0; //将队列的头和尾定义尾0
	return true;
}

//检测队列是否为空
bool isEmpty(seqQueue*& queue) {
	if (!queue)return false;
	if (queue->front == queue->end)return true;
	return false;
}

//检验队列是否已经饱满
bool isOverQueue(seqQueue*& queue) {
	if (!queue)return false;
	if (queue->end == MAXSIZE)return true;
	return false;
}

//在队列中插入元素
bool insertQueue(seqQueue*& queue, int i) {
	if (!queue)return false;

	if (isOverQueue(queue)) {
		cout << "队列已经饱满!" << endl;
		return false;
	}
	queue->queue[queue->end] = i;
	queue->end++;
	return true;
}

//删除队列中的元素法一
bool deleteQueue(seqQueue*& queue) {
	if (!queue)return false;
	if (queue->front == queue->end) {
		cout << "队列已清空!" << endl;
		return false;
	}
	queue->queue[queue->front] = queue->queue[queue->front++];
	return true;
}

//删除队列中的元素法二
bool deleteQueue1(seqQueue*& queue) {
	if (!queue)return false;
	if (queue->front == queue->end) {
		cout << "队列已清空!" << endl;
		return false;
	}
	queue->front++;
	return true;
}

//打印队列中的元素
void printQueue(seqQueue*& queue) {
	int i = 0;
	i += queue->front;
	if (!queue) {
		cout << "队列为空!" << endl;
		exit(1);
	}
	while (i < queue->end) {
		cout << queue->queue[i] << "  ";
		i++;
	}
}

?测试代码main文件的实现

#include<iostream>
#include<stdlib.h>
#include"queue.h"

using namespace std;

int main(void) {
	seqQueue* queue;
	queue = new seqQueue;

	initQueue(queue);

	for (int i = 1;i <= 8;i++) {
		insertQueue(queue, i);
	}
	printQueue(queue);
	cout << endl << endl;

	for (int i = 1;i <=8;i++) {
		deleteQueue1(queue);
	}
	printQueue(queue);
	cout << endl << endl;

	system("pause");
	return 0;
}

2：在讲述完第一种队列的实现方法以后我们进行第二种队列实现方法的讲述，也就是链表的方法实现，队列链表方法的实现比起链表的实现要复杂一点但是我们在学习了链表以后其实队列链表形式的实现也变得简单了许多，因为都是线性结构，在定义队列链表是我们应该由抽象思维转向形象思维，也就是从队列的效果图出发。

（1）跟据以往的思维我们先分析效果图链表形式队列的组成元素，由图我们不难看出链表形式的队列由队头，和队列的节点组成，所以我们在定义该队列时我们应该定义两个结构体来表示该队列，第一个就是表示队头的结构体，第二个就是表示队列节点的结构体，对队头结构体的分析，因为队头结构体中的两个成员（front）和（back）都是指向队列节点，所以在定义队头结构体时两个成员（front）和（back）的类型要和队列节点的类型相同才能指向队列节点，对队列节点结构体的分析，由图可知队列节点结构体由两个成员组成，第一个为指向下一个节点地址的（next）和保存数据的（date）组成。

具体代码实现：

typedef int TypeDate;

//用结构体定义一个链表
typedef struct linkList {
	TypeDate date;
	struct linkList* next;
}linkNode;

//用结构体定义一个队列
typedef struct queue {
	TypeDate length;
	linkNode* front;
	linkNode* back;
}seqQueue;

学过c语言的同学就知道该行代码只是一个宏定义

typedef int TypeDate;

在队头结构体中我们多加了一行代码是为了记录队列的长度

TypeDate length;

为什么要多加该行代码呢？

理解：本人是这样理解的，因为我们在获取队列长度时一般的想法是遍历一遍队列每遍历一个节点length加1，但是在遍历队列时如果队列的长度非常的长，而我们遍历队列时就要消耗cpu资源，这样程序执行的效率就很低，如果我们在入队队列元素时每入队一个元素就让length+1，这样我们就可以在入队完元素后直接就可以获得队列的长度，这样看来程序的执行效率就高了许多，这是本人对该行代码的理解，如果有什么错误请批评指正。

（2）在定义完队列后跟据以往思维就是应该对该队列进行初始化，初始化队列也很简单因为开始初始化时没有进行元素的插入，所以让对头的两个成员 都为空，length为0，为队列queue分配一块内存用来保存队列中的元素。

	//初始化队列
bool initQueue(seqQueue*& queue) {
	queue = new seqQueue;
	queue->back = queue->front = NULL;
	queue->length = 0;
	return true;
}

（3）初始化好队列后进行的操作就是进行队列元素的入队

入队的具体思路：入队时先判断队列中有没有节点，判断的理由也很简单如果有节点队头的成员front是指向第一个节点的，如果没有节点则队头成员front为空。如果只有一个节点则队头成员front，back，都指向该节点的地址，该节点的成员next赋值为空。如果队头后面有有节点则队头成员front继续指向第一个节点，而另一个成员back指向最后一个节点，上一个节点的next指向新插入节点的地址，新插入节点的成员next赋值为空，length加1。

//向队列中插入元素
bool insertQueue(seqQueue*& queue, linkNode* list) {
	if (!queue || !list)return false;
	if (!queue->front) {
		queue->front = list;
		queue->back = list;
		list->next = NULL;
		queue->length++;
	}
	else {
		queue->back->next = list;
		queue->back = list;
		list->next = NULL;
		queue->length++;
	}
	return true;
}

（4）队列元素的打印，打印的方法和链表元素打印的方法相似，都是先遍历一次队列，遍历队列时我们应该先判断该队列是否为空，判断的方法也很简单如果队头节点为空该队列就为空，应为只要该队列有节点front就必定不为空，因为front就指向第一个节点。

//打印队列中的元素
bool printQueue(seqQueue*& queue) {
	linkList* p;
	if (!queue)return false;
	if (!iSempty(queue))return false;
	p = queue->front;
	while (p) {
		cout << p->date << " :" << "ox" << p << "   ";
		p = p->next;
	}
	return true;
}

判断队列是否为空：

//判断队列是否为空
bool iSempty(seqQueue*& queue) {
	if (!queue->front) {
		cout << "队列为空";
		return false;
	}
	return true;
}

（5）删除队列中的元素，删除的方法和链表差不多，从第一个元素开始删除

//删除队列
bool deleteQueue(seqQueue*& queue) {
	if (!queue)return false;
	linkList* p;
	while (queue->front) {
		p = queue->front;
		cout << queue->front->date << " :" << "ox" << queue->front << "   ";
		queue->front = queue->front->next;
		delete p;
		queue->length--;
	}
	cout << endl;
	if (!queue->front) {
		cout << "队列以全部出队!" << endl;
	}
	return true;
}

（6）获取队头元素

//获取对头元素
bool getHeadQueue(seqQueue*& queue) {
	if (!queue)return false;
	cout << "对头元素为: " << queue->front->date << endl;
	return true;
}

（7）获取队列长度

//获得队列的长度
bool getLength(seqQueue*& queue) {
	if (!queue)return false;
	cout << "队列长度: " << queue->length << endl;
	return true;
}

经验：本人在测试代码时踩的坑（因为在打印队列元素时直接就用对头成员front而没有用一个临时变量来保存传入函数的队列queue，所以在打印到最后一个元素时queue->front 指向NULL，而删除元素时里面判断条件为while (queue->front)，所以直接就跳出循环没有进行元素的删除。如果在打印队列元素时用一个linkList* p来保存queue->front，后面直接对p进行操作就不会影响queue->front的指向。在删除队列元素的函数中传入函数的队列queue中queue->front依然指向第一个节点的地址，这样就不会影响以后函数的使用）总结（发生以上情况的原因时两个结构体中的成员都为全局成员，后面函数对该成员的使用都影响该成员的值）。以上这段文字看不懂没关系这只是本人为了记录以下写的心得。

（8）具体代码实现

头文件编写：

#pragma once
#include<iostream>

using namespace std;

typedef int TypeDate;

//用结构体定义一个链表
typedef struct linkList {
	TypeDate date;
	struct linkList* next;
}linkNode;

//用结构体定义一个队列
typedef struct queue {
	TypeDate length;
	linkNode* front;
	linkNode* back;
}seqQueue;

//初始化队列
bool initQueue(seqQueue*& queue) {
	queue = new seqQueue;
	queue->back = queue->front = NULL;
	queue->length = 0;
	return true;
}

//向队列中插入元素
bool insertQueue(seqQueue*& queue, linkNode* list) {
	if (!queue || !list)return false;
	if (!queue->front) {
		queue->front = list;
		queue->back = list;
		list->next = NULL;
		queue->length++;
	}
	else {
		queue->back->next = list;
		queue->back = list;
		list->next = NULL;
		queue->length++;
	}
	return true;
}

//判断队列是否为空
bool iSempty(seqQueue*& queue) {
	if (!queue->front) {
		cout << "队列为空";
		return false;
	}
	return true;
}

//打印队列中的元素
bool printQueue(seqQueue*& queue) {
	linkList* p;
	if (!queue)return false;
	if (!iSempty(queue))return false;
	p = queue->front;
	while (p) {
		cout << p->date << " :" << "ox" << p << "   ";
		p = p->next;
	}
	return true;
}

//删除队列
bool deleteQueue(seqQueue*& queue) {
	if (!queue)return false;
	linkList* p;
	while (queue->front) {
		p = queue->front;
		cout << queue->front->date << " :" << "ox" << queue->front << "   ";
		queue->front = queue->front->next;
		delete p;
		queue->length--;
	}
	cout << endl;
	if (!queue->front) {
		cout << "队列以全部出队!" << endl;
	}
	return true;
}

//获得队列的长度
bool getLength(seqQueue*& queue) {
	if (!queue)return false;
	cout << "队列长度: " << queue->length << endl;
	return true;
}

//获取对头元素
bool getHeadQueue(seqQueue*& queue) {
	if (!queue)return false;
	cout << "对头元素为: " << queue->front->date << endl;
	return true;
}

测试代码main文件实现：

#include<iostream>
#include<stdlib.h>
#include"queue.h"

int main(void) {
	linkList* list;
	seqQueue* queue;

	//初始化队列
	initQueue(queue);

	//在队列中插入元素
	for (int i = 1;i <= 5;i++) {
		list = new linkList;
		list->date = i;
		insertQueue(queue, list);
	}
	printQueue(queue);
	cout << endl;

	//获取队列长度
	getLength(queue);

	//获取对头元素
	getHeadQueue(queue);

	//将队列中的元素出对
	deleteQueue(queue);
	cout << endl;

	//获取队列长度
	getLength(queue);

	system("pause");
	return 0;
}

有什么错误请指正