栈概念及基本操作

栈也同链表和顺序表一样是一种线性表只是比较特殊而已，栈遵循一种先进后出的原则,其实栈就像生活中的叠盘子一样，将盘子一个一个的叠起来，每次都只能在最顶层叠，然后取盘子的时候也是从顶层一个一个的拿；

就同上面盘子一样，最先放的那个盘子它所在的位置是最底下的，然后最后放的那个盘子所在的位置在最上面。其实转到栈来说最早进入栈的那个元素存放的位置被称为栈底，最后进入的那个元素存放的位置被称为栈顶，但是并不是最先进栈的元素要最后才出，它最先进去的也可以最先出栈只是它进栈然后再出栈才将后一个元素进栈。

我们每次对栈的操作包括：插入数据（进栈）、删除数据（出栈）都是在栈顶进行的。
那应该用什么来实现？它既可以用数组实现也可以用数组实现，但是这里用数组实现要稍好，因为数组每次都在尾端进行插入删除操作，以数组实现栈操作，出栈和入栈在尾部操作，不会移动额外的元素，它的时间复杂度为O(1),它有一个唯一的缺陷就是空间不够了需要扩容，但是内存申请是特别快，而且他也不是每次都需要扩容。但是如果一定要用链表的话，那么用单向还是双向链表，这里用单向链表较好，因为双向链表毕竟还要多用一个指针，所以用单链表吧，那么单链表的话就以栈顶为单链表的头，链表每次在头进行插入和删除操作，即时间复杂度也为O(1)，但是栈用链表实现还是数组实现，这里看个人习惯叭，我还是比较习惯用数组实现，本文就是以数组来实现栈的。

栈的结构定义

typedef int SLDataType;//这里为栈类型，以后类型修改的时候就可以在这里进行修改不然的话在代码中去要修改很多麻烦
typedef struct Stack
{
SLDataType* a;//动态栈
int top;//栈顶
int capacity;//初始容量大小一般情况下先给4个元素大小
}St;
1
2
3
4
5
6
7

当然也可以用静态数组实现，只是空间不好把握

对于top的初始化给值可以有很多种，但是一般是0，或者-1，给0，代表top位置为栈顶元素的下一个位置，用的时候先用再加加，然后top给-1的话表示当前位置就是栈顶元素的位置，用的时候先加加再使用
在本文中top为0
栈的初始化

开始时op = 0,并且给栈先分配四个元素大小空间

void STInit(St* s)
{
//初始化栈大小为4
s->a = malloc(sizeof(SLDataType) * 4);
if (s->a == NULL)
{
perror("malloc fail\n");
return;
}
s->capacity = 4;//
s->top = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

压栈

void STPush(St* s, SLDataType x)
{
assert(s);
if (s->top == s->capacity)//判断栈是否满
//栈这时满了，那么就要扩容了，扩容一般情况下扩二倍
{
SLDataType* tmp = (SLDataType*)realloc(s->a, sizeof(SLDataType)*(s->capacity)* 2);
if (tmp == NULL)
{
perror("realloc fail\n");
return;
}

else
{
s->a = tmp;
s->capacity *= 2;
}
}

s->a[s->top] = x;
s->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

出栈

//这里出栈是将栈顶元素删掉，
void STPop(St* s)
{

assert(s);
assert(s->top>0);//断言判断，栈为空就直接报错
//这里判断栈是否为空
s->top--;
}

1
2
3
4
5
6
7
8
9
10

取栈顶元素

int STTop(St* s)
{
    assert(s->top>0);
return s->a[(s->top-1)];//直接返回栈顶的那个元素，但是要注意的是栈顶下标，top表示的是栈顶元素的下一个位置，所以这里top要减一才可以取到栈顶元素
}
1
2
3
4
5

栈大小

int STSize(St* s)
{
return s->top;//栈顶指针top所在位置就是栈中有效元素的个数
}

1
2
3
4
5

销毁

void STDestroy(St* s)
{

assert(s);
free(s->a);//动态开辟的释放，不然存在内存泄漏危机
s->a = NULL;
s->top = 0;
s->capacity = 0;
}
1
2
3
4
5
6
7
8
9

源码

stack.c

#include"Stack.h"

void STInit(St* s)
{
assert(s);
//初始化栈大小为4
s->a = malloc(sizeof(SLDataType) * 4);
if (s->a == NULL)
{
perror("malloc fail\n");
return;
}
s->capacity = 4;
s->top = 0;
}
//
//销毁栈
void STDestroy(St* s)
{

assert(s);
free(s->a);
s->a = NULL;
s->top = 0;
s->capacity = 0;
}

//插入x，尾插(栈顶插入）
void STPush(St* s, SLDataType x)
{
assert(s);
if (s->top == s->capacity)
{
SLDataType* tmp = (SLDataType*)realloc(s->a, sizeof(SLDataType)*(s->capacity)* 2);
if (tmp == NULL)
{
perror("realloc fail\n");
return;
}

else
{
s->a = tmp;
s->capacity *= 2;
}
}

s->a[s->top] = x;
s->top++;
}

//出栈
void STPop(St* s)
{

assert(s);
assert(s->top>0);
s->top--;
}

//判空
bool STEmpty(St*s)
{assert(s);
 return s->top == 0;
 }


//栈顶元素
int STTop(St* s)
{
assert(s);
    assert(s->top>0)
return s->a[(s->top-1)];
}

//栈的大小
int STSize(St* s)
{assert(s);
return s->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
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

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int SLDataType;
typedef struct Stack
{
int* a;
int top;
int capacity;
}St;

//初始化栈
void STInit(St* s);

//销毁栈
void STDestroy(St* s);

//入栈（压栈）
void STPush(St* s, SLDataType x);

//取栈顶元素
int STTop(St* s);

//判断栈是否为空
bool STEmpty(St*s);

//出栈
void STPop(St* s);

//栈大小
int STSize(St* s);
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

test.c

栈实现
#include"Stack.h"

void test()
{
St st;
STInit(&st);

STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);

while (!STEmpty(&st))
{
printf("%d ", STTop(&st));

STPop(&st);
}

//STDestroy(&st);
}
int main()
{
test();
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

OJ题括号匹配

下面来看这样一个OJ题

给定字符串且只含括号，问字符串是否有效，其实就是检查它们是否匹配，这里匹配可是要按顺序匹配啊，如 ( 只能 由 ) 与其匹配，{ 只能由
} 与其匹配 ， [ 只能由 ] 与其匹配，不能出现混淆，如果不按这样顺序匹配也是无效的
查看是否匹配我们就可以用栈来实现，当左括号就进栈，然后右括号就取出栈顶元素与当前字符比较是否匹配，
用我们刚刚写的栈作为接口来实现这道OJ题

typedef char STDataType;//由于是字符串，所以自需要在这里更改类型就可以了
typedef struct STNode
{
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* st)
{
assert(st);
st->a = (STDataType*)malloc(sizeof(STDataType)*4);

if (st->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}

st->capacity = 4;
st->top = 0;
}
//销毁
void StackDestory(ST* st)
{
assert(st);
free(st->a);
st->a = NULL;
st->top = st->capacity = 0;
}
//进栈
void StackPush(ST* st, STDataType x)
{
assert(st);
if (st->top == st->capacity)
{
STDataType* tmp = (STDataType*)realloc(st->a,st->capacity*2*(sizeof(STDataType) ));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
st->a = tmp;
st->capacity *= 2;
}
}
st->a[st->top] = x;
st->top++;
}
//出栈
void StackPop(ST* st)
{
assert(st);
assert(st->top > 0);
st->top--;
}
//判空
bool StackEmpty(ST* st)
{
assert(st);
return st->top == 0;
}
//获取栈顶元素
STDataType StackTop(ST* st)
{
assert(st);
assert(st->top > 0);
return st->a[st->top-1];
}
//获取栈的大小
int StackSize(ST* st)
{
assert(st);
return st->top;
}
//先将栈的这些接口写上

//左括号就进栈
// 右括号就将取栈顶元素与当前字符比较是否匹配
// 注意：判断栈空
// 如果栈一开始就是空的，且当前字符为右括号，那么就是不匹配
// (){}[]这种匹配形式
// 且还需要注意字符串已经匹配完了，但是栈里面还是有元素时，也是不匹配的
bool isValid(char * s)
{
  ST st;
  StackInit(&st);

  while(*s != '\0')
  {
     //当前字符为左括号进进栈
      if(*s == '(' ||*s =='{' || *s == '[')
      {
          StackPush(&st,*s);
      }
      //右括号就取栈顶元素匹配且出栈
      else
      {
        //在匹配时要确保有左括号和当前右括号匹配，就要保证栈不为空
        
        if(!StackEmpty(&st))
        { 
          //在栈不为空的情况下取出栈顶元素与当前字符匹配，看是否能匹配成功，匹配成功就将栈顶元素出栈然后字符串向后走继续匹配
            char c = StackTop(&st);
            if(c =='(' && *s==')' 
            || c=='[' &&*s ==']' 
            || c =='{' && *s=='}')
            StackPop(&st);
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }  
      s++;
  }
  //最后字符串结束之后检查栈是否为空，为空就表示所有都是匹配的，返回true,不为空就表示里面还有左括号没有参与匹配，就是匹配失败，返回false
  if(!StackEmpty(&st))
  {
      return false;
  }

  else
  return true;
}
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

栈的应用有很多，著名的有对于历史的回溯，如网页的打开，用户打开了许多网页，然后用户可以很快的回到上以个浏览页面甚至更上一个页面。但是今天关于栈的实现就到这里叭