北邮22信通一枚~   

跟随课程进度每周更新数据结构与算法的代码和文章 

持续关注作者  解锁更多邮苑信通专属代码~

上一篇文章：

北邮22信通：（10）第三章 3.2栈的实现_青山如墨雨如画的博客-CSDN博客

下一篇文章：

***鲜花***

有问题评论区留言哦 一起讨论

***********

目录

3.3.0无注释源代码

循环队列：

链队列：

3.3.1循环队列的实现

几点解释

代码部分

运行结果

3.3.2链队列的实现

几点解释

代码部分

运行结果

3.3.0无注释源代码

循环队列：

//循环队列书上代码
#include <iostream>
using namespace std;
const int queuesize = 1000;
class student
{
private:int ID;string name;
public:student(){this->ID = 0;this->name = "INVALID";}student(int ID, string name){this->ID = ID;this->name = name;}void print(){cout << "this->ID=" << this->ID << " ";cout << "this->name=" << this->name << endl;}friend ostream& operator <<(ostream& output, student& stu){output << "ID=" << stu.ID << " ";output << "name=" << stu.name << endl;return output;}
};template<class temp>
class circlequeue
{
private:temp data[queuesize];int front;int rear;
public:circlequeue() { this->front = this->rear = 0; }void enqueue(temp x);temp dequeue();temp getfront();int getlength();bool empty(){return this->front == this->rear ? true : false;}
};template<class temp>
void circlequeue<temp>::enqueue(temp x)
{if ((this->rear + 1) % queuesize == this->front) throw "overflow";this->rear = (this->rear + 1) % queuesize;this->data[this->rear] = x;
}template<class temp>
temp circlequeue<temp>::dequeue()
{if (this->rear == this->front)throw"underflow";this->front = (this->front + 1) % queuesize;return this->data[this->front];
}template<class temp>
temp circlequeue<temp>::getfront()
{if (this->rear == this->front)throw"underflow";return this->data[(this->front + 1) % queuesize];
}template<class temp>
int circlequeue<temp>::getlength()
{return (this->rear - this->front + queuesize);
}int main()
{try{system("color 0A");student stu[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"liu"} };circlequeue<student> cq;for (int i = 0; i < 5; i++)cq.enqueue(stu[i]);student tempstu;cout << "now let's check if the queue is empty……" << endl;cout << cq.empty() << endl;for (int i = 0; i < 5; i++){tempstu = cq.getfront();cout << "before dequeue, the front data of the circlequeue is " << tempstu;cout << "before dequeue, the length of the circlequeue is " << cq.getlength() << endl;cout << "now we start to run the function dequeue……" << endl;cq.dequeue();cout << "deleted……" << endl << endl;}cout << "now let's recheck if the queue is empty……" << endl;cout << cq.empty();}catch (const char* ss){cout << ss << endl;}return 0;}

链队列：

#include <iostream>
using namespace std;
const int queuesize = 1000;
class student
{
private:int ID;string name;
public:student(){this->ID = 0;this->name = "INVALID";}student(int ID, string name){this->ID = ID;this->name = name;}void print(){cout << "this->ID=" << this->ID << " ";cout << "this->name=" << this->name << endl;}friend ostream& operator <<(ostream& output, student& stu){output << "ID=" << stu.ID << " ";output << "name=" << stu.name << endl;return output;}
};template<class temp>
struct node
{temp data;node<temp>* next;
};template <class temp>
class linkqueue
{
private:node<temp>* front;node<temp>* rear;
public:linkqueue();~linkqueue();void enqueue(temp x);temp dequeue();temp getfront();int getlength();bool empty(){return (this->front == this->rear) ? true : false;}
};template<class temp>
linkqueue<temp>::linkqueue()
{this->front = this->rear = new node <temp>;this->front->next = NULL;
}template<class temp>
void linkqueue<temp>::enqueue(temp x)
{this->rear->next = new node<temp>;this->rear = this->rear->next;this->rear->data = x;this->rear->next = NULL;
}template<class temp>
temp linkqueue<temp>::dequeue()
{node<temp>* p = this->front->next;if (!p)throw"underflow";/*如果为空队列，抛出异常*/this->front->next = p->next;temp x = p->data;delete p;if (!(this->front->next))this->rear = this->front;return x;
}template<class temp>
temp linkqueue<temp>::getfront()
{if (!this->front->next)throw"overflow";return this->front->next->data;
}template<class temp>
linkqueue<temp>::~linkqueue()
{while (this->front != NULL){this->rear = this->front->next;delete this->front;this->front = this->rear;}
}template<class temp>
int linkqueue<temp>::getlength()
{node<temp>* p = this->front;int cnt = 0;while (p != this->rear){cnt++;p = p->next;}return cnt;
}int main()
{try{system("color 0A");student stu[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"liu"} };linkqueue<student> lq;for (int i = 0; i < 5; i++)lq.enqueue(stu[i]);student tempstu;cout << "now let's check if the queue is empty……" << endl;cout << lq.empty() << endl;for (int i = 0; i < 5; i++){tempstu = lq.getfront();cout << "before dequeue, the front data of the linkqueue is " << tempstu;cout << "before dequeue, the length of the linkqueue is " << lq.getlength() << endl;cout << "now we start to run the function dequeue……" << endl;lq.dequeue();cout << "deleted……" << endl << endl;}cout << "now let's recheck if the queue is empty……" << endl;cout << lq.empty();}catch (const char*ss){cout << ss << endl;}return 0;}

3.3.1循环队列的实现

几点解释

1.为了实现循环队列更加方便，在此规定front位置永不存储队列元素，所以当队列满时，其长度实际为数组长度减1；

2.根据队列的性质，入队操作是对rear的移动，出队操作是对front的移动；

3.当front==next时，队列为空队列；

4.关于enqueue函数判断上溢的一点解释：

template<class temp>
void circlequeue<temp>::enqueue(temp x)
{if ((this->rear + 1) % queuesize == this->front) throw "overflow";this->rear = (this->rear + 1) % queuesize;this->data[this->rear] = x;
}

解释一下overflow的判断条件：
什么叫“上溢”：
顾名思义，就是向上溢出，本来队列已经满了，现在再从队尾插入一个元素，
队头那个元素就被挤死了。想出去，我没执行出队函数；不出去，队尾又补充进来一个元素。
这种情况就叫做上溢。
循环队列也会面对一模一样的问题。
下面解释if ((this->rear + 1) % queuesize == this->front) throw "overflow";
假设循环队列长度为5，第一个位置储存front，最后一个位置储存rear。这个长度为5的队列里，有效数据（即除去front）有4个。现在我执行入队操作，rear往后移一位，(rear+1)%queuesize=1=front，那不就被挤住了嘛。
所以称作上溢。 

5.解释一下dequeue下溢的判断条件：

template<class temp>
temp circlequeue<temp>::dequeue()
{if (this->rear == this->front)throw"underflow";this->front = (this->front + 1) % queuesize;return this->data[this->front];
}

同理我们来理解一下this->rear==this->front这个判断条件：
那就是队头和队尾相等，那就是空队列。空队列不能执行dequeue函数，
所以称之为下溢。 

代码部分

//循环队列书上代码
#include <iostream>
using namespace std;
const int queuesize = 1000;
class student
{
private:int ID;string name;
public:student(){this->ID = 0;this->name = "INVALID";}student(int ID, string name){this->ID = ID;this->name = name;}void print(){cout << "this->ID=" << this->ID << " ";cout << "this->name=" << this->name << endl;}friend ostream& operator <<(ostream& output, student& stu){output << "ID=" << stu.ID << " ";output << "name=" << stu.name << endl;return output;}
};template<class temp>
class circlequeue
{
private:temp data[queuesize];int front;int rear;
public:circlequeue() { this->front = this->rear = 0; }void enqueue(temp x);temp dequeue();temp getfront();int getlength();bool empty(){return this->front == this->rear ? true : false;}
};template<class temp>
void circlequeue<temp>::enqueue(temp x)
{if ((this->rear + 1) % queuesize == this->front) throw "overflow";this->rear = (this->rear + 1) % queuesize;this->data[this->rear] = x;
}
/*表扬这个取模运算，非常精彩*/
/*
解释一下overflow的判断条件：
什么叫“上溢”：
顾名思义，就是向上溢出，本来队列已经满了，现在再从队尾插入一个元素，
队头那个元素就被挤死了。想出去，我没执行出队函数；不出去，队尾又补充进来一个元素。
这种情况就叫做上溢。
循环队列也会面对一模一样的问题。
下面解释if ((this->rear + 1) % queuesize == this->front) throw "overflow";
假设循环队列长度为5，第一个位置储存front，最后一个位置储存rear。这个长度为5的队列里，有效数据（即除去front）有4个
现在我执行入队操作，rear往后移一位，(rear+1)%queuesize=1=front，那不就被挤住了嘛。
所以称作上溢。
*/template<class temp>
temp circlequeue<temp>::dequeue()
{if (this->rear == this->front)throw"underflow";this->front = (this->front + 1) % queuesize;return this->data[this->front];
}
/*
同理我们来理解一下this->rear==this->front这个判断条件：
那就是队头和队尾相等，那就是空队列。空队列不能执行dequeue函数，
所以称之为下溢。
*/template<class temp>
temp circlequeue<temp>::getfront()
{if (this->rear == this->front)throw"underflow";return this->data[(this->front + 1) % queuesize];
}template<class temp>
int circlequeue<temp>::getlength()
{return (this->rear - this->front + queuesize);
}int main()
{try{system("color 0A");student stu[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"liu"} };circlequeue<student> cq;for (int i = 0; i < 5; i++)cq.enqueue(stu[i]);student tempstu;cout << "now let's check if the queue is empty……" << endl;cout << cq.empty() << endl;for (int i = 0; i < 5; i++){tempstu = cq.getfront();cout << "before dequeue, the front data of the circlequeue is " << tempstu;cout << "before dequeue, the length of the circlequeue is " << cq.getlength() << endl;cout << "now we start to run the function dequeue……" << endl;cq.dequeue();cout << "deleted……" << endl << endl;}cout << "now let's recheck if the queue is empty……" << endl;cout << cq.empty();}catch (const char* ss){cout << ss << endl;}return 0;}

运行结果

3.3.2链队列的实现

几点解释

1.为了实现链队列更加方便，在此规定对头指针所指位置永不存储队列元素，所以当队列满时，其长度实际为数组长度减1；

2.根据队列的性质，入队操作是对尾指针的操作，出队操作是对头指针的操作；

3.当对头指针和队尾指针指向头一个位置时，队列为空队列；

4.说说默认构造函数的一点心得：

template<class temp>
linkqueue<temp>::linkqueue()
{this->front = this->rear = new node <temp>;this->front->next = NULL;
}

说明：从默认无参构造函数我们可以看出：
当队列为空队列时，头指针和尾指针指向同一个位置；
从而我们可以反推出来：
当头指针和尾指针指向同一个位置时，
循环队列为空队列。
两者互为充要条件。

5.浅谈入队函数enqueue

template<class temp>
void linkqueue<temp>::enqueue(temp x)
{this->rear->next = new node<temp>;this->rear = this->rear->next;this->rear->data = x;this->rear->next = NULL;
}

说明：根据队列的结构特点，
插入元素应该从队尾插入。
所以书写enqueue函数时，
我们是在对尾指针进行操作的。

6.说说dequeue函数中判断队列是否为空这条语句是啥意思：

template<class temp>
temp linkqueue<temp>::dequeue()
{node<temp>* p = this->front->next;if (!p)throw"underflow";/*如果为空队列，抛出异常*/this->front->next = p->next;temp x = p->data;delete p;if (!(this->front->next))this->rear = this->front;return x;
}

 解释一下if (!p)throw "underflow" ;这个语句为什么表示的是“如果队列为空队列，抛出异常”:
首先，如果一个队列为空队列，那么这个队列的头指针和尾指针指向同一个位置，头指针的下一个指针指向NULL；其次，运算符！表示“非”运算，返回值类型为布尔型；综上，如果指针p，也就是this->front->next==NULL,那么  !p  就等价于!this->front->next，就等价于!NULL，我们知道NULL是假值，那么!NULL就是真值，表示执行语句。翻译过来就是如果这件事情（也就是this->front->next==NULL）是真的，那我们执行throw "underflow"语句；

*********

代码部分

//循环队列书上代码
//在此规定对头指针所指位置永不存储队列元素
//当队列满时，其长度实际为数组长度减1
//当队头指针和队尾指针指向同一个位置时，队列为空队列
#include <iostream>
using namespace std;
const int queuesize = 1000;
class student
{
private:int ID;string name;
public:student(){this->ID = 0;this->name = "INVALID";}student(int ID, string name){this->ID = ID;this->name = name;}void print(){cout << "this->ID=" << this->ID << " ";cout << "this->name=" << this->name << endl;}friend ostream& operator <<(ostream& output, student& stu){output << "ID=" << stu.ID << " ";output << "name=" << stu.name << endl;return output;}
};template<class temp>
struct node
{temp data;node<temp>* next;
};template <class temp>
class linkqueue
{
private:node<temp>* front;node<temp>* rear;
public:linkqueue();~linkqueue();void enqueue(temp x);temp dequeue();temp getfront();int getlength();bool empty(){return (this->front == this->rear) ? true : false;}
};template<class temp>
linkqueue<temp>::linkqueue()
{this->front = this->rear = new node <temp>;this->front->next = NULL;
}
/*
说明：从默认无参构造函数我们可以看出：
当队列为空队列时，头指针和尾指针指向同一个位置；
从而我们可以反推出来：
当头指针和尾指针指向同一个位置时，
循环队列为空队列。
两者互为充要条件。
*/template<class temp>
void linkqueue<temp>::enqueue(temp x)
{this->rear->next = new node<temp>;this->rear = this->rear->next;this->rear->data = x;this->rear->next = NULL;
}
/*
说明：根据队列的结构特点，
插入元素应该从队尾插入。
所以书写enqueue函数时，
我们是在对尾指针进行操作的。
*/template<class temp>
temp linkqueue<temp>::dequeue()
{node<temp>* p = this->front->next;if (!p)throw"underflow";/*如果为空队列，抛出异常*/this->front->next = p->next;temp x = p->data;delete p;if (!(this->front->next))this->rear = this->front;return x;
}
/*
解释一下if (!p)throw"underflow";
这个语句为什么表示的是“如果队列为空队列，抛出异常”:
首先，如果一个队列为空队列，那么这个队列的头指针和尾指针指向同一个位置，
头指针的下一个指针指向NULL；
其次，运算符！表示“非”运算，返回值类型为布尔型；
综上，如果指针p，也就是this->front->next==NULL,
那么!p就等价于!this->front->next,就等价于!NULL，
我们知道NULL是假值，那么!NULL就是真值，表示执行语句
翻译过来就是如果这件事情（也就是this->front->next==NULL）是真的，
那我们执行throw "underflow"语句；
*/template<class temp>
temp linkqueue<temp>::getfront()
{if (!this->front->next)throw"overflow";return this->front->next->data;
}template<class temp>
linkqueue<temp>::~linkqueue()
{while (this->front != NULL){this->rear = this->front->next;delete this->front;this->front = this->rear;}
}template<class temp>
int linkqueue<temp>::getlength()
{node<temp>* p = this->front;int cnt = 0;while (p != this->rear){cnt++;p = p->next;}return cnt;
}int main()
{try{system("color 0A");student stu[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"liu"} };linkqueue<student> lq;for (int i = 0; i < 5; i++)lq.enqueue(stu[i]);student tempstu;cout << "now let's check if the queue is empty……" << endl;cout << lq.empty() << endl;for (int i = 0; i < 5; i++){tempstu = lq.getfront();cout << "before dequeue, the front data of the linkqueue is " << tempstu;cout << "before dequeue, the length of the linkqueue is " << lq.getlength() << endl;cout << "now we start to run the function dequeue……" << endl;lq.dequeue();cout << "deleted……" << endl << endl;}cout << "now let's recheck if the queue is empty……" << endl;cout << lq.empty();}catch (const char*ss){cout << ss << endl;}return 0;}

运行结果