logo
小吃货落樱
banner
数据结构的世界

Queue

Scroll down

队列

基本操作

1
2
3
4
#include<stdio.h>
#include"SeQueue.h"
#include<stdlib.h>

SeQueue.h

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
#pragma once
typedef int ElemType;
#define MAXSIZE 8

typedef struct{
	ElemType data[MAXSIZE];
	int front;
	int rear;
	int size;
}SeQueue;

//初始化队列
void initQueue(SeQueue &Q);

//判断队列是否为空
bool isEmpty(SeQueue Q);

//元素入队
bool enQueue(SeQueue &Q,ElemType x);

//出队
ElemType deQueue(SeQueue &Q);

//获取队头
ElemType getHead(SeQueue Q);

//获取队列长度
int getSize(SeQueue Q);

//打印队列元素
void print(SeQueue 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
#include"All.h"


//初始化队列
void initQueue(SeQueue &Q)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		Q.data[i]=0;
	}
	Q.size=0;
	Q.front=0;
	Q.rear=0;
}

//判断队列是否为空
bool isEmpty(SeQueue Q)
{
	return Q.front==Q.rear;
	//return Q.size==0;

}

//元素入队
bool enQueue(SeQueue &Q,ElemType x)
{
	if(Q.rear>=MAXSIZE)//Q.rear>=MAXSIZE
	{
		return false;
	}
	Q.data[Q.rear++]=x;
	Q.size++;
	return true;
}

//出队
ElemType deQueue(SeQueue &Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}else{
		Q.size--;
		return Q.data[Q.front++];
	}

}

//获取队头
ElemType getHead(SeQueue Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}
	return Q.data[Q.front];
}

//获取队列长度
int getSize(SeQueue Q)
{
	return Q.size;
	//return Q.rear-Q.front
}

//打印队列元素
void print(SeQueue Q)
{
	if(isEmpty(Q));
	for(int i=Q.front;i<Q.rear;i++)
	{
		printf("%d ",Q.data[i]);
	}
	printf("\n");
	printf("Q.front=%d\n",Q.front);
	printf("Q.rear=%d\n",Q.rear);
	printf("Q.size=%d\n",Q.size);
}

测试结果

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
#include"All.h"

int main()
{
	SeQueue Q;
	initQueue(Q);
	for(int i=0;i<5;i++)
	{
		enQueue(Q,i);
	}
	print(Q);
	printf("\n");
	for(int i=0;i<3;i++)
	{
		ElemType x=deQueue(Q);
		printf("当前出队的元素值：%d\n",x);
	}
	print(Q);
	printf("\n");
	for(int i=10;i<15;i++)
	{
		enQueue(Q,i);
	}
	print(Q);
	system("pause");
	return 0;
}



结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
0 1 2 3 4
Q.front=0
Q.rear=5
Q.size=5

当前出队的元素值：0
当前出队的元素值：1
当前出队的元素值：2
3 4
Q.front=3
Q.rear=5
Q.size=2

3 4 10 11 12
Q.front=3
Q.rear=8
Q.size=5
请按任意键继续. .

循环队列

头文件

1
2
3
#include"CircularQueue.h"
#include<stdio.h>
#include<stdlib.h>
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
#pragma once
typedef int ElemType;
#define MAXSIZE 8

typedef struct{
	ElemType data[MAXSIZE];
	int front;
	int rear;
	int size;
	int tag;//来标记是空队还是满队0为空1为有元素
}Queue;

//初始化队列
bool initQueue(Queue &Q);

//判断队列是否为满
bool isFull(Queue Q);

//判断队空
bool isEmpty(Queue Q);

//元素x入队
bool enQueue(Queue &Q,ElemType x);

//出队
ElemType deQueue(Queue &Q);

//取队头元素
ElemType getHead(Queue Q);

//获取队列长度
int getSize(Queue Q);

//打印队列元素
void printQueue(Queue 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
#include"All.h"

//初始化队列
bool initQueue(Queue &Q)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		Q.data[i]=0;
	}
	Q.front=0;
	Q.rear=0;
	Q.size=0;
	Q.tag=0;
	return true;
}

//判断队列是否为满
bool isFull(Queue Q)
{
	return (Q.rear+1)%MAXSIZE==Q.front;
	//reurn size==MAXSIZE;
	//return Q.tag==1&&Q.front==Q.rear;
}

//判断队空
bool isEmpty(Queue Q)
{
	return Q.front==Q.rear;
	//return size==0;
	//return Q.front==Q.rear&&tag==0;
}

//元素x入队
bool enQueue(Queue &Q,ElemType x)
{
	if(isFull(Q))
	{
		return false;
	}
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear+1)%MAXSIZE;
	//Q.size++;
	/*if(Q.rear==Q.front)
	{
		Q.tag=1;
	}*/
	return true;
}

//出队
ElemType deQueue(Queue &Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}else{
		ElemType x=Q.data[Q.front];
		Q.front=(Q.front+1)%MAXSIZE;
		Q.size--;
		//if(Q.front==Q.rear)
		//{
		//	Q.tag=0;
		//}
		return x;
	}
}

//取队头元素
ElemType getHead(Queue Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}
	ElemType x=Q.data[Q.front];
	return x;
}

//获取队列长度
int getSize(Queue Q)
{
	//return Q.rear-Q.front;//队头在队尾前面
	//return (Q.rear-Q.front+MAXSIZE);//队尾在队头前面
	return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;//合并
	//return Q.tag?((Q.rear-Q.front+MAXSIZE)%MAXSIZE):MAXSIZE;
	//return Q.size;
}

//打印队列元素
void printQueue(Queue Q)
{
	if(isEmpty(Q))
	{
		return;
	}
	int len=getSize(Q);
	int i=Q.front;
	while(len>0)
	{
		printf("%d ",Q.data[i]);
		i=(i+1)%MAXSIZE;
		len--;
	}
	printf("\n");
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include"All.h"

int main()
{
	Queue Q;
	initQueue(Q);
	for(int i=0;i<5;i++)
	{
		enQueue(Q,i);
	}
	printQueue(Q);
	for(int i=0;i<2;i++)
	{
		deQueue(Q);
	}
	printQueue(Q);
	for(int i=10;i<15;i++)
	{
		enQueue(Q,i);
	}
	printQueue(Q);
	system("pause");
	return 0;
}

结果

1
2
3
4
0 1 2 3 4
2 3 4
2 3 4 10 11 12 13
请按任意键继续. . .

链队列

头文件

1
2
3
#include<stdio.h>
#include"LinkQueue.h"
#include<stdlib.h>

结构体+函数声明

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
#pragma once

typedef int ElemType;

typedef struct LinkQueue{
	ElemType data;
	LinkQueue*next;
}LNode;//结点结构

typedef struct{
	LNode*front;
	LNode*rear;
	int size;
}Queue;//队列结构

//初始化队列
void initQueue(Queue &Q);

//判断队列是否为空
bool isEmpty(Queue Q);

//入队
void enQueue(Queue &Q,ElemType x);

//出队
ElemType deQueue(Queue &Q);

//取队头元素
ElemType getHead(Queue Q);

//获取队列长度
int getSize(Queue Q);

//打印队列元素
void print(Queue 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
#include"All.h"

//初始化队列
void initQueue(Queue &Q)
{
	Q.front=NULL;
	Q.rear=NULL;
	Q.size=0;
}

//判断队列是否为空
bool isEmpty(Queue Q)
{
	return (Q.front==NULL||Q.rear==NULL||Q.size==0);
}

//入队
void enQueue(Queue &Q,ElemType x)
{
	LNode*node=(LNode*)malloc(sizeof(LNode));
	node->data=x;
	node->next=NULL;
	if(isEmpty(Q))
	{
		Q.rear=node;
		Q.front=node;
	}else{
		Q.rear->next=node;
		Q.rear=node;
	}
	Q.size++;
}

//出队
ElemType deQueue(Queue &Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}
	LNode*pre=Q.front;
	Q.front=Q.front->next;
	ElemType x=pre->data;
	free(pre);
	if(Q.front==NULL)
	{
		Q.rear=NULL;
	}
	Q.size--;
	return x;
}

//取队头元素
ElemType getHead(Queue Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}else{
		return Q.front->data;
	}
}

//获取队列长度
int getSize(Queue Q)
{
	return Q.size;
}

//打印队列元素
void print(Queue Q)
{
	if(isEmpty(Q))
	{
		return;
	}
	LNode*pre=Q.front;
	while(pre)
	{
		printf("%d ",pre->data);
		pre=pre->next;
	}
	printf("\n");
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include"All.h"

int main()
{
	Queue Q;
	initQueue(Q);
	for(int i=0;i<10;i++)
	{
		enQueue(Q,i);
	}
	print(Q);
	for(int i=0;i<6;i++)
	{
		deQueue(Q);
	}
	print(Q);
	system("pause");
	return 0;
}

结果

1
2
3
0 1 2 3 4 5 6 7 8 9
6 7 8 9
请按任意键继续. . .

双端队列

头文件+结构体+函数声明

1
2
3
#include<stdio.h>
#include<stdlib.h>
#include"DeQueue.h"
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
#pragma once

typedef int ElemType;

typedef struct DNode{
	ElemType data;
	DNode*prior;
	DNode*next;
}DNode;

typedef struct{
	DNode*front;//队尾
	DNode*rear;//队头
	int size;//队列大小
}DeQueue;

//1初始化双端队列//带头结点
void initQueue(DeQueue &Q);

//2判断队列是否为空
bool isEmpty(DeQueue Q);

//3向队头添加元素
void pushHead(DeQueue &Q,ElemType x);

//4从队头移除元素
ElemType popHead(DeQueue &Q);

//5在队尾添加元素
void pushTail(DeQueue &Q,ElemType x);

//6从队尾删除元素
ElemType popTail(DeQueue &Q);

//7获取表头
ElemType peekHead(DeQueue Q);

//8取表尾
ElemType peekTail(DeQueue Q);

//9从头到尾打印队列
void printHead(DeQueue Q);

//10从尾到头打印
void printTail(DeQueue Q);

//11获取队列长度
int length(DeQueue 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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include"All.h"

//初始化双端队列//带头结点
void initQueue(DeQueue &Q)
{
	DNode*node=(DNode*)malloc(sizeof(DNode));
	node->next=NULL;
	node->prior=NULL;
	Q.rear=node;
	Q.front=node;
	Q.size=0;
}

//判断队列是否为空
bool isEmpty(DeQueue Q)
{
	return Q.size==0||Q.front==Q.rear;
}

//向队头添加元素
void pushHead(DeQueue &Q,ElemType x)
{
	
	DNode*pre=(DNode*)malloc(sizeof(DNode));
	pre->data=x;
	pre->next=NULL;
	pre->prior=NULL;
	if(isEmpty(Q))
	{
		pre->prior=Q.front;
		Q.front->next=pre;
		Q.rear=pre;
	}else{
		pre->next=Q.front->next;
		Q.front->next->prior=pre;
		Q.front->next=pre;
		pre->prior=Q.front;
	}
	Q.size++;
	}

//从队头移除元素
ElemType popHead(DeQueue &Q)
{
	if(isEmpty(Q))
	{
		return-999;
	}
	ElemType x;
	if(Q.front->next==Q.rear)//只有一个元素时
	{
		x=Q.rear->data;
		free(Q.rear);
	}else{
		DNode*pre=Q.front->next;
		pre->next->prior=Q.front;
		Q.front->next=pre->next;
		x=pre->data;
		free(pre);
	}//不止一个元素时
	Q.size--;	
	return x;
}

//在队尾添加元素
void pushTail(DeQueue &Q,ElemType x)
{
	DNode*pre=(DNode*)malloc(sizeof(DNode));
	pre->data=x;
	pre->next=NULL;
	pre->next=Q.rear->next;
	pre->prior=Q.rear;
	Q.rear->next=pre;
	Q.rear=pre;
	Q.size++;
}

//从队尾删除元素
ElemType popTail(DeQueue &Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}
	DNode*last=Q.rear;
	ElemType x=last->data;
	Q.rear=Q.rear->prior;
	Q.rear->next=NULL;
	free(last);
	Q.size--;
	return x;
}

//获取表头
ElemType peekHead(DeQueue Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}else{
		return Q.front->next->data;
	}
}

//取表尾
ElemType peekTail(DeQueue Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}else{
		return Q.rear->data;
	}
}


//从头到尾打印队列
void printHead(DeQueue Q)
{
	if(isEmpty(Q))
	{
		return;
	}else{
		DNode*pre=Q.front;
		while(pre->next)
		{
			pre=pre->next;
			printf("%d ",pre->data);
		}
		printf("\n");
	}
}

//从尾到头打印
void printTail(DeQueue Q)
{
	if(isEmpty(Q))
	{
		return;
	}else{
		DNode*last=Q.rear;
		while(last!=Q.front)
		{
			printf("%d ",last->data);
			last=last->prior;
		}
		printf("\n");
	}
	
}

//获取队列长度
int length(DeQueue Q)
{
	return Q.size;
}

测试

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
#include"All.h"

int main()
{
	DeQueue Q;
	initQueue(Q);
	for(int i=0;i<5;i++)
	{
		pushHead(Q,i);
	}
	printf("从头到尾：");
	printHead(Q);
	printf("从尾到头：");
	printTail(Q);
	printf("队列长度%d",length(Q));
	printf("\n\n");

	for(int i=10;i<13;i++)
	{
		pushTail(Q,i);
	}
	printf("从头到尾：");
	printHead(Q);
	printf("从尾到头：");
	printTail(Q);
	printf("队列长度%d",length(Q));
	printf("\n\n");

	for(int i=0;i<2;i++)
	{
		popHead(Q);
	}
	printf("从头到尾：");
	printHead(Q);
	printf("从尾到头：");
	printTail(Q);
	printf("队列长度%d",length(Q));
	printf("\n\n");

	for(int i=0;i<2;i++)
	{
		popTail(Q);
	}
	printf("从头到尾：");
	printHead(Q);
	printf("从尾到头：");
	printTail(Q);
	printf("队列长度%d",length(Q));
	printf("\n\n");

	system("pause");
	return 0;
}


结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
从头到尾：4 3 2 1 0
从尾到头：0 1 2 3 4
队列长度5

从头到尾：4 3 2 1 0 10 11 12
从尾到头：12 11 10 0 1 2 3 4
队列长度8

从头到尾：2 1 0 10 11 12
从尾到头：12 11 10 0 1 2
队列长度6

从头到尾：2 1 0 10
从尾到头：10 0 1 2
队列长度4

请按任意键继续. . .

老爷，养我呜呜呜

其他文章
cover
考研数学
  • 24/08/14
  • 20:16
  • 自我感想
cover
HTML学习
  • 24/07/05
  • 21:16
  • HTML
网站标题

网站运行时间：0天

最后更新时间：00:00:00

目录导航 置顶
  1. 1. 循环队列
  2. 2. 链队列
  3. 3. 双端队列
请输入关键词进行搜索
  • to close