栈的顺序表实现
1. 栈的概念及结构
1.1 概念
1.2 栈顶
1.3 栈底
2. 接口
2.1 可写接口
1）数据入栈
2）数据出栈
3）清空栈
2.2 只读接口
1）获取栈顶数据
2）获取栈元素个数
3）栈的判空
3. 栈的顺序表实现
3.1 Stack.h
3.2 Stack.c
3.3 Test.c
4. 总结
1. 栈的概念及结构
1.1 概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
即：栈是仅限在表尾进行插入和删除的线性表。
- 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
- 出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
1.2 栈顶
栈是一个线性表，我们把允许插入和删除的一段称为栈顶。
1.3 栈底
和栈顶相对，另一端称为栈底，实际上，栈底的元素我们不需要关心。
2. 接口
2.1 可写接口
1）数据入栈
栈的插入操作，叫做 入栈，也可称为 进栈、压栈。如下图所示，代表了三次入栈操作：
代码实现：
void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; 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] = x; ps->top++; }
由于栈是由顺序表实现的，因此当空间不够需要扩容，入栈之后top需要+1为了记录下一个入栈位置。
2）数据出栈
栈的删除操作，叫做 出栈，也可称为 弹栈。如下图所示，代表了两次出栈操作：
void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; }
弹一次让top减一即可。
3）清空栈
一直 出栈，直到栈为空，如下图所示：
即一直出栈到没有元素即可。
//想要直接清除栈也可以直接销毁，此代表着程序结束 void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
2.2 只读接口
1）获取栈顶数据
对于一个栈来说只能获取 栈顶 数据，一般不支持获取 其它数据。
STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; }
2）获取栈元素个数
栈元素个数一般用一个额外变量存储，入栈 时加一，出栈 时减一。这样获取栈元素的时候就不需要遍历整个栈。通过 **O ( 1 )**的时间复杂度获取栈元素个数。
int StackSize(ST* ps) { assert(ps); return ps->top; }
3）栈的判空
当栈元素个数为零时，就是一个空栈，空栈不允许 出栈 操作。
bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
3. 栈的顺序表实现
对于顺序表，在 C语言 中表现为 数组，在进行 栈的定义 之前，我们需要考虑以下几个点：
1）栈数据的存储方式，以及栈数据的数据类型；
2）栈的大小；
3）栈顶指针；
此类信息都在对应的Stack.h头文件中定义
3.1 Stack.h
#pragma once #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 StackDestory(ST* ps);//栈的销毁 void StackPush(ST* ps, STDataType x);//入栈 void StackPop(ST* ps);//出栈 STDataType StackTop(ST* ps);//获取栈顶元素 bool StackEmpty(ST* ps);//判断栈是否为空 int StackSize(ST* ps);//计算栈的数据个数
3.2 Stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void StackInit(ST* ps) { ps->a = NULL; ps->top = ps->capacity = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; 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] = 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]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; }
3.3 Test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void TestStack() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); printf("%d ", StackTop(&st)); StackPop(&st); printf("%d ", StackTop(&st)); StackPop(&st); printf("%d ", StackTop(&st)); StackPush(&st, 4); StackPush(&st, 5); printf("\n"); while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } printf("\n"); } int main() { TestStack(); return 0; }
4. 总结
栈的学习内容就到这里，下一章会是队列的实现以及oj题的讲解。
