栈和队列（8.4）

队列（8.4）"/>

栈和队列（8.4）

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

后入栈的数据先出来，例如存入1，2，3，出栈的顺序是3，2，1。

思考一下，栈的实现是用数组还是链表更合适呢？

都可以实现，但相对来说，数组更好一些，数组的尾插尾删效率更高。

typedef int STDataType;
//支持动态增长的栈
typedef struct Stack
{
    STDataType* a;
    int top;//栈顶
    int capacity;//容量
}ST;

1.2.1 栈初始化

存在一个问题，栈顶 top 应该初始化为多少？

如果初始化为 0，入栈一个数据 top ++，意味着 top 是栈顶元素的下一个位置

初始化为 -1， top 则为栈顶元素本身

这两种做法都是可以的。

完整代码：
头文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义栈静态栈（一般不用）
//#define N 10
//struct Stack
//{
//	int a[N];
//	int top;
//};typedef int STDataType;
//支持动态增长的栈
typedef struct Stack
{STDataType* a;int top;//栈顶int capacity;//容量
}ST;// 初始化栈
void STInit(ST* ps);
// 入栈
void STPush(ST* ps, STDataType x);
// 出栈
void STPop(ST* ps);
// 获取栈顶元素
STDataType STTop(ST* ps);
// 获取栈中有效元素个数
int STSize(ST* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool STEmpty(ST* ps);
// 销毁栈
void STDestroy(ST* ps);

测试文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"void TestStack1()
{//初始化结构体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);}printf("\n");STDestroy(&st);
}int main()
{TestStack1();return 0;
}

实现文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"// 初始化栈
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}// 销毁栈
void STDestroy(ST* ps)
{assert(ps);//释放free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}// 入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//如果放满，扩容if (ps->top == ps->capacity){//如果容量为空，就先赋值，如果不为空，就将容量翻倍int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//直接用realloc申请空间，当原本没有空间时，它等同于malloc//先用tmp承接开辟的空间，以免开辟失败破坏原空间STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}//放值ps->a[ps->top] = x;ps->top++;
}// 出栈
void STPop(ST* ps)
{assert(ps);//top为0说明栈空，不能继续删assert(ps->top > 0);--ps->top;
}// 获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);//top是栈顶元素的下一个位置，正好是sizereturn ps->top;
}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool STEmpty(ST* ps)
{assert(ps);//top为0栈为空return ps->top == 0;
}// 获取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);//top为0说明栈空，没有元素assert(ps->top > 0);return ps->a[ps->top - 1];
}

例题：

20. 有效的括号 - 力扣（LeetCode）

思路：由于左括号需要以正确的顺序闭合，栈的特性完美适配这一要求：我们创建一个栈（栈的基本操作我们直接cv前面的代码），将左括号入栈，然后取栈顶，与栈外的右括号相匹配，如果刚好完全匹配没有剩余，则为有效，相反，左括号或右括号中任一有剩余则为无效。

typedef char STDataType;
//支持动态增长的栈
typedef struct Stack
{STDataType* a;int top;//栈顶int capacity;//容量
}ST;// 初始化栈
void STInit(ST* ps);
// 入栈
void STPush(ST* ps, STDataType x);
// 出栈
void STPop(ST* ps);
// 获取栈顶元素
STDataType STTop(ST* ps);
// 获取栈中有效元素个数
int STSize(ST* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool STEmpty(ST* ps);
// 销毁栈
void STDestroy(ST* ps);
// 初始化栈
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}// 销毁栈
void STDestroy(ST* ps)
{assert(ps);//释放free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}// 入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//如果放满，扩容if (ps->top == ps->capacity){//如果容量为空，就先赋值，如果不为空，就将容量翻倍int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//直接用realloc申请空间，当原本没有空间时，它等同于malloc//先用tmp承接开辟的空间，以免开辟失败破坏原空间STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}//放值ps->a[ps->top] = x;ps->top++;
}// 出栈
void STPop(ST* ps)
{assert(ps);//top为0说明栈空，不能继续删assert(ps->top > 0);--ps->top;
}// 获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);//top是栈顶元素的下一个位置，正好是sizereturn ps->top;
}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool STEmpty(ST* ps)
{assert(ps);//top为0栈为空return ps->top == 0;
}// 获取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);//top为0说明栈空，没有元素assert(ps->top > 0);return ps->a[ps->top - 1];
}
bool isValid(char * s){ST st;char top;STInit(&st);while(*s){//如果为左括号if(*s=='{'||*s=='('||*s=='['){//入栈STPush(&st, *s);}//如果为右括号else{//栈内为空，说明左右括号数量不匹配if(STEmpty(&st)){//销毁空间，返回STDestroy(&st);return false;}//栈内不为空，取栈顶与栈外的右边括号匹配top=STTop(&st);//取出之后就出栈，以便于后面的元素出栈STPop(&st);//左右不匹配if(*s=='}'&&top!='{'||*s==']'&&top!='['||*s==')'&&top!='('){STDestroy(&st);return false;}}s++;}//通过遍历说明右括号完全被匹配，栈内的左括号可能有剩余，没有剩余ture,有剩余falsebool ret=STEmpty(&st);return ret;STDestroy(&st);
}