一、概念
1、栈的定义
栈是仅限在表尾进行插入和删除的线性表。
栈又被称为后进先出（Last In First Out）的线性表，简称LIFO。
2、栈顶
栈是一个线性表，我们把允许插入和删除的一端称为栈顶
3、栈底
和栈顶相对，另一端称为栈底
二、接口
1、可写接口
（1）数据入栈
栈的插入操作，叫做入栈，也可称为进栈、压栈。
代表了两次入栈
（2）数据出栈
栈的删除操作，叫做出栈，也可以叫做弹栈
代表出了一次栈
（3）清空栈
一直出栈，直到栈为空
2、只读接口
（1）获取栈顶数据
对于一个栈来说只能获取栈顶数据，一般不支持获取其它数据
（2）获取栈元素个数
栈元素个数一般用一个额外变量存储，入栈时加一，出栈时减一
（3）栈的判空
当栈元素个数为零时，就是一个空栈，空栈不允许出栈操作
三、顺序表实现
1.数据结构定义
#define DataType int // (1)定义为整型
#define maxn 100005 // (2)代表栈的最大元素个数
struct Stack { // (3)结构体
DataType data[maxn]; // (4)栈元素存储方式-数组
int top; // (5)栈顶指针
};2.入栈
void StackPushStack(struct Stack *stk, DataType dt) { // (1)stk指向栈对象的指针
stk->data[ stk->top ] = dt; // (2)将入栈的元素放入栈中
stk->top = stk->top + 1; // (3)栈顶指针上移
}可将代码简洁写为：
void StackPushStack(struct Stack *stk, DataType dt) {
stk->data[ stk->top++ ] = dt;
}3、出栈
void StackPopStack(struct Stack* stk) {
--stk->top;
}直接将栈顶元素减一下移即可
4、清空栈
对于数组来说，我们将栈顶指针直接置为栈底，也就是数组下标为0即可，下次入栈的时候会将之前的内存重复使用
void StackClear(struct Stack* stk) {
stk->top = 0;
}5、只读接口
DataType StackGetTop(struct Stack* stk) {
return stk->data[ stk->top - 1 ]; // (1)获取栈顶元素
}
int StackGetSize(struct Stack* stk) {
return stk->top; // (2)获取栈元素个数
}
bool StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk); // (3)判断栈是否为空
}6、栈的顺序表实现源码
#define DataType int
#define bool int
#define maxn 100010
struct Stack {
DataType data[maxn];
int top;
};
void StackClear(struct Stack* stk) {
stk->top = 0;
}
void StackPushStack(struct Stack *stk, DataType dt) {
stk->data[ stk->top++ ] = dt;
}
void StackPopStack(struct Stack* stk) {
--stk->top;
}
DataType StackGetTop(struct Stack* stk) {
return stk->data[ stk->top - 1 ];
}
int StackGetSize(struct Stack* stk) {
return stk->top;
}
bool StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk);
}四、栈的链表实现
1.、数据结构定义
typedef int DataType; // (1)栈结点的数据域
struct StackNode; // (2)链表结点声明
struct StackNode { // (3)data为数据域，*next指针域
DataType data;
struct StackNode *next;
};
struct Stack {
struct StackNode *top; // (4)栈顶指针
int size; // (5)栈的元素个数，也就是链表的长度
};2、入栈
类似头插法
void StackPushStack(struct Stack *stk, DataType dt) {
// (1)创建一个结点
struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) );
insertNode->next = stk->top; // (2)当前结点指向栈顶结点
insertNode->data = dt; // (3)赋值
stk->top = insertNode; // (4)栈顶指针指向新创建的结点
stk->size++; // (5)栈元素个数加一
}3、出栈
出栈过程就是删除这个链表的头结点
void StackPopStack(struct Stack* stk) {
struct StackNode *temp = stk->top; // (1)temp指向栈顶元素
stk->top = temp->next; // (2)栈顶指针执行它的下一个结点
free(temp); // (3)将temp对应的结点释放
stk->size--; // (4)栈元素个数减一
}4、清空栈
void StackClear(struct Stack* stk) {
while(!StackIsEmpty(stk)) { // (1)栈不为空
StackPopStack(stk); // (2)执行出栈操作
}
stk->top = NULL; // (3)将栈指针置NULL
}5、只读接口
DataType StackGetTop(struct Stack* stk) {
return stk->top->data; // (1)获取栈顶元素
}
int StackGetSize(struct Stack* stk) {
return stk->size; // (2)栈元素个数
}
int StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk); //判空
}6、栈的链表实现源码
typedef int DataType;
struct StackNode;
struct StackNode {
DataType data;
struct StackNode *next;
};
struct Stack {
struct StackNode *top;
int size;
};
void StackPushStack(struct Stack *stk, DataType dt) {
struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) );
insertNode->next = stk->top;
insertNode->data = dt;
stk->top = insertNode;
stk->size++;
}
void StackPopStack(struct Stack* stk) {
struct StackNode *temp = stk->top;
stk->top = temp->next;
stk->size--;
free(temp);
}
DataType StackGetTop(struct Stack* stk) {
return stk->top->data;
}
int StackGetSize(struct Stack* stk) {
return stk->size;
}
int StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk);
}
void StackClear(struct Stack* stk) {
while(!StackIsEmpty(stk)) {
StackPopStack(stk);
}
stk->top = NULL;
stk->size = 0;
}五、两种实现的优缺点
1、顺序表实现
入栈和出栈的常数时间复杂度低，清空栈时间复杂度是O(1)
不足之处是需要预习申请好空间，而且当空间不够时需要申请空间
2、链表实现
入栈和出栈的常数时间复杂度略高，清空栈的时间复杂度为O(n)
好处是不用预先分配空间，可以一直入栈。