栈作为线性结构中的一种，与线性表其实并无太大区别，无非就是在线性表的基础上加了一个限制罢了，那么，本篇文章将从栈的实现和一个简单的应用来介绍栈。
栈的概念
栈是一种特殊的线性表，其只能在固定的一端进行插入和删除操作，这是栈顶，而另一端叫栈底。栈的数据元素遵循LIFO即后进先出（Last In First Out ）的规则。
常见术语
压栈/入栈/进栈：栈的插入操作，只能在栈顶进行。
出栈：栈的删除操作，也只能在栈顶进行。
栈的实现
作为一种特殊的线性表，栈也有两种实现方式，即顺序栈和链栈。由于栈的特性：只能从一端进行插入和删除；因此采用顺序表的形式实现操作时更加便捷。
栈的定义
实现顺序栈时，由于静态数组将数组大小写死了，因此不推荐使用，而是考虑动态数组。
//静态版本
//#define N 100
//typedef int STDataType;
//
//typedef struct Stack
//{
// STDataType a[N];
// int top;
// size_t capacity;
//}Stack;
//动态版本
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
size_t capacity;
}Stack;
栈的常见接口如下：
void StackInit(Stack* ps);//初始化栈
void StackDestroy(Stack* ps);//销毁栈
void StackPush(Stack* ps, STDataType x);//进栈操作
void StackPop(Stack* ps);//出栈操作
bool StackEmpty(Stack* ps);//判空操作
size_t StackSize(Stack* ps);//求栈的大小
STDataType StackTop(Stack* ps);//读取栈顶元素
下面我们来一一实现：
1.初始化栈
注意：初始化时top置为0，表面top所指为栈顶的后面一个位置。
void StackInit(Stack* ps)
{
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
2.销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);//防止ps为NULL
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
3.进栈
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)//考虑增容
{
//分情况：capacity 为0或不为0
size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
Stack* tmp = (Stack*)realloc(sizeof(Stack) * newcapacity);
if (tmp == NULL)//增容失败
{
perror("realloc");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;//更新容量
}
ps->a[ps->top++] = x;//这里进栈时top要先用后加
}
4.出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));//出栈操作要保证栈非空
ps->top--;
}
5.判空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
6.求栈的大小
size_t StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
7.读取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
return ps->a[ps->top - 1];
}
栈的应用
这里用一个题来简单体验一下栈的实际应用。
括号匹配问题：
leetcode题目链接
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
由于所给括号只有三组，这里采用栈可以轻松解决。
思路：遇到‘（’ ，‘[’, ‘{’, 即左括号则将其压栈处理，遇到‘）’， ‘]’ , ‘}’ 即右括号时则将栈顶元素出栈，若不能匹配则返回false，若匹配则继续匹配下一组，直到匹配完全部括号则返回true。
参考代码：
typedef char STDataType;
typedef struct Stack
{
STDataType* a;
int top;
size_t capacity;
}Stack;
void StackInit(Stack* ps);//初始化栈
void StackDestroy(Stack* ps);//销毁栈
void StackPush(Stack* ps, STDataType x);//进栈操作
void StackPop(Stack* ps);//出栈操作
bool StackEmpty(Stack* ps);//判空操作
size_t StackSize(Stack* ps);//求栈的大小
STDataType StackTop(Stack* ps);//读取栈顶元素
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackDestroy(Stack* ps)
{
assert(ps);//防止ps为NULL
if(ps->a)
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)//考虑增容
{
//分情况：capacity 为0或不为0
size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
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;//这里进栈时top要先用后加
}
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));//出栈操作要保证栈非空
ps->top--;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
size_t StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
return ps->a[ps->top - 1];
}
bool isValid(char * s)
{
Stack st;
StackInit(&st);//初始化栈
int match = true;//记录下括号匹配状态
while(*s)//遍历s，若为左括号则压栈，若为右括号则将栈顶元素出栈进行匹配
{
if(*s == '('
|| *s == '['
|| *s == '{')//左括号则压栈
{
StackPush(&st, *s);
}
else//右括号则取栈顶元素看是否匹配
{
if(!StackEmpty(&st))
{
char op = StackTop(&st);
if((*s == ')' && op != '(')
|| (*s == ']' && op != '[')
|| (*s == '}' && op != '{'))//括号不匹配，将match置为false
{
match = false;
}
StackPop(&st);
}
else//栈空而s仍进入了循环，说明右括号多于左括号，返回false
{
match = false;
}
}
s++;
}
if(!StackEmpty(&st))//左括号多于右括号的情况
{
match = false;
}
StackDestroy(&st);//防止内存泄漏
return match;
}
这题思路不难，但是实现时有几个细节需要注意：
1.遍历s时要记得迭代
2.通过列举所有左括号与右括号不匹配的情况来简略代码
3.需要考虑左括号多于右括号以及右括号多于左括号的情况
4.每次读取完栈顶元素时要记得进行出栈操作。