一、栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
二、栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
具体实现代码如下：
#pragma once //Stack.h #include <stdio.h> #include <assert.h> #include <stdlib.h> // 支持动态增长的栈 //使用数组实现 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);
//Stack.c #include "Stack.h" void StackInit(Stack* ps) { assert(ps); ps->_a = NULL; ps->_top = 0; ps->_capacity = 0; } void StackPush(Stack* ps, STDataType data) { assert(ps); //容量满了 if (ps->_capacity == ps->_top) { //如果数组的容量为0，就赋值为4,；如果数组的容量不为0且容量满了，就扩大为原来容量的二倍。 int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->_a,sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->_a = tmp; ps->_capacity = newCapacity; } ps->_a[ps->_top] = data; ps->_top++; } void StackPop(Stack* ps) { assert(ps); assert(ps->_top > 0); ps->_top--; } STDataType StackTop(Stack* ps) { assert(ps); assert(ps->_top > 0); return ps->_a[ps->_top - 1]; } int StackSize(Stack* ps) { assert(ps); return ps->_top; } int StackEmpty(Stack* ps) { return ps->_top; } void StackDestroy(Stack* ps) { assert(ps); free(ps->_a); ps->_a = NULL; ps->_capacity = 0; ps->_top = 0; }
test.c #include "Stack.h" void test01() { Stack st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); while (StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } printf("\n"); StackDestroy(&st); } int main() { test01(); return 0; }
三、初学栈的练习题
题1：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路：当输入的字符串中出现左括号时就进栈，出现右括号时就与栈顶的左括号看是否相匹配。若相匹配就栈顶的左括号出栈，不匹配就直接返回false。若所有左右括号都匹配才返回true。
具体实现代码如下（C语言实现）：
//C语言实现需要自己将栈的各个功能实现 typedef char STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; void StackInit(Stack* ps) { assert(ps); ps->_a = NULL; ps->_top = 0; ps->_capacity = 0; } void StackPush(Stack* ps, STDataType data) { assert(ps); if (ps->_capacity == ps->_top) { int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->_a,sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->_a = tmp; ps->_capacity = newCapacity; } ps->_a[ps->_top] = data; ps->_top++; } void StackPop(Stack* ps) { assert(ps); assert(ps->_top > 0); ps->_top--; } STDataType StackTop(Stack* ps) { assert(ps); assert(ps->_top > 0); return ps->_a[ps->_top - 1]; } int StackSize(Stack* ps) { assert(ps); return ps->_top; } int StackEmpty(Stack* ps) { return ps->_top; } void StackDestroy(Stack* ps) { assert(ps); free(ps->_a); ps->_a = NULL; ps->_capacity = 0; ps->_top = 0; } bool isValid(char * s) { Stack st; StackInit(&st); char topVal; while(*s) { //左括号入栈 if(*s == '(' || *s == '[' || *s == '{') { StackPush(&st, *s); } //右括号与栈顶左括号进行匹配 else { //栈里已经没有左括号了，再输入一个右括号，不匹配。 if(StackEmpty(&st) == 0) { StackDestroy(&st); return false; } topVal = StackTop(&st); //不匹配返回false。 if((topVal == '(' && *s != ')') || (topVal == '[' && *s != ']') || (topVal == '{' && *s != '}')) { StackDestroy(&st); return false; } //匹配成功栈顶出栈。 StackPop(&st); } s++; } //最后栈里还剩有左括号返回false，不剩返回true。 int ret = StackEmpty(&st); if(ret == 0) return true; else return false; }
