【C语言】数据结构-栈(详解)
慕雪年华

[TOC]

前言

在之前的数据结构学习中,我们学习了顺序表、链表这两种结构

除了单链表以外,还有一个结构,是双向带头循环链表。这个链表的形式如下

  • 头节点的prev指向尾部节点
  • 尾节点的next指向头节点,构成循环

image

别看它的形式有些复杂,实际代码的实现,比单链表还简单

因为head->prev指向了尾节点,所以不需要找尾。尾删的时候也不需要遍历找尾节点的前一位,因为尾节点的prev就存放了前一位的地址。

所以这里就偷懒不写博客了!反正也没啥人看😭

好吧,最后我还是写了一篇水文👉点我


本篇博客讲述的是另外一个特别的线性表,

1.什么是栈

数据结构里的栈,和函数栈帧中的“栈”有一定相似,但实际上它们完全不同

栈作为一个特殊的线性表,它只允许在表的一头添加、删除数据。

所有的数据都遵循先进后出,后进先出的原则

  • 压栈:栈的插入操作叫做进栈/压栈/入栈,新的数据存放在栈顶
  • 出栈:栈的删除操作,先删除栈顶的数据

image

2.栈的实现

栈可以用数组或者链表来实现,相对而言,数组的方法更优

因为数组在尾插数据的时候,可以很方便的找到尾。而单链表需要遍历找尾,耗时较长。

image

是不是有些似曾相识呢?没错,实际上栈区就是一个只能尾插+尾删的顺序表

3.敲代码!

3.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
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;

// 初始化栈
void StackInit(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回false,如果不为空返回true
bool StackEmpty(Stack* ps);
//打印
void StackPrint(Stack* ps);

和顺序表不同的是,我们需要写一个单独的函数来获取栈顶元素,这一点在很多OJ题目中都需要用到。

3.2函数实现

如果你看过了我之前顺序表的博客,这部分对你来说想必不难。

如果有什么问题,欢迎在评论区提出!

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

// 初始化
void StackInit(Stack* ps)
{
STDataType* new = (STDataType*)malloc(4*sizeof(STDataType) );
if (new == NULL)
exit(-1);
else
{
ps->a = new;
ps->top = 0;
ps->capacity = 4;
}
}

// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);

free(ps->a);
ps->a = NULL;

ps->capacity = 0;
ps->top = 0;
}

// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->top == ps->capacity)//容量检查
{
STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
if (new == NULL)
{
exit(-1);
}
else
{
ps->a = new;
ps->capacity *= 2;
}
}
ps->a[ps->top] = data;
ps->top++;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
if (ps->top > 0)
(ps->top)--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];

}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
// 检测栈是否为空,如果为空返回true,如果不为空返回false
bool StackEmpty(Stack* ps)
{
assert(ps);
if (ps->top == 0)
return true;
else
return false;
}

void StackPrint(Stack* ps)
{
assert(ps);
int n = ps->top;
for (int i = 0; i < n; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}

大家在自己编写这种带多个板块的代码的时候,一定要一个板块写完就检查一遍!不要将问题都丢一块解决,那样会非常难受的!

image

在其他版块都确认无误之后,也要过来瞅一眼Destroy板块,避免出现free错误等情况。

这个板块我们可以通过打断点(VS快捷键F9)并调试的方法来检查该板块是否正确

image

4.知识巩固,来道OJ!

leetcode 20 有效的括号

leetcode:20. 有效的括号

image

这道题就是一道非常使用用栈来解决的OJ题

题目要求我们判断给出的字符串中,括号是否一一对应

1
2
3
{[]}//对应
{[(])}//不对应
{{()}//少了一个右边括号,不对应

具体要怎么做呢?思路如下:

  • 用一个指针来遍历字符串,如果是左括号{([其中一个,就入栈
  • 如果是右边括号,说明左括号已经入栈完毕,开始比对
  • 栈顶的括号一定是和当前右括号匹配的,如果不是则为false
  • 每判断一次,就让栈顶的左括号出栈一次

最后的函数实现如下

需要注意的是,STDataType类型需要更改为char类型,此时存放的是括号字符,并不是数字

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
typedef char STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;

// 初始化
void StackInit(Stack* ps)
{
STDataType* new = (STDataType*)malloc(sizeof(STDataType) * 4);
if (new == NULL)
{
exit(-1);
}
else
{
ps->a = new;
ps->top = 0;
ps->capacity = 4;
}
}

// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);

free(ps->a);
ps->a = NULL;

ps->capacity = 0;
ps->top = 0;
}

// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
if (new == NULL)
{
exit(-1);
}
else
{
ps->a = new;
ps->capacity *= 2;
}
}
ps->a[ps->top] = data;
ps->top++;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
if (ps->top > 0)
(ps->top)--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];

}
// 检测栈是否为空,如果为空返回true,如果不为空返回false
bool StackEmpty(Stack* ps)
{
assert(ps);
if (ps->top == 0)
return true;
else
return false;
}

bool isValid(char * s){
Stack st;
StackInit(&st);

while(*s)
{
if(*s=='{'||*s=='['||*s=='(')
{
StackPush(&st,*s);
s++;
}
else
{
if(StackEmpty(&st))
{
return false;
}

char top=StackTop(&st);//取栈顶元素
StackPop(&st);//把栈顶删除
//如( { 这两个,取了栈顶{,就立马pop掉它

if((*s=='}'&&top=='{')
||(*s==')'&&top=='(')
||(*s==']'&&top=='['))
{
s++;
}
else
{
StackDestroy(&st);

return false;
}

}
}
bool ret=StackEmpty(&st);
//如果为空,说明匹配完毕;非空说明还有剩下的左括号

StackDestroy(&st);

return ret;
}

这个算法的用时还是非常短的!

image

结语

数据结构学到这里,其实在了解完这些结构的真正思路后,代码的实现反而并不是那么重要。

在学习这部分知识的时候,一定要多画图!

如果你不适应用鼠标画图,可以直接用纸笔画,一些非常简单的草图,也能极大帮助我们理解当前的代码,找出问题👍