1. 栈
1.1栈的概念及结构
栈:一种特殊的线性表，其只允许在 固定的一端 进行 插入和删除 元素操作。 进行数据插入和删除 操作的一端称为 栈顶 ，另一端称为 栈底 。栈中的数据元素遵守 后进先出 LIFO (Last in First Out) 的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈， 入数据在栈顶
出栈: 栈的删除操作叫做出栈。 出数据也在栈顶 。
栈:一种特殊的线性表，其只允许在 固定的一端 进行 插入和删除 元素操作。 进行数据插入和删除 操作的一端称为 栈顶 ，另一端称为 栈底 。栈中的数据元素遵守 后进先出 LIFO (Last in First Out) 的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈， 入数据在栈顶
出栈: 栈的删除操作叫做出栈。 出数据也在栈顶 。
特点：栈只能在栈顶进行插入和删除。
按惯例一般出栈顺序是4 3 2 1，但一定是4 3 2 1吗？答案：不一定是。
也有可能是4 3 2 1；1 2 3 4；3 2 4 1..... 但 3 1 2 4是绝对不可能的。
2.栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为 数组在尾上插入数据的代价比较小。
数组栈：完美符合栈固定一端的插入和删除的操作；
如果使用单链表来模拟实现数组栈，用头做栈顶，尾做栈底。
栈的初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}如果我们在初始化的时候top的初始值是0，top就指向4后面，如果top想指向4本身就要初始值赋值给-1。
所以想top指向栈顶数据就初始化为-1，top想指向栈顶数据的下一个位置初始化为0。
栈的销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}栈的插入
void STPush(ST* ps, Stacktype x)
{assert(ps);if (ps->top== ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;Stacktype* tmp = (Stacktype*)realloc(ps->a,sizeof(Stacktype) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}布尔值检查
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}栈的删除
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}返回栈顶元素
Stacktype STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}栈的大小
int STsz(ST* ps)
{assert(ps);return ps->top;
}完整代码实现
头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int Stacktype;
typedef struct Stack
{Stacktype* a;int top;//栈顶 相当于szint capacity;//扩容
}ST;void STInit(ST*ps);//初始化
void STDestroy(ST* ps);//销毁void STPush(ST* ps, Stacktype x);//插入
void STPop(ST* ps);//删除int STsz(ST* ps);//空间大小
Stacktype STTop(ST* ps);//栈顶
bool STEmpty(ST* ps);//布尔值检查两个源文件： 函数代码实现Stack.c与测试用例test.c
Stack.c
#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->capacity = 0;ps->top = 0;
}void STPush(ST* ps, Stacktype x)
{assert(ps);if (ps->top== ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;Stacktype* tmp = (Stacktype*)realloc(ps->a,sizeof(Stacktype) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}Stacktype STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}
int STsz(ST* ps)
{assert(ps);return ps->top;
}test.c
#include"Stack.h"
void test1()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);while (!STEmpty(&st)){int top = STTop(&st);printf("%d\n", top);STPop(&st);}STDestroy(&st);
}
int main()
{test1();return 0;
}
void test1()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);printf("%d ",STTop(&st));STPop(&st);STPush(&st, 3);STPush(&st, 4);while (!STEmpty(&st)){int top = STTop(&st);printf("%d ", top);STPop(&st);}STDestroy(&st);
}
int main()
{test1();return 0;
}
