个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》
文章目录
- 前言
- 一、栈的实现思路
- 1. 结构的定义
- 2. 初始化栈(StackInit)
- 3. 入栈(StackPush)
- 4. 出栈(StackPop)
- 5. 获取栈顶元素(StackTop)
- 6. 检查栈是否为空(StackEmpty)
- 7. 销毁栈(StackDestroy)
- 二、代码实现
- 总结
前言
栈：一种特殊的线性结构，其只允许在一端进行插入，删除数据。允许操作数据的一端被称为栈顶，另一端被称为栈底。
本篇博客将要实现的是数组栈。
一、栈的实现思路
对于栈的特殊性，用数组(在数组尾部插入删除数据) 和 链表(头插头删数据)实现栈的时间复杂度都是O(1)，难度不大。
数组栈的优劣
优
- 数组支持随机访问(用下标访问数据)，许多算法需要随机访问的支持，如二分法…
- 缓存利用率高
劣
- 空间不够时要扩容
- 有时会造成空间浪费
1. 结构的定义
栈的结构非常简单
一个指向动态开辟空间的指针，一个记录实际空间大小的变量，一个记录栈顶元素的下标即可。
typedef int STDataType;typedef struct Stack{STDataType* data;int top;//栈顶下标int capacity;//空间大小}Stack;2. 初始化栈(StackInit)
data指针指向动态开辟的空间，capacity记录此时空间大小，top置为0。
- top 置0，表示栈顶数据将要插入的位置。
- top 置-1，表示此时栈顶数据的位置。
这里，采用top 置0。
//初始化栈#define SIZE 4void StackInit(Stack* ps){assert(ps);ps->data = (STDataType*)malloc(sizeof(STDataType) * SIZE);if (ps->data == NULL){perror("malloc");exit(-1);}ps->top = 0;ps->capacity = SIZE;}3. 入栈(StackPush)
因为top初始化为0，所以直接在top下标处入数据即可。但要注意，在入数据前要检查容量，如果top == capacity 要扩容。
- 此处检查容量的操作，可以封装成一个函数，但没必要，因为栈的操作只有入栈要检查容量，其它的操作并不需要检查容量，封装成一个函数反而效率减低了(函数的调用要形成函数栈帧)。
//入栈void StackPush(Stack* ps, STDataType x){assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * (ps->capacity * 2));if (tmp == NULL){perror("realloc");exit(-1);}ps->data = tmp;ps->capacity *= 2;}ps->data[ps->top] = x;ps->top++;}4. 出栈(StackPop)
top 表示的是栈顶数据将要入栈的位置，那么出栈操作，只需要让top 减 1即可。(下次入栈数据会直接覆盖)
但要注意，top = 0 时，表示栈内没有数据，不能进行出栈操作。
- 出栈操作不能获取数据
//出栈void StackPop(Stack* ps){assert(ps);assert(ps->top != 0);ps->top--;}5. 获取栈顶元素(StackTop)
top 指向的是数据将要入栈的位置，也就是栈顶数据的下一个位置。
那么要获取栈顶数据，只需要读取top – 1处即可。但要注意，如果top = 0，那么top – 1 = -1，会越界访问，所以top = 0 时，不能获取栈顶元素。
//获取栈顶元素STDataType StackTop(Stack* ps){assert(ps);assert(ps->top > 0);return ps->data[ps->top - 1];}6. 检查栈是否为空(StackEmpty)
top 指向的是数据将要入栈的位置，其数值也表示栈内数据个数。
所以我们只需要进行 top == 0 的判断，即可知道栈是否为空。
//检查栈是否为空bool StackEmpty(Stack* ps){assert(ps);return ps->top == 0;}7. 销毁栈(StackDestroy)
free掉动态开辟的空间，使capacity 置 0，top 置 0。
//销毁栈void StackDestroy(Stack* ps){assert(ps);free(ps->data);ps->top = 0;ps->capacity = 0;}二、代码实现
Stack.h 文件存放的是函数的声明，头文件的引用，结构体的定义
Stack.c 文件存放的是函数的实现
//Stack.h文件#pragma once#include #include #include #include #define SIZE 4typedef int STDataType;typedef struct Stack{STDataType* data;int top;int capacity;}Stack;//初始化栈void StackInit(Stack* ps);//入栈void StackPush(Stack* ps, STDataType x);//出栈void StackPop(Stack* ps);//获取栈顶元素STDataType StackTop(Stack* ps);//检查栈是否为空bool StackEmpty(Stack* ps);//销毁栈void StackDestroy(Stack* ps);//Stack.c文件#include "Stack.h"//初始化栈void StackInit(Stack* ps){assert(ps);ps->data = (STDataType*)malloc(sizeof(STDataType) * SIZE);if (ps->data == NULL){perror("malloc");exit(-1);}ps->top = 0;ps->capacity = SIZE;}//入栈void StackPush(Stack* ps, STDataType x){assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * (ps->capacity * 2));if (tmp == NULL){perror("realloc");exit(-1);}ps->data = tmp;ps->capacity *= 2;}ps->data[ps->top] = x;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->data[ps->top - 1];}//检查栈是否为空bool StackEmpty(Stack* ps){assert(ps);return ps->top == 0;}//销毁栈void StackDestroy(Stack* ps){assert(ps);free(ps->data);ps->top = 0;ps->capacity = 0;}总结
以上就是我对于栈的实现。
