一、栈的概念和结构
栈：
一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
数组实现栈：
链表实现栈：
二、关于栈的选择题试练
试题一
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
A、 1 2 3 4 5 A B C D E B、E D C B A 5 4 3 2 1
C、 A B C D E 1 2 3 4 5 D、5 4 3 2 1 E D C B A
解析：对于栈而言，栈的元素遵守先进后出，后进先出的原则；题目进栈的顺序是1、2、3、4、5、A、B、C、D、E，那么逆序就是它出栈的顺序，即：E、D、C、B、A、1、2、3、4、5；所以本题选 B;
试题二
2.若进栈序列为 1, 2, 3, 4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（ ）。
A 1, 4, 3, 2 B 2, 3, 4, 1
C 3, 1, 4, 2 D 3, 4, 2, 1
解析
所以本题选 C
三、静态栈与动态栈的选用
我们可以采用静态栈结构或者动态栈结构；静态栈需要我们开辟好足够的空间，这不是我们能控制的，如果用栈存储数据量小，开辟的空间又很大，这时候就存在浪费了；如果开辟的空间很小，又不够存放数据；我们通常使用的是动态增长的栈，只要空间不够就会增容；本次我们主要实现动态栈；
静态栈：
typedef int STDataType; #define N 1000 typedef struct Stack { STDataType a[N]; int top; //栈顶 }Stack;
动态栈：
typedef int STDataType; typedef struct Stack { STDataType* a; int top; //栈顶 int capacity; }ST;
四、栈的各个接口函数的实现
1.栈的初始化
//栈的初始化 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; }
2.在栈顶插入数据 （入栈）
//在栈顶插入数据 void StackPush(ST* ps, STDataType x) { assert(ps); //插入数据时如果空间不够，就增容 if (ps->top == ps->capacity) { //我们创建的栈刚开始没有空间，可以采用三目操作符，先给它4个空间的大小； int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x;//把数据压栈（放到栈顶） ps->top++;//记录数据的个数，同时也能知道栈顶得的数据值是多少 }
3.栈顶数据的删除（出栈）
//栈顶数据的删除 void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps));//判断栈是否为空，为空则不能删除； ps->top--; }
4.取栈顶的数据
//取栈顶的数据 STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1];//这里top是数据的个数，减去1就是对应栈顶的数据的下标 }
5.栈的元素个数
//栈的元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; }
6.判断栈是否为空
//判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); //不需要遍历数组，直接给有个判断表达式，如果top为0就说明栈为空 return ps->top == 0; }
7.栈的销毁
//栈的销毁 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; }
五、源代码
Stack.h
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top;//栈顶 int capacity; }ST; //栈的初始化 void StackInit(ST* ps); //栈的销毁 void StackDestroy(ST* ps); //在栈顶插入数据 void StackPush(ST* ps, STDataType x); //栈顶数据的删除 void StackPop(ST* ps); //取栈顶的数据 STDataType StackTop(ST* ps); //栈的元素个数 int StackSize(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps);
Stack.c
#include "stack.h" //栈的初始化 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } //栈的销毁 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } //在栈顶插入数据 void StackPush(ST* ps, STDataType x) { assert(ps); //插入数据时如果空间不够，就增容 if (ps->top == ps->capacity) { //我们创建的栈刚开始没有空间，可以采用三目操作符，先给它4个空间的大小； int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x;//把数据压栈（放到栈顶） ps->top++;//记录数据的个数，同时也能知道栈顶得的数据值是多少 } //栈顶数据的删除 void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps));//判断栈是否为空，为空则不能删除； ps->top--; } //取栈顶的数据 STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1];//这里top是数据的个数，减去1就是对应栈顶的数据的下标 } //栈的元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; } //判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); //不需要遍历数组，直接给有个判断表达式，如果top为0就说明栈为空 return ps->top == 0; }
test.c
#include "stack.h" void StackTest1() { ST st; StackInit(&st); //1 2 3 4入栈 StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); while (!StackEmpty(&st)) { printf("%d ", StackTop(&st));//打印栈就是依次取栈顶的数据，打印出来4 3 2 1 StackPop(&st); } //用完后记得销毁栈 StackDestroy(&st); } int main() { StackTest1(); return 0; }
