【数据结构】栈

Hi~！这里是奋斗的小羊，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
💥💥个人主页：奋斗的小羊
💥💥所属专栏：C语言

🚀本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

前言

栈作为一种比较特殊的存储结构，可以使用数组、单链表、双向链表等多种方法来实现，其在函数调用和递归、表达式求值、浏览器的历史记录、撤销操作、系统调用等多个场景中被广泛使用。

一、栈

1、栈的结构和概念

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素的操作。
进行元素的插入和删除的一端称为栈顶，另一端称为栈底，栈中的数据遵循后进先出的原则。
压栈：栈的插入操作叫做进栈、压栈、入栈
出栈：栈的删除操作叫做出栈

栈的结构类似于桶，只能从上面进，只能从上面出，因此我们一般只关心栈顶。
在这里插入图片描述

2、实现栈的方法选择

了解的栈的结构，接下来就要考虑如何实现栈。
在这之前我们学习了顺序表（底层就是数组）和链表，链表又分单链表和双向链表，用哪个方法实现效果最好呢？

上篇文章中我们简单地列举的顺序表和链表的比较，如下：

	顺序表	链表（双向链表）
存储空间上	逻辑、物理上都连续	逻辑上连续、物理上不一定连续
随机访问	复杂度O(1)	复杂度O(N)
任意位置插入或删除数据	需要挪动数据，复杂度O(N)	只需要改变指针指向
插入	动态顺序表，空间不够时扩容，扩容本身就有消耗，还容易空间浪费	没有容量的概念
应用场景	数据高效存储+频繁访问	任意位置频繁插入、删除数据
缓存利用率	高	低

其中我们关键看缓存利用率，简单地说缓存利用率是指计算机系统中缓存（如CPU缓存、内存缓存等）被有效利用的程度。
CPU执行指令运算要访问数据，会先去缓存中找有没有这个数据，如果有，说明缓存命中了；如果没有，说明缓存未命中，就从主存中读取一段连续内存空间的数据到缓存，继续找。
而我们知道在物理结构上顺序表是连续的，链表不连续。那从主存中读取一段连续内存空间的数据到缓存时链表读取到的很可能不是我们想要的数据，从而造成缓存污染。
虽然顺序表在扩容的时候时间和空间都有消耗，而且还容易存在空间浪费，但是动态扩容也不是说很频繁，只有在空间不够时才扩容。
其实在实现栈上顺序表和链表只是五十步和百步的区别，只是相对而言顺序表更好一点。

3、栈的实现

3.1完整代码

用顺序表的方法实现栈，和我们之前实现的顺序表没多大区别，只是栈中的元素只能从栈顶进从栈顶出，遵循后进先出的原则。
这里我们就先展示用顺序表的方法实现的栈的完整代码，其中的细节再一一介绍。
stack.h:

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int st_data_type;typedef struct stack
{st_data_type* arr;int top;int capacity;
}stack;//初始化和销毁
void stack_init(stack* pst);
void stack_destroy(stack* pst);//入栈和出栈
void stack_push(stack* pst, st_data_type x);
void stack_pop(stack* pst);//取出栈顶元素
st_data_type stack_top(stack* pst);//判空
bool stack_empty(stack* pst);//获取数据个数
int stack_size(stack* pst);

stack.c:

#include "stack.h"//初始化
void stack_init(stack* pst)
{assert(pst);pst->arr = NULL;pst->top = pst->capacity = 0;
}//入栈
void stack_push(stack* pst, st_data_type x)
{assert(pst);if (pst->capacity == pst->top){int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;st_data_type* tmp = (st_data_type*)realloc(pst->arr, newcapacity * sizeof(st_data_type));if (tmp == NULL){perror("realloc fail!");return 1;}pst->arr = tmp;tmp = NULL;pst->capacity = newcapacity;}pst->arr[pst->top] = x;pst->top++;
}//出栈
void stack_pop(stack* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}//取出栈顶元素
st_data_type stack_top(stack* pst)
{assert(pst);assert(pst->top > 0);return pst->arr[pst->top-1];
}//销毁
void stack_destroy(stack* pst)
{assert(pst);free(pst->arr);pst->arr = NULL;pst->capacity = pst->top = 0;
}//判空
bool stack_empty(stack* pst)
{assert(pst);return pst->top == 0;
}//获取元素个数
int stack_size(stack* pst)
{assert(pst);return pst->top;
}

test.c:

#define  _CRT_SECURE_NO_WARNINGS#include "stack.h"void test()
{stack st;stack_init(&st);//...stack_push(&st, 1);stack_push(&st, 2);stack_push(&st, 3);stack_push(&st, 4);stack_destroy(&st);
}int main()
{test();return 0;
}

可以看到因为栈结构的特殊，栈的实现比之前的顺序表简单多了，少了很多接口（函数）。
其中初始化、入栈、销毁函数跟之前实现的顺序表是一样的，这里就不再赘述。

3.2特殊的接口

出栈：

//出栈
void stack_pop(stack* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}

因为出栈就是删除栈顶的一个元素数据，所以出栈的实现只需要将top--就行了。

取出栈顶元素数据：

//取出栈顶元素
st_data_type stack_top(stack* pst)
{assert(pst);assert(pst->top > 0);return pst->arr[pst->top-1];
}

在取栈顶元素的时候，极其容易写出：return pst->arr[pst->top]; 这条代码，因为我们下意识思维会认为最后一个元素数据的下标为top，其实不是的，这里跟顺序表中的size一样表示的是栈中元素的个数，所以栈中最后一个元素的下标是top-1。

判空、获取数据个数：

//判空
bool stack_empty(stack* pst)
{assert(pst);return pst->top == 0;
}//获取元素个数
int stack_size(stack* pst)
{assert(pst);return pst->top;
}

如果栈中没有数据，则pst->top == 0;为真，返回ture，反之则返回false。

3.3访问栈的所有元素

由于栈后进先出的特殊结构，访问栈的所有元素我们不能像顺序表那样利用下标循环打印，应该使用下面这种方式：

while (!stack_empty(&pst))
{printf("%d ", stack_top(&pst));stack_pop(&pst);
}

拿到栈顶的元素后再拿下一个元素前需要先将栈顶的元素弹出（也就是删除），才能访问到下一个元素。
但是这也导致了一个问题，就是我们访问完栈中的所有元素后栈也就空了，不过不用担心这是正常现象。

这里有个问题: 栈的原则是后进先出，如果我们入栈的顺序是1、2、3、4，那出栈的顺序一定是4、3、2、1吗？
其实不是的，因为我们可以边进边出。

#define  _CRT_SECURE_NO_WARNINGS#include "stack.h"void test()
{stack st;stack_init(&st);stack_push(&st, 1);printf("%d ", stack_top(&st));stack_pop(&st);stack_push(&st, 2);printf("%d ", stack_top(&st));stack_pop(&st);stack_push(&st, 3);stack_push(&st, 4);while (!stack_empty(&st)){printf("%d ", stack_top(&st));stack_pop(&st);}stack_destroy(&st);
}int main()
{test();return 0;
}

请添加图片描述

4、用栈解决括号匹配的问题

题目：有效的括号—leetcode

题目描述：

在这里插入图片描述

我们怎么使用栈的特点来解决这个问题呢？

解题思路：
返回false的情况有两种，一种是数量不匹配，一种是顺序不匹配。
栈有后进先出的特点，而括号匹配的问题首先需要找到若干个左括号，然后再找右括号进行一一配对，如果全部配对成功则返回true，否则返回false。
也就是说当我们拿到字符串中的第一个字符，如果是左括号则压栈，如果是右括号则出栈与右括号配对，只要有一次配对不上就返回false。

有几个需要注意的点或特殊情况：

如果拿到的第一个字符就是右括号（也就是栈为空时），这时则直接返回false
当在字符串中取到‘\0’退出循环后，还要再判断一下栈是否为空，因为有可能栈内还剩有压进去的左括号
在每次返回前都要先销毁栈，避免内存泄漏

解题过程如下：

bool isValid(char* s) {//创建栈并初始化stack st;stack_init(&st);while (*s != '\0'){//左括号则压栈if (*s == '(' || *s == '[' || *s == '{'){stack_push(&st, *s);}//右括号则出栈，配对else{if (stack_empty(&st))//拿到的第一个字符就是右括号{stack_destroy(&st);return false;}//取char top = stack_top(&st);//删stack_pop(&st);//如果不配对则直接返回falseif (top == '(' && *s != ')'|| top == '[' && *s != ']'|| top == '{' && *s != '}'){stack_destroy(&st);//避免内存泄漏return false;} }s++;}//判断栈内是否还有未配对的左括号bool ret = stack_empty(&st);stack_destroy(&st);return ret;
}