关于栈的简单讲解

哈喽，小伙伴们大家好呀，今天给大家带来栈、队列的那些知识点。

栈的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。

总结

一种线性表，进行数据插入和删除的一端为栈顶

遵循原则

栈的实现

#include<stdio.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 StackPush(Stack* ps, STDataType x);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);

首先还是一样的初始化栈，关于初始化，我们之前已经讲过了许多次了，那么今天我们再来最后一次写初始化。

总结一下初始化和销毁部分主要写的内容

初始化部分：对于结构体的数组或者指针等进行解引用时通常置为空也就是NULL,另外对于一些如int类型的赋值为0。

销毁部分：与初始化部分相似，但从理论上则与初始化互逆。

温馨提醒：free完一个结构体变量后就要讲其置为空，且int类型还原为0，是一个好习惯哦！

入栈部分

这个与先前的链表尾插的思路相似

思路：先判ps指针不为空，再通过判断栈顶（top）是否与空间相等，如果相等，增加间，再将newcapacity传给capacity,将tmp给数组a，最后把x给到数组p->a[ps->top]，并且栈顶元素个数也要++

出栈部分

相较于入栈而言，出栈就变得很简单。出栈顾名思义就是从栈内将元素一个一个得往外移出，并且移出时栈顶元素个数要减减

那么想要元素出栈，就要先获取栈顶元素，那么如何获取呢？

栈顶元素获取

思路：先断言指针不为空，再返回数组元素

栈顶元素的有效个数

思路：先断言指针不为空再返回ps->top

检测栈是否为空

思路：直接返回ps->top ==0;即可，因为bool类型会对给出的条件做出判断，如果为真则返回0，反之，则返回一个不为0的数。

例题讲解

题目要求：左括号与右括号若匹配，则返回true,反之，返回，false

思路：在有栈的情况下通过循环依次将左括号入栈(注意不能少了s++)，若遇到非左括号的则进入判空环节，如果非空，则取栈然后进行与右括号匹配(注意：取完后要删除)，若匹配成功则返回true，否则销毁并返回false，反之如果为空，则销毁并返回false

源代码：

typedef char STDataType;

typedef struct Stack

{

STDataType* a;

int top; // 栈顶

int capacity; // 容量

}Stack;

// 初始化栈

void StackInit(Stack* ps);

// 入栈

void StackPush(Stack* ps, STDataType x);

// 出栈

void StackPop(Stack* ps);

// 获取栈顶元素

STDataType StackTop(Stack* ps);

// 获取栈中有效元素个数

int StackSize(Stack* ps);

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0

bool StackEmpty(Stack* ps);

// 销毁栈

void StackDestroy(Stack* ps);

void StackInit(Stack* ps)

{

assert(ps);

ps->a = NULL;

ps->capacity = 0;

ps->top = 0;

}

void StackPush(Stack* ps, STDataType x)

{

assert(ps);

if (ps->top == ps->capacity)

{

int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));

if (tmp == NULL)

{

perror("realloc fail");

exit(1);

}

ps->capacity = newcapacity;

ps->a = tmp;

}

ps->a[ps->top] = x;

ps->top++;

}

STDataType StackTop(Stack* ps)

{

assert(ps);

//assert(ps->top > 0);

return ps->a[ps->top - 1];

}

void StackPop(Stack* ps)

{

assert(ps);

ps->top--;

}

bool StackEmpty(Stack* ps)

{

assert(ps);

return ps->top == 0;

}

int StackSize(Stack* ps)

{

assert(ps);

return ps->top;

}

void StackDestroy(Stack* ps)

{

assert(ps);

free(ps->a);

ps->a = NULL;

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

}

bool isValid(char* s) {

Stack st;

StackInit(&st);

while(*s)

{

if(*s == '(' || *s == '[' || *s == '{')

{

StackPush(&st, *s);

}

else

{

if(StackEmpty(&st))

{

StackDestroy(&st);

return false;

}

char top = StackTop(&st);

StackPop(&st);

if((top == '(' && *s != ')')

|| (top == '[' && *s != ']')

|| (top == '{' && *s != '}') )

{

StackDestroy(&st);

return false;

}

++s;

}

bool ret = StackEmpty(&st);

StackDestroy(&st);//这里的销毁别忘了哦

return ret;

}

本文总结

1.初始化与销毁通用思路模板

初始化：对于像指针等，初始化时置为空即可，也就是NULL；对于像int类型的变量一般初始化为0。

销毁：第一步先判空，再使用free释放指针，之后就与初始化相同

2.入栈与出栈(取栈)通用思路模板

入栈：

入栈时，先思考是否已经有了足够空间，若无空间则使用malloc或者reallocation申请空间或增加空间容量，申请或扩容成功后，要将该空间转移到需要该空间的临时创建的变量中，再对应赋值给需要该空间的原变量和原空间。

eg.申请的新空间newcapacity, 新创建的数组tmp

↓ ↓

pq->capacity = newcapacity pq->a = tmp

3.判断空间是否充足代码模板

if (ps->top == ps->capacity)
{
   int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
   STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
   if (tmp == NULL)
   {
       perror("realloc fail");
       exit(1);
   }
   ps->capacity = newcapacity;
   ps->a = tmp;
}

那么本篇文章的内容就先给大家讲到这里，喜欢我的朋友可以给我点个赞哦，我们下期见！