【C++】数据结构之链队列（入队、出队、查找、翻转）_实现队列的翻转csdn c++

要求：

1. 写一个带有头结点的链队列
2. 实现入队、出队、查找、翻转功能

思路

1. 初始化队列，使front指针和rear指针同时指向一个空间
2. 入队：新建一个链节空间，把数据放入其中，rear指针指向的下一个链节为该空间。
3. 出队：删去头指针指向的链节，返回元素数据。
4. 查找：逐个比较链节内容，若存储的数据和查找元素相同，则为查找成功，返回1，反之返回0；
5. 翻转队列：用三个指针pre、pcur、pnext分别记录前一个结点、当前结点、下一个结点，让当前结点指向前一个结点，然后pre = pcur;pcur = pnext;pnext = pcur->next;不断循环，直到pnext指向空为止。最后front指针指向循环到最后的pcur，rear指针指向front指针原先指向的链节。

#include <vector>
#include <cstring>
#include <ctime>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <stdio.h>
using namespace std;

//定义链节
typedef struct  QNode
{
	int data;
	struct QNode *next;
}QNode,*QueuePtr;

//定义队列的指针类型
typedef struct LinkQueue
{
	QueuePtr front;
	QueuePtr rear;
};

//初始化队列，加上头结点
int InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear = new QNode;
	Q.front->next = NULL;
	return 1;//初始化成功返回1
}

//入队
int EnQueue(LinkQueue &Q,int e)
{
	QNode *p = new QNode;
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return 1;//入队成功返回1
}

//出队
int DeQueue(LinkQueue &Q,int &e)
{
	if (Q.front == Q.rear)
		return -1;//队列为空返回-1
	QNode *p = Q.front->next;
	Q.front->next = p->next;
	e = p->data;
	delete p;
	return 1;//出队成功返回1
}

//查找元素
int FindElem(LinkQueue &Q, int e)
{
	if (Q.front == Q.rear)
		return -1;
	QNode *p = new QNode;
	p = Q.front->next;
	while (p)
	{
		if (p->data == e)
			return 1;//成功返回1
		else
		{
			p = p->next;
		}
	}
	return 0;//失败返回0
}

//翻转链表
void OverTurnQueue(LinkQueue &Q)
{
	QNode *pre = new QNode;
	QNode *pcur = new QNode;
	QNode *pnext = new QNode;

	pre = Q.front->next;
	pcur = pre->next;
	pnext = pcur->next;
	Q.rear = pre;
	while (pnext)
	{
		pcur->next = pre;
		pre = pcur;
		pcur = pnext;
		pnext = pcur->next;
	}
	pcur->next = pre;
	Q.front->next = pcur;
	Q.rear->next = NULL;
}

//打印当前队列元素
void PrintElem(LinkQueue &Q)
{
	QNode *p = Q.front->next;
	while (p)
	{
		cout << p->data << '\t';
		p = p->next;
	}
	cout << endl;
	delete p;
}

int main()
{
	srand(time(0));
	int e;
	LinkQueue *Q = new LinkQueue();
	InitQueue(*Q);
	cout << "原始元素：" << endl;
	for (int i = 0; i < 10; i++)
	{
		e = rand()%(99 - 10 + 1) + 10;
		cout << e << '\t';
		EnQueue(*Q, e);
		
	}
	cout << endl;
	cout << "打印队列" << endl;
	PrintElem(*Q);
	OverTurnQueue(*Q);
	cout << "打印翻转队列" << endl;
	PrintElem(*Q);
	DeQueue(*Q, e);
	cout << "打印出队元素" << endl;
	cout << e << endl;
	cout << "打印队列" << endl;
	PrintElem(*Q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136