【图文并茂】c++介绍之队列_c++队列

发现更多的计算机知识，欢迎访问xiaocr的个人网站

1.1队列的定义

队列（queue）简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入操作，而在表的另一端进行删除操作

一些基础概念：

• 队尾（rear） ：进行插入的一端
• 队首（front）：进行删除的一端
• 入队（enqueue）：插入新元素
• 出队（dequeue）：删除新元素

队列是一种先进先出表（FIFO），而前面介绍过的栈是一种先进后出表。

（一个队列）

---

1.2队列抽象数据类型

如图：

---

1.3队列的顺序存储结构及其基本运算

队列中数据元素的逻辑结构呈线性关系，所以队列可以像线性表一样采用顺序存储结构进行存储，即分配一块连续的存储空间来存放队列的元素，并用两个指针来反映队列中元素变化

顺序队：采用顺序存储结构的队列

（1）声明

typedef int ElemType;
#define MaxSiaze 50
typedef struct
{
	ElemType data[MaxSiaze];
	int front, rear;	//队头与队尾指针
}SqQueue;
1
2
3
4
5
6
7

图示：

Pe-1694079903125)

(2)初始化队列

//初始化队列
void InitQueue(SqQueue*& q)
{
	q = (SqQueue*)malloc(sizeof(SqQueue));
	q->front = q->rear = -1;
}
1
2
3
4
5
6

(3)销毁队列

//销毁队列
void DestroyQueue(SqQueue*& q)
{
	free(q);
}
1
2
3
4
5

(4)判断队列是否为空

//判断队列是否为空
bool QueueEmpty(SqQueue*&q)
{
	return(q->front == q->rear);
}
1
2
3
4
5

(5)入队

bool enQueue(SqQueue*& q, ElemType e)
{
	if (q->rear == MaxSiaze - 1)	//队满上溢出
		return false;
	q->rear++;
	q->data[q->rear] = e;
	return true;
}
1
2
3
4
5
6
7
8

(6)出队

bool deQueue(SqQueue*& q, ElemType& e)
{
	if (q->front == q->rear)//队空下溢出
		return false;
	q->front++;
	e = q->data[q->front];
	return true;
}
1
2
3
4
5
6
7
8

完整代码：

#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSiaze 50
typedef struct
{
	ElemType data[MaxSiaze];
	int front, rear;	//队头与队尾指针
}SqQueue;
//初始化队列
void InitQueue(SqQueue*& q)
{
	q = (SqQueue*)malloc(sizeof(SqQueue));
	q->front = q->rear = -1;
}
//销毁队列
void DestroyQueue(SqQueue*& q)
{
	free(q);
}
//判断队列是否为空
bool QueueEmpty(SqQueue*&q)
{
	return(q->front == q->rear);
}
bool enQueue(SqQueue*& q, ElemType e)
{
	if (q->rear == MaxSiaze - 1)	//队满上溢出
		return false;
	q->rear++;
	q->data[q->rear] = e;
	return true;
}
bool deQueue(SqQueue*& q, ElemType& e)
{
	if (q->front == q->rear)//队空下溢出
		return false;
	q->front++;
	e = q->data[q->front];
	return true;
}
int main() {

	return 0;
}
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

---

1.4队列的链式存储结构及其基本运算

链队：采用链式存储结构的队列

对于单链表实现的链队，在这种链队中只允许在单链表的表头进行删除操作和在表尾进行插入操作

链队的基本知识：

• 队空的条件 q -->rear == NULL(也可以是q -->front == NULL)
• 队满的条件:不考虑
• 元素e的进队操作：新建一个结点存放元素e(由p指向它，将结点p插入作为尾结点)
• 出队操作：取出队首结点的data值并将其删除

（1）声明

typedef int ElemType;
typedef struct qnode
{
	ElemType data;	//存放元素
	struct qnode* next;//下一个结点指针
}DataNode;
typedef struct
{
	DataNode* front; //指向队首结点
	DataNode* rear; //指向队首结点
}LinkQuNode;
1
2
3
4
5
6
7
8
9
10
11

(2)销毁队列

//销毁
void DestroyQueue(LinkQueue *&q)
{
	DataNode * pre = q->front,*p;	//pre指向队首结点 
	if(pre!=NULL)
	{
		p = pre->next;				//p指向结点pre的后继结点 
		while(p!=NULL)				//p不空循环 
		{
			free(pre);				//释放pre结点 
			pre = p;				//同步后移 
			p = p->next;
		}
		free(pre);
	}
	free(q);
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（3）判断队列是否为空

bool QueueEmpty(LinkQueue *q)
{
    return (q-->rear == NULL)
}
1
2
3
4

(4)进队列

//进队列
void enQueue(LinkQuNode*& q,ElemType e)
{
	DataNode* p;
	p = (DataNode*)malloc(sizeof(DataNode));
	p->data = e;
	p->next = NULL;
	if (q->rear == NULL)//若链队为空，则新结点既是队首结点又是队尾结点
		q->front = q->rear = p;
	else
	{
		q->rear->next = p;	//将结点p链接到队尾，并将rear指向它
		q->rear = p;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(5)出队列

//出队列
bool deQueue(LinkQuNode*& q, ElemType e)
{
	DataNode* t;
	if (q->rear == NULL)	//原来队列已经为空
		return false;
	t = q->front;			//指向首结点
	if (q->front == q->rear)	//原来队列中只有一个数据结点
		q->front = q->rear = NULL;
	else
		q->front = q->front->next;
	e = t->data;
	free(t);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

完整代码：

#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct qnode
{
	ElemType data;	//存放元素
	struct qnode* next;//下一个结点指针
}DataNode;
typedef struct
{
	DataNode* front; //指向队首结点
	DataNode* rear; //指向队首结点
}LinkQuNode;
 //初始化
void InitQueue(LinkQuNode*& q)
{
	q = (LinkQuNode*)malloc(sizeof(LinkQuNode));
	q->front = q->rear = NULL;
}
//销毁
void DestroyQueue(LinkQueue *&q)
{
	DataNode * pre = q->front,*p;	//pre指向队首结点 
	if(pre!=NULL)
	{
		p = pre->next;				//p指向结点pre的后继结点 
		while(p!=NULL)				//p不空循环 
		{
			free(pre);				//释放pre结点 
			pre = p;				//同步后移 
			p = p->next;
		}
		free(pre);
	}
	free(q);
} 
//进队列
void enQueue(LinkQuNode*& q,ElemType e)
{
	DataNode* p;
	p = (DataNode*)malloc(sizeof(DataNode));
	p->data = e;
	p->next = NULL;
	if (q->rear == NULL)//若链队为空，则新结点既是队首结点又是队尾结点
		q->front = q->rear = p;
	else
	{
		q->rear->next = p;	//将结点p链接到队尾，并将rear指向它
		q->rear = p;
	}
}
//出队列
bool deQueue(LinkQuNode*& q, ElemType e)
{
	DataNode* t;
	if (q->rear == NULL)	//原来队列已经为空
		return false;
	t = q->front;			//指向首结点
	if (q->front == q->rear)	//原来队列中只有一个数据结点
		q->front = q->rear = NULL;
	else
		q->front = q->front->next;
	e = t->data;
	free(t);
	return true;
}
int main()
{

	return 0;
}
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

当然了，队列的形式多种多样，比如双端队列，循环队列等等。希望本文对你有所帮助