PTA数据结构(C++版)——7-1 队列的实现及基本操作（

发表于

这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战

1.编译运行

在这里插入图片描述

2.题目：

给定一个初始为空的队列和一系列入队、出队操作，请编写程序输出每次出队的元素。队列的元素值均为整数。

  • 输入格式：

输入第1行为1个正整数n，表示操作个数；接下来n行，每行表示一个操作，格式为1 d或0。1 d表示将整数d入队，0表示出队。n不超过20000。

  • 输出格式：

按顺序输出每次出队的元素，每个元素一行。若某出队操作不合法（如在队列空时出队），则对该操作输出invalid。

  • 输入样例:

在这里给出一组输入。例如：

7
1 1
1 2
0
0
0
1 3
0

  • 输出样例:

1
2
invalid
3

3.想法

本来这个是用一个最简单的有限长数组实现队列的性质即可，但是考虑到假如我们要对其频繁的动态增删，或者为其增加特别多的元素，那么有限长的数组就不能实现了。那么与顺序表结构相对的就是适合频繁增删的链式结构，所以为了实现动态添加，在这里我就本着玩的心态，选择了链式存储结构，用链队实现我们的想法，完成一个理论上没有上限，可以无限增加的队列。

4.代码块

  • 队列的链式存储结构
    设置一个结构体，每个结点包含数据 Data，和一个指向下一个结点的 指针 *next。
    再设置一个结构体，拥有可以指向队列头尾结点的指针。
1
2
3
4
5
6
7
8
9
cpp复制代码typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct {
	QueuePtr front;	//队头指针 
	QueuePtr rear;	//队尾指针 
}LinkQueue;
  • 链队的初始化

生成新结点作为头结点，队头和队尾指针指向此结点

1
2
3
4
5
6
cpp复制代码Status InitQueue(LinkQueue &Q){
	Q.front = Q.rear=new QNode;
	//头结点的指针域为空 
	Q.front->next = NULL;
	return Ok;
}
  • 链队的入队
    1. 插入元素e为Q的新的队尾元素
    2. 为入队元素分配结点空间，用指针P指向
    3. 给新结点的数据域赋值
    4. 将新结点插入到队尾，修改队尾指针
1
2
3
4
5
6
7
8
cpp复制代码Status EnQueue(LinkQueue &Q,QElemType e){
	QNode *p=new QNode;
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return Ok;
}
  • 链队的出队
    1. 元素出队即删除队列的队头元素
    2. 首先判断队列是否为空
    3. 生成一个新结点起到一个数据中转的作用
    4. 修改头结点的指针域
    5. 元素被删，队尾指针指向头结点
    6. 释放原队头元素的空间
1
2
3
4
5
6
7
8
9
10
11
12
cpp复制代码Status DeQueue(LinkQueue &Q,QElemType &e){
	//删除Q的队头元素，用e返回其值
	if(Q.front==Q.rear) return Error;
	//p指向队头元素 
	QNode *p=Q.front->next;
	//e保存队头元素的值 
	e=p->data;
	Q.front->next = p->next;
	if(Q.rear == p) Q.rear =Q.front;
	delete p;
	return Ok; 
}
  • 取链队的头元素
    1. 判断队列是否为空
    2. 取结点的 data 域
1
2
3
4
5
6
7
8
cpp复制代码SElemType GetHead(LinkQueue Q){
	//返回Q的队头元素，不修改指针
	//队列非空 
	if(Q.front!=Q.rear){
		//返回队头元素的值，队头指针不变 
		return Q.front->next->data;
	} 
}

4.源码

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
cpp复制代码#include<iostream>
using namespace std;
typedef int QElemType;
typedef int SElemType;
typedef int Status;
#define Ok 1
#define Error 0 
//队列的链式存储结构 
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct {
	QueuePtr front;	//队头指针 
	QueuePtr rear;	//队尾指针 
}LinkQueue;

 //链队的初始化 
Status InitQueue(LinkQueue &Q){
	//生成新结点作为头结点，队头和队尾指针指向此结点 
	Q.front = Q.rear=new QNode;
	//头结点的指针域为空 
	Q.front->next = NULL;
	return Ok;
}

//链队的入队
Status EnQueue(LinkQueue &Q,QElemType e){
	//插入元素e为Q的新的队尾元素
	//为入队元素分配结点空间，用指针P指向 
	QNode *p=new QNode;
	//新结点的数据域为e 
	p->data = e;
	//将新结点插入到队尾 
	p->next = NULL;
	//修改队尾指针 
	Q.rear->next = p;
	Q.rear = p;
	return Ok;
} 

//链队的出队
Status DeQueue(LinkQueue &Q,QElemType &e){
	//删除Q的队头元素，用e返回其值
	//若队列为空，则返回Error 
	if(Q.front==Q.rear) return Error;
	//p指向队头元素 
	QNode *p=Q.front->next;
	//e保存队头元素的值 
	e=p->data;
	//修改头结点的指针域 
	Q.front->next = p->next;
	//最后一个元素被删，队尾指针指向头结点 
	if(Q.rear == p) Q.rear =Q.front;
	//释放原队头元素的空间 
	delete p;
	return Ok; 
} 

//取链队的头元素
SElemType GetHead(LinkQueue Q){
	//返回Q的队头元素，不修改指针
	//队列非空 
	if(Q.front!=Q.rear){
		//返回队头元素的值，队头指针不变 
		return Q.front->next->data;
	} 
} 
 int main(){
 	QElemType e;
 	LinkQueue Q; 
 	InitQueue(Q);
 	int n,b;
 	cin>>n;
 	while(n-->0){
 		cin>>b;
 		if(b==1){
 				cin>>b;
 				EnQueue(Q,b);
 		}
		 if(b==0){
 			if(Q.front==Q.rear)
 				cout<<"invalid"<<endl;
 			else{
 				DeQueue(Q,b);
 				cout<<b<<endl;
 			}			
 		}			
 	}
 	return 0;
 }

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%