队列的定义与部分习题讲解

队列

一、队列的定义

​ 队列，简称队，如下图所示。它是一种运算受限的线性表，其仅允许在表的一端进行插入，而在表的另一端进行删除，通常把进行插入的一端称作队尾，进行删除的一端称作队首或对头。向队列插入新元素称作进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。

二、队列的特点

​ 队列的主要特点是“ 先进先出 ”，即先进队的元素先出队，所以队列也称先进先出表。

三、队列的存储结构

​ 队列有两种主要的存储结构，即顺序队和链队，前者采用顺序存储结构实现队列，后者采用链式存储结构实现队列。

1.顺序队

​ 顺序队是分配一块连续的存储区域存放队列中的元素，并用两个变量分别指向队首和队尾。

1.1顺序队的结构示意图如下

1.2顺序队列的存储结构

#define MAXSIZE 10
typedef int ElemType;
typedef struct
{
	ElemType data[MAXSIZE];		//数据存储
	int front,rear;				//队首和队尾指针
}SqQueue,*SQ;				//声明顺序队类型
1
2
3
4
5
6
7

顺序队列有循环和非循环两种存储方式

1.3非循环队列的要素

	队空条件：qu.rear==qu.front
	队满条件：qu.rear=MAXSIZE-1
	元素x进队（需要移动队尾指针）：qu.rear++;qu.data[qu.rear]=x
	出队x(需移动队首指针)：qu.front++;x=qu.data[qu.front];
1
2
3
4

1.3.1循环队列的要素

队空条件：qu.rear==qu.front
队满条件：（qu.rear+1）%MAXSIZE=qu.front;
元素x进队（需要移动队尾指针）：qu.rear=(qu.rear+1)%MAXSIZE;qu.data[qu.rear]=x
出队x(需移动队首指针)：qu.front=(qu.front+1)%MAXSIZE;x=qu.data[qu.front];
1
2
3
4

2.链队

2.1链队的结构示意图如下

2.2链队的存储结构

typedef int ElemType;
//链队中数据节点的类型QNode声明
typedef struct qnode
{
	ElemType data;
	struct qnode* next;
}QNode;			//声明链队数据节点类型

//链队节点的类型LiQueue声明
typedef struct
{
	QNode* front;		//队头指针
	QNode* rear;		//队尾指针
}LiQueue,*LQU;			//声明链队节点类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.3链队的要素

队空条件：lqu->rear==NULL 或 lqu->front==NULL
队满条件：一般不考虑队满的情况
节点p进队操作：lqu-rear->next=p;lqu->rear=p;
节点p出队操作：p=lqu->front;lqu->front=p->next;x=p->data;free(p);
1
2
3
4

四、队列的基本运算

//初始化队列
void InitQueue(SqQueue& qu);

//判断是否为空
int QueueEmpty(SqQueue qu);

//进队
int EnQueue(SqQueue& qu, ElemType x);

//出队
int DeQueue(SqQueue& qu, ElemType& x);
1
2
3
4
5
6
7
8
9
10
11

五、顺序队的代码实现

1.代码的实现

main.cpp

#include"SqQueue.h"

void test1()
{
	ElemType x,k;
	SqQueue qu;
	InitQueue(qu);
	EnQueue(qu, 1);
	EnQueue(qu, 2);
	EnQueue(qu, 3);
}

int main()
{
	test1();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

SqQueue.cpp

#include"SqQueue.h"

//初始化队列
void InitQueue(SqQueue& qu)
{
	qu.front = qu.rear = 0;
}

//判断是否为空
int QueueEmpty(SqQueue qu)
{
	return (qu.front == qu.rear);
}

//进队
int EnQueue(SqQueue& qu, ElemType x)
{
	非循环队列的定义
	//if (qu.rear = MAXSIZE - 1)
	//	return 0;
	//qu.rear++;
	//qu.data[qu.rear] = x;
	//return 1;

	if ((qu.rear + 1) % MAXSIZE == qu.front)	//队满
		return 0;
	qu.rear = (qu.rear + 1) % MAXSIZE; 
	qu.data[qu.rear] = x;		//元素x进队
	return 1;
}

//出队
int DeQueue(SqQueue& qu, ElemType& x)
{
	if (qu.rear == qu.front)		//队空
		return 0;
	qu.front = (qu.front + 1) % MAXSIZE;
	x = qu.data[qu.front];		//元素出队
	return 1;
}
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

SqQueue.h

#pragma once
#include<iostream>
#include<stdlib.h>
using namespace std;

#define MAXSIZE 10
typedef int ElemType;

//顺序栈的定义
/*
		栈空条件：st.top==-1
		栈满条件：st.top==MAXSIZE-1
		元素进栈操作：st.top++;st.data[st.top]=x;
		出栈操作：x=st.data[st.top];st.top--;
*/
typedef struct
{
	ElemType data[MAXSIZE];		//存放栈中元素
	int top;					//栈顶指针
}SqStack;		//声明顺序栈类型

//顺序队的定义
/*
			非循环队列的要素

	队空条件：qu.rear==qu.front
	队满条件：qu.rear=MAXSIZE-1
	元素x进队（需要移动队尾指针）：qu.rear++;qu.data[qu.rear]=x
	出队x(需移动队首指针)：qu.front++;x=qu.data[qu.front];
*/
/*
		循环队列的要素

	队空条件：qu.rear==qu.front
	队满条件：（qu.rear+1）%MAXSIZE=qu.front;
	元素x进队（需要移动队尾指针）：qu.rear=(qu.rear+1)%MAXSIZE;qu.data[qu.rear]=x
	出队x(需移动队首指针)：qu.front=(qu.front+1)%MAXSIZE;x=qu.data[qu.front];
*/
typedef struct
{
	ElemType data[MAXSIZE];		//数据存储
	int front,rear;				//队首和队尾指针
}SqQueue,*SQ;				//声明顺序队类型

//初始化队列
void InitQueue(SqQueue& qu);

//判断是否为空
int QueueEmpty(SqQueue qu);

//进队
int EnQueue(SqQueue& qu, ElemType x);

//出队
int DeQueue(SqQueue& qu, ElemType& x);
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

2.对顺序队列习题的讲解

2.1设计一个算法，利用队列的基本运算返回指定队列中的元素

解题思路：

​ 假设采用循环队列，队列中没有取队尾元素的基本运算，建立一个临时队列tempqu,将指定队列qu中的所有元素出队并进队到tempqu队中，这样qu队列为空，再将队列tempqu中的所有元素出队并进队到qu队中最后一个元素即为所求

代码实现

//设计一个算法，利用队列的基本运算返回指定队列中的元素
void Last(SqQueue qu, ElemType& x)
{
	SqQueue tempqu;
	InitQueue(tempqu);			//初始化队列
	while (!QueueEmpty(qu))		//qu队列不为空时
	{
		DeQueue(qu, x);			//出队元素x
		EnQueue(tempqu, x);			//将队列中的元素取出并进队到tempqu中
	}
	while (!QueueEmpty(tempqu))	//tempqu队列不为空时
	{
		DeQueue(tempqu, x);		//出队元素x
		EnQueue(qu, x);			// 将队列中的元素取出并进队到qu中
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.2设计一个算法，利用队列和栈的基本运算将指定队列中的内容进行逆转

解题思路：

​ 假设采用循环队列，建立一个临时栈tempst，将指定队列qu中的所有元素出队并进栈到tempst栈中这样qu队列为空，在将栈tempst中的所以元素出栈并进队到qu队中，这样qu队列中的内容就发生了逆置

代码实现

//设计一个算法，利用队列和栈的基本运算将指定队列中的内容进行逆转
void Reverse(SqQueue& qu)
{
	ElemType x;
	SqStack tempst;			//定义临时栈
	InitStack(tempst);		//初始化栈tempst
	while (!QueueEmpty(qu))
	{
		DeQueue(qu, x);		//出队操作
		Push(tempst, x);	//进栈操作
	}
	while (!StackEmpty(tempst))
	{
		Pop(tempst, x);		//出栈操作
		EnQueue(qu, x);		//进队操作
	}
}

//初始化栈
void InitStack(SqStack& st)
{
	st.top = -1;
}

//判断栈是否为空
int StackEmpty(SqStack st)
{
	return (st.top == -1);
}

//数据进栈
int Push(SqStack& st, ElemType x)
{
	if (st.top == MAXSIZE - 1)
		return 0;
	st.top++;
	st.data[st.top] = x;
	return 1;
}

//数据出栈
int Pop(SqStack& st, ElemType& x)
{
	if (st.top == -1)
		return 0;
	x = st.data[st.top];
	st.top--;
}
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

2.3删除循环队列中第k个元素

解题思路

​ 计算队列中的个数，通过循环，在循环体内同步进行出队和进队操作，当遇到第K个元素时跳过

//删除循环队列中第k个元素
int del_k(SqQueue& qu, int k)
{
	ElemType e;
	int i;
	int count = (qu.rear - qu.front + MAXSIZE) % MAXSIZE;	//求队列中的元素个数
	if (k <= 0 || k > count)
		return 0;
	for (i = 1; i <= count; i++)
	{
		DeQueue(qu, e);		//出队，并用e保存对头的值
		if (i != k)
			EnQueue(qu, e);		//入队，e是出队是的值
	}
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

六、链队的代码实现

1.代码的实现

main.cpp

#include"LiQueue.h"

void test1()
{
	LQU lqu;
	ElemType x;
	InitQueue(lqu);
	EnQueue(lqu, 1);
	EnQueue(lqu, 2);
	EnQueue(lqu, 3);
}

int main()
{
	test1();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LiQueue.cpp

#include"LiQueue.h"

//初始化队列
void InitQueue(LQU& lqu)
{
	lqu = (LiQueue*)malloc(sizeof(LiQueue));
	lqu->front = NULL;
	lqu->rear = NULL;
}

//判断队空
int QueueEmpty(LQU lqu)
{
	return (lqu->rear == NULL);
}

//进队
void EnQueue(LQU& lqu, ElemType x)
{
	QNode* p;
	p= (QNode*)malloc(sizeof(QNode));
	p->data = x;
	p->next = NULL;
	if (lqu->rear == NULL)		//如果链队为空，则新节点既是头节点也是尾节点
		lqu->front = lqu->rear = p;
	else			
	{
		lqu->rear->next = p;		//将节点p链到队尾，rear指向它
		lqu->rear = p;
	}
}
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

LiQueue.h

#pragma once
#include<iostream>
#include<stdlib.h>
using namespace std;

typedef int ElemType;

/*
	队空条件：lqu->rear==NULL 或 lqu->front==NULL
	队满条件：一般不考虑队满的情况
	节点p进队操作：lqu-rear->next=p;lqu->rear=p;
	节点p出队操作：p=lqu->front;lqu->front=p->next;x=p->data;free(p);
*/
//链队中数据节点的类型QNode声明
typedef struct qnode
{
	ElemType data;
	struct qnode* next;
}QNode;			//声明链队数据节点类型

//链队节点的类型LiQueue声明
typedef struct
{
	QNode* front;		//队头指针
	QNode* rear;		//队尾指针
}LiQueue,*LQU;			//声明链队节点类型

//初始化队列
void InitQueue(LQU& lqu);

//判断队空
int QueueEmpty(LQU lqu);

//进队
void EnQueue(LQU& lqu, ElemType x);
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

总结

​ 从开始的顺序表到现在的队列，如果你也有深入学习的话，你就会发现它们有很高的相似程度，而且经过一些理解还能实现利用栈先进后出的特性可以完成队列先进先出的特性，并且它们的存储方式大都相同，顺序存储的话就是分配一块联系的存储空间，链式存储也和单链表有很大的相似，只是它们对于单链表来说有了一定的限制。