链式队列的实现（入队、出队、遍历和反转（翻转））（详细图文讲解反转、翻转）附C++实现

首先先讲一下链式队列的实现思想： 链式队列的实现，我们设置一个特殊的节点，这个结点的内容不是值和指向下一个结点的next、而是指向整条队列的队头和队尾的front和rear指针

我用的c++实现的（算法不分语言，任何语言都可以实现），我们先定义一个链式队列的普通节点

class QueueNode { public: char value;//值 QueueNode* next; QueueNode(char value) { this->value = value; this->next = NULL; } };

然后定义链式队列的“特殊节点”

class LinkQueue { public: QueueNode* front;//队头指针 QueueNode* rear;//队尾指针 LinkQueue(){ this->front = NULL; this->rear = NULL; } //遍历队列的函数 void outQueue(); //入队操作 void enQueue(char value); //出队操作 void DeQueue(); //将链式队列实现反转并且输出 bool fanzhuan(); }; //创建一个空队列 LinkQueue* creatQueue();

下面是对这些功能的实现 首先是入队操作： 入队的思想很简单，我们将产生一个新的普通节点，然后这个普通节点的值赋值为value，然后将这个新的节点插入到队列的尾部，然后rear后移一位。

void LinkQueue::enQueue(char value) { //入队操作 //新创建一个队列节点 QueueNode* p = new QueueNode(value); this->rear->next = p; this->rear = p; cout << "入队成功" << endl; }

然后是出队操作： 出队的思想也很简单，这个头指针的front指针所指向的就是队头元素，我们把他进行弹出即可 当然在进行出队操作的时候需要判断队列是否为空。

void LinkQueue::DeQueue() { //先判断是否有元素在队列中 if (this->front->next == this->rear->next) { cout << "出队失败！队列没有元素。" << endl; return; } QueueNode* q = new QueueNode(-1); q = this->front->next;//保存要出队的元素 this->front->next = q->next;//进行出队操作 //判断如果要出队的节点时最后一个元素时，改变一下尾指针的指向 if (this->rear == q) { this->rear = this->front; } delete[] q;//删除出队的元素 this->outQueue();//输出队列查看一下 cout << "出队成功!" << endl; }

接下来是反转（翻转）队列： 翻转（反转队列的思想）: 找到初始队列的队尾节点用一个指针cur保存他，然后从初始队列的队头节点开始，遍历地将队内元素插入到cur之后（相当于是头插法）、直到队头节点等于cur的时候停止进行插入、然后对此时的front、rear进行重新定位，这样就实现了队列的反转。具体代码实现如下：

bool LinkQueue::fanzhuan() { //将队列继续进行反转 if (this->front->next == this->rear->next) { cout << "队列元素已空，无法进行反转操作!!" << endl; return false; } /*进行反转操作，可以利用链式队列的头结点中的front指针和rear指针 我们可以创建一个新的指针来记录初始队列的队尾元素，然后，迭代的将对头元素插入到队尾元素，直到对头元素为初始队列的队尾元素时，说明初始队列已经反转成功。 */ QueueNode* cur = new QueueNode('#');//用于指向初始队列的队尾元素 cur = this->rear; QueueNode* p = this->front->next;//p指向对头元素 while (p->next != NULL && p != cur) { //还没有到队尾元素就进行反转 QueueNode* temp = p->next; p->next = this->rear->next; this->rear->next = p; p = temp;//节点往后移一位继续进行如此操作 } this->front->next = cur;//对front进行重定位 //找到队尾节点 while (p != NULL) { if (p->next == NULL) { this->rear = p;//对rear进行重定位 } p = p->next; } cout << "反转成功" << endl; return true; }

遍历操作:

void LinkQueue::outQueue() { QueueNode * p = this->front->next; while (p != NULL) { cout << p->value << " "; p = p->next; } }

还有一个是创建空队列：这个比较简单

LinkQueue* creatQueue() { LinkQueue* linkQueue = new LinkQueue(); linkQueue->front = linkQueue->rear =new QueueNode(-1); linkQueue->front->next = NULL; cout << "创建成功！" << endl; return linkQueue; }

最后是：数据结构不是很熟练，有不同看法或者是有更好的看法欢迎留言讨论！ 完整代码如下：

//QueueNode.h #pragma once #include<iostream> using namespace std; class QueueNode { public: char value;//值 QueueNode* next; QueueNode(char value) { this->value = value; this->next = NULL; } }; class LinkQueue { public: QueueNode* front;//队头指针 QueueNode* rear;//队尾指针 LinkQueue(){ this->front = NULL; this->rear = NULL; } //遍历队列的函数 void outQueue(); //入队操作 void enQueue(char value); //出队操作 void DeQueue(); //将链式队列实现反转并且输出 bool fanzhuan(); }; //创建一个空队列 LinkQueue* creatQueue(); //hanshu.cpp #include"QueueNode.h" //遍历队列的函数 void LinkQueue::outQueue() { QueueNode * p = this->front->next; while (p != NULL) { cout << p->value << " "; p = p->next; } } //创建空队列 LinkQueue* creatQueue() { LinkQueue* linkQueue = new LinkQueue(); linkQueue->front = linkQueue->rear =new QueueNode(-1); linkQueue->front->next = NULL; cout << "创建成功！" << endl; return linkQueue; } //入队操作 void LinkQueue::enQueue(char value) { //入队操作 //新创建一个队列节点 QueueNode* p = new QueueNode(value); this->rear->next = p; this->rear = p; cout << "入队成功" << endl; } //出队操作 void LinkQueue::DeQueue() { //先判断是否有元素在队列中 if (this->front->next == this->rear->next) { cout << "出队失败！队列没有元素。" << endl; return; } //然后再进行出队 QueueNode* q = new QueueNode(-1); q = this->front->next;//保存要出队的元素 this->front->next = this->front->next->next; //判断如果要出队的节点时最后一个元素时，改变一下尾指针的指向 if (this->rear == q) { this->rear = this->front; } delete[] q; this->outQueue(); cout << "出队成功!" << endl; } //反转操作 bool LinkQueue::fanzhuan() { //将队列继续进行反转 if (this->front->next == this->rear->next) { cout << "队列元素已空，无法进行反转操作!!" << endl; return false; } //this->front->1 2 3 4 5<-rear<-this /*进行反转操作，可以利用链式队列的头结点中的front指针和rear指针 我们可以创建一个新的指针来记录初始队列的队尾元素，然后，迭代的将对头元素插入到队尾元素，直到对头元素为初始队列的队尾元素时，说明初始队列已经反转成功 */ QueueNode* cur = new QueueNode('#');//用于指向初始队列的队尾元素 cur = this->rear; QueueNode* p = this->front->next;//p指向对头元素 while (p->next != NULL && p != cur) { //还没有到队尾元素就进行 QueueNode* temp = p->next; p->next = this->rear->next; this->rear->next = p; p = temp;//节点往后移一位继续进行如此操作 } this->front->next = cur; //找到队尾节点 while (p != NULL) { if (p->next == NULL) { this->rear = p; } p = p->next; } cout << "反转成功" << endl; return true; } #include<iostream> #include"QueueNode.h" using namespace std; /* 项目:实现队列的链式存储结构 功能: 1、创建空队列 2、实现入队操作 3、实现出队操作 4、队列反转 5、遍历 6、退出 时间：2019.10.27 */ int main() { int op = 0; char value = 0; LinkQueue* linkQueue = new LinkQueue(); cout << "链式队列的实现： 1、创建空队列 2、进行入队操作 3、进行出队操作 4、进行队列反转 5、查看队列（遍历） 6、退出程序" << endl; cin >> op; while (op != 6) { switch (op) { case 1: linkQueue = creatQueue(); break; case 2: cout << "输入#停止入队" << endl; while (value != '#') { cin >> value; if (value == '#') { value = '0'; break; } linkQueue->enQueue(value); } break; case 3: linkQueue->DeQueue(); break; case 4: linkQueue->fanzhuan(); break; case 5: linkQueue->outQueue(); cout << endl; break; case 6: break; } cout << "链式队列的实现： 1、创建空队列 2、进行入队操作 3、进行出队操作 4、进行队列反转 5、查看队列（遍历） 6、退出程序" << endl; cin >> op; } system("pause"); return 0; }