数据结构——栈的实现

本日，我们来写一下关于栈的博文。
1.首先我们先了解一下什么是栈？
一：概念：

栈：一种特殊的线性表，其只允许在固定的一端举行插入和删除元素操作。
举行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素服从后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶

为了更好的理解，我们画个图辅助了解一下吧。

详细解释：
你看上面：
想要加数据的时候，就在栈顶入数据，此时叫压栈
再看，想要删数据的时候，是不是也得再栈顶出？此时叫出栈
同时，你是不是就发现了无论它是加照旧删，遵循的规律都是后进先出
 
二：栈的实现

好了，有了上面的认识后，就可以举行实现部门了。
在此之前，我们首先得考虑考虑，我们得接纳什么情势呢？是数组照旧链表呢？
一般来说，两者都是可以的，但是利用数组的情势更优一些，对此我们在这里就以链表来实现它。
链式栈：可以用双向链表，但最好用单链表（用头那边当栈顶）
如果用的是数组的话，一般是尾部当栈顶
其实，感觉这里跟序次表那些都差不多呢~
好了，至此，正式开始吧：
建立数组栈结构：

1. typedef struct Stack
2. {
3.         STDataType* a;
4.         int top;
5.         int capacity;
6. }ST;

复制代码

初始化部门

1. void STInit(ST* ps)
2. {
3.         assert(ps);
5.         ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
6.         if (ps->a == NULL)
7.         {
8.                 perror("malloc fail");
9.                 return;
10.         }
12.         ps->capacity = 4;
13.         ps->top = 0;   // top是栈顶元素的下一个位置
15.         //ps->top = -1;   // top是栈顶元素位置
16. }

复制代码

但是这里有些问题：top指向的是栈顶的下一个，先放数据再++
照旧栈顶位置，一开始就在0这个位置出发。先++再放数据。给-1位置
看下图：

那么，肯定有人疑惑为什么呢？
答：由于当初始化给0时，就代表栈顶有元素了，给-1的时候就表现栈为空。
你也可以那样想到数组那个，你看：
数组[0]的时候它是不是就代表已经有一个元素了，这个元素相当于就在第一个位置那样？
同样，当你希望初始化时不需要有数据（相当于联想到数组），当0时有一个数字，这时，你给-1，是不是相当于没有数据了？
有人有问了，当你给-1的话，不会酿成野指针了吗？
其实这个问题不用担心，由于这里给-1的时候就要判断了。这里0去访问是合法的，但是刚初始化没有push的内容，就会有问题了，所以如果利用0的话，还需要做出处理。

总的来说，利用0照旧-1都是没有强制性要求你，都是可以的，看个人喜好了。
这里利用的0的情势。

烧毁部门：

1. void STDestroy(ST* ps)
2. {
3.         assert(ps);
5.         free(ps->a);
6.         ps->a = NULL;
7.         ps->top = 0;
8.         ps->capacity = 0;
9. }

复制代码

这里烧毁的时候，利用-1和0，ps->top就会有一点的区别了。

插入部门

1. void STPush(ST* ps, STDataType x)
2. {
3.         assert(ps);
5.         if (ps->top == ps->capacity)
6.         {
7.                 STDataType* tmp = (STDataType*)realloc(ps->a,
8.                         sizeof(STDataType) * ps->capacity*2);
9.                 if (tmp == NULL)
10.                 {
11.                         perror("realloc fail");
12.                         return;
13.                 }
15.                 ps->a = tmp;
16.                 ps->capacity *= 2;
17.         }
19.         ps->a[ps->top] = x;
20.         ps->top++;
21. }

复制代码

解释：
在插入之前，我们先举行判断它是否已经满了，满了的话就扩容，反之不用。
插入的话，也比较简朴，由于它只能在栈顶插入嘛。由于这里利用的0的情势
所以就直接找到栈顶的位置，插进去就可以了。

1. ps->a[ps->top] = x;
2.         ps->top++;

复制代码

删除部门

1. void STPop(ST* ps)
2. {
3.         assert(ps);
4.         assert(!STEmpty(ps));
6.         ps->top--;
7. }

复制代码

也由于只能栈顶先删，所以就减减top就可以了。

得出栈的大小部门

1. int STSize(ST* ps)
2. {
3.         assert(ps);
5.         return ps->top;
6. }

复制代码

由于利用的是数组栈，我们又知道，数组是连续的，所以直接返回top所在的位置，就可以得出大小了。
判断空部门

1. bool STEmpty(ST* ps)
2. {
3.         assert(ps);
5.         return ps->top == 0;
6. }

复制代码

由于利用的是0，即栈的下一个，当它栈顶的位置是0的时候，就代表它没有数据了，也就是空。
此时返回就好了。
另外，我们上面的删是不是也得判断一下是否空的情况对不对？如果它已经空了，那么还删的话，有什么意义？对吧？
所以可以看到上面的删除部门，我们利用了断言它不为空。

找尾部门

1. STDataType STTop(ST* ps)
2. {
3.         assert(ps);
4.         assert(!STEmpty(ps));
6.         return ps->a[ps->top - 1];
7. }

复制代码

这是说，如果你要找尾的话，数组嘛，所以直接找下标就可以了。

好了，功能已经介绍完了。

现在来附上完整代码：
Stack部门

1. #define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"void STInit(ST* ps){        assert(ps);        ps->a = (StDatatype*)malloc(sizeof(StDatatype) * 4);        if (ps->a == NULL)        {                perror("malloc fail");                return;        }        ps->top = 0;        ps->capacity = 4;}void Destory(ST* ps){        assert(ps);        free(ps->a);        ps->a = NULL;        ps->capacity = 0;        ps->top = 0;}void STPush(ST* ps,StDatatype x){        if (ps->top== ps->capacity)        {                StDatatype* temp =(StDatatype*) realloc(ps->a, sizeof(StDatatype) * ps->capacity * 2);                if (temp == NULL)                {                        perror("realloc fail");                        return 0;                }                ps->a = temp;                ps->capacity *= 2;        }        ps->a[ps->top] = x;
2.         ps->top++;}void STPop(ST* ps)
3. {
4.         assert(ps);
5.         assert(!STEmpty(ps));
7.         ps->top--;
8. }
9. int size(ST* ps){        assert(ps);        return ps->top;}bool STEmpty(ST* ps)
10. {
11.         assert(ps);
13.         return ps->top == 0;
14. }StDatatype STTop(ST* ps){        assert(ps);        assert(!STEmpty(ps));        return ps->a[ps->top-1];}

复制代码

Stack.h部门

1. #pragma once
2. #include<stdio.h>
3. #include<assert.h>
4. #include<stdlib.h>
5. #include<stdbool.h>
6. //
7. //typedef struct Stack
8. //{
9. //        int a[20];
10. //        int top;
11. //};
13. typedef char StDatatype;
14. typedef struct Stack
15. {
16.         StDatatype* a ;
17.         int top;
18.         int capacity;
20. }ST;
22. //ʼ
23. void STInit(ST* ps);
24. void Destory(ST* ps);
25. void STPush(ST* ps,StDatatype x);
26. void STPop(ST* ps);
27. int size(ST* ps);
28. bool STEmpty(ST* ps);
29. StDatatype STTop(ST* ps);
30. bool isValid(char* s);

复制代码

测试部门：

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include "Stack.h"
3. int main()
4. {
5.         ST st;
6.         STInit(&st);
7.         STPush(&st,'(');
8.         STPush(&st, ']');
9.         bool ret = isValid(&s);
10.        
11.         if (ret == "false")
12.         {
13.                 printf("no");
14.         }
15.         else
16.         {
17.                 printf("yes");
18.         }
19.        
21.         Destory(&st);
22.         return 0;
23. }

复制代码

好了，到了每次鸡汤部门：
你每一步都会算数的！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。