范某帅的博客
0%

数据结构-第三章-栈和队列

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 6.6k 阅读时长 ≈ 6 分钟

栈的基本操作

栈的顺序存储

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
#include <stdio.h>
#define Maxsize 10

typedef struct {
	int data[Maxsize];
	int top;
}SqStack;

void InitStack(SqStack& S) {
	S.top = -1;
}

bool isEmpty(SqStack S) {
	return S.top == -1;
}

bool Push(SqStack& S, int element) {
	if (S.top == Maxsize - 1) {
		return false;
	}
	S.data[++S.top] = element;
	return true;
}

int Pop(SqStack& S) {
	if (S.top == -1) {
		return -1;
	}
	return S.data[S.top--];
}

int GetTop(SqStack S) {
	if (S.top == -1) {
		return -1;
	}
	return S.data[S.top];
}

void ShowStack(SqStack S) {
	for (int i = 0; i <= S.top; i++) {
		printf("%d ", S.data[i]);
	}
}

int main()
{
	SqStack S;
	InitStack(S);
	Push(S, 1);
	Push(S, 3);
	Push(S, 5);
	Push(S, 7);
	Push(S, 9);
	if (isEmpty(S)) {
		printf("空的\n");
	}
	else {
		printf("不是空的\n");
	}
	ShowStack(S);
	printf("\n出栈的元素是：%d", Pop(S));
	printf("\n出栈的元素是：%d\n", Pop(S));
	ShowStack(S);
	return 0;
}

另一种方式，初始化时top=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
#include <stdio.h>
#define Maxsize 10

typedef struct {
	int data[Maxsize];
	int top;
}SqStack;

void InitStack(SqStack &S) {
	S.top = 0;
}

bool Push(SqStack &S, int element) {
	if (S.top == Maxsize)
	{
		return false;
	}
	S.data[S.top++] = element;
	return true;
}

int Pop(SqStack &S) {
	if (!S.data[0])
	{
		return -1;
	}
	return S.data[--S.top];
}

共享栈

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#define Maxsize 10

typedef struct {
	int data[Maxsize];
	int top0;
	int top1;
}SqStack;

void InitStack(SqStack &S) {
	S.top0 = -1;
	S.top1 = Maxsize;
}

栈的链式存储

1
2
3
4
5
6
#include <stdio.h>

typedef struct LinkNode {
	int data;
	struct LinkNode* next;
}*LiStack;

队列的基本操作

队列的顺序实现

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
#include <stdio.h>
#define Maxsize 10

typedef struct {
	int data[Maxsize];
	int front, rear;
}SqQueue;

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

//判断是否为空
bool isEmpty(SqQueue Q) {
	return Q.front == Q.rear;
}

//入队
bool EnQueue(SqQueue &Q, int element) {
	//判断队列是否已满
	if ((Q.rear + 1) % Maxsize == Q.front)
	{
		return false;
	}
	Q.data[Q.rear] = element;
	Q.rear = (Q.rear + 1) % Maxsize;
	return true;
}

//出队
int DeQueue(SqQueue &Q) {
	//判断队列是否为空
	if (Q.rear == Q.rear)
	{
		return -1;
	}
	int element = Q.data[Q.front];
	Q.front = (Q.front + 1) / Maxsize;
	return element;
}

int GetHead(SqQueue &Q) {
	//判断队列是否为空
	if (Q.rear == Q.front)
	{
		return -1;
	}
	return Q.data[Q.front];
}

队列的链式实现

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
#include <stdio.h>
#include <malloc.h>

typedef struct LinkNode {
	int data;
	struct LinkNode* next;
}LinkNode;

typedef struct {
	LinkNode* front, * rear;
}LinkQueue;

//带头结点
void InitQueue(LinkQueue &Q) {
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next = NULL;
}

//不带头节点
void InitQueueNoHead(LinkQueue &Q) {
	Q.front = Q.rear = NULL;
}

//是否为空
bool isEmpty(LinkQueue Q) {
	return Q.front == Q.rear;
}

//新元素入队 带头结点
void EnQueue(LinkQueue &Q, int element) {
	LinkNode* new_point = (LinkNode*)malloc(sizeof(LinkNode));
	new_point->data = element;
	new_point->next = NULL;
	Q.rear->next = new_point;
	Q.rear = new_point;
}

//新元素入队 不带头节点
void EnQueueNoHead(LinkQueue &Q, int element) {
	LinkNode* new_point = (LinkNode*)malloc(sizeof(LinkNode));
	new_point->data = element;
	new_point->next = NULL;
	if (Q.front == NULL)
	{
		Q.front = new_point;
		Q.rear = new_point;
	}
	else
	{
		Q.rear->next = new_point;
		Q.rear = new_point;
	}
}

//出队 带头结点
void DeQueue(LinkQueue &Q) {
	if (Q.front == Q.rear)
	{
		printf("队列为空");
	}
	else
	{
		LinkNode* point = Q.front->next;
		printf("出队的元素是%d\n", point->data);
		Q.front->next = point->next;
		if (Q.rear == point)
		{
			Q.rear = Q.front;
		}
		free(point);
	}
}

//出队 不带头节点
void DeQueueNoHead(LinkQueue &Q) {
	if (Q.front = NULL)
	{
		printf("队列为空");
	}
	else
	{
		LinkNode* point = Q.front;
		printf("出队的元素是%d\n", point->data);
		Q.front = point->next;
		if (Q.rear == point)
		{
			Q.front = Q.rear = NULL;
		}
		free(point);
	}
}

void ShowQueue(LinkQueue Q) {
	LinkNode* point = Q.front->next;
	while (point!= NULL) {
		printf("%d ", point->data);
		point = point->next;
	}
	printf("\n");
	free(point);
}

int main() {
	LinkQueue Q;
	InitQueue(Q);
	for (int i = 0; i <= 10; i++)
	{
		EnQueue(Q, i);
	}
	if (isEmpty(Q))
	{
		printf("队列为空");
	}
	else
	{
		printf("队列不为空");
	}
	ShowQueue(Q);
	DeQueue(Q);
	DeQueue(Q);
	DeQueue(Q);
	EnQueue(Q, 0);
	EnQueue(Q, 1);
	EnQueue(Q, 2);
	ShowQueue(Q);
	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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#define Maxsize 10

typedef struct {
	char data[Maxsize];
	int top;
}SqStack;

void InitStack(SqStack& S) {
	S.top = -1;
}

bool isEmpty(SqStack S) {
	return S.top == -1;
}

bool Push(SqStack& S, char element) {
	if (S.top == Maxsize - 1) {
		return false;
	}
	S.data[++S.top] = element;
	return true;
}

int Pop(SqStack& S) {
	if (S.top == -1) {
		return -1;
	}
	return S.data[S.top--];
}

int GetTop(SqStack S) {
	if (S.top == -1) {
		return -1;
	}
	return S.data[S.top];
}

void ShowStack(SqStack S) {
	for (int i = 0; i <= S.top; i++) {
		printf("%d ", S.data[i]);
	}
}

void bracketCheck(char str[], int length) {
	SqStack S;
	InitStack(S);
	
	for (int i = 0; i < length; i++)
	{
		if (str[i] == '(' || str[i] == '[' || str[i] == '{')
		{
			Push(S, str[i]);
		}
		else
		{
			if (isEmpty(S))
			{
				printf("栈为空");
			}
			else
			{
				char topElement = Pop(S);
				if (str[i] == ')' && topElement != '(')
				{
					printf("匹配不正确！");
				}
				if (str[i] == ']' && topElement != '[')
				{
					printf("匹配不正确！");
				}
				if (str[i] == '}' && topElement != '{')
				{
					printf("匹配不正确！");
				}
			}
		}
	}
	if (isEmpty(S))
	{
		printf("匹配成功！");
	}
	else
	{
		printf("匹配失败！");
	}
}

int main()
{	
	char str_char[] = { '{', '{', '[', '[', ']', ']', '(', ')', '(', ')', '}', '}' };
	bracketCheck(str_char, (sizeof(str_char)/sizeof(str_char[0])));
	return 0;
}

本文标题:数据结构-第三章-栈和队列

文章作者:fanchen

发布时间:2021年05月27日 - 21:55:25

最后更新:2021年05月29日 - 09:10:07

原始链接:http://88fanchen.github.io/posts/5116f53a/

许可协议:署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。