【数据结构】栈的基本概念 | 从零开始实现数组栈 | 画图解析 | 数组栈与链式栈
前言:
本章我们将学习 "栈" ,首先介绍栈的概念和结构,然后我们将着重讲解数组栈的实现。我们从零开始写数组栈的接口,并从零开始步步解读。本章旨在筑牢栈知识点的基础,对后续的刷题有着很大的帮助。
一、栈(stack)
0x00 栈的概念
📚 栈的概念:
① 栈是一种特殊的线性表,它只允许在固定的一端进行插入和删除元素的操作。
② 进行数据插入的删除和操作的一端,称为 栈顶 。另一端则称为 栈底 。
③ 栈中的元素遵守后进先出的原则,即 LIFO原则(Last In First Out)。
压栈:栈的插入操作叫做 进栈 / 压栈 / 入栈 ,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
0x01 栈的结构
🔍 栈的结构:
0x02 数组栈和链式栈
📚 实现栈无非就两种结构:数组结构 和 链式结构,两种结构都可以实现。
❓ 数组栈和链式栈哪种结构更好?
💡 相对而言数组的结构实现更优,尾插尾删的效率高,缓存利用率高,它的唯一缺点只是增容,但是增容1次扩2倍对栈来说本身就比较合理,是无伤大雅的。而链式栈虽然不会空间浪费,用一个 malloc 申请一个,但是链式栈存在一个致命的缺点:单链表不好出数据,必须要实现双向链表,否则尾上删除数据将会异常麻烦。
📌 如果硬要使用链式栈:
① 如果用尾做栈顶,尾插尾删,要设计成双向链表,否则删数据效率低。
② 如果用头做栈顶,头插头删,就可以设计成单链表。
🔺 总结:本章栈的实现将采用数组结构!
二、栈的定义
0x00 动态栈
📌 注意:本章将采用动态栈实现!
typedef int StackDataType;
typedef struct Stack {
StackDataType* array; //数组
int top; //栈顶
int capacity; //容量
} Stack;
🔑 解读:顺序表相信大家已经很熟了,这里和顺序表没啥两样。创建结构体,结构体有三个变量,array 是用来存放数据的数组。top 用来表示栈顶,这里相当于顺序表中的 size 变量。capacity 表示栈的容量。
0x01 静态栈
📚 简单介绍下静态栈:
typedef char StackDataType;
#define N 10
typedef struct Stack {
StackDataType _array[N]; //数组
int _top; //栈顶
} Stack;
🔑 解读:N 给多了浪费给少了又不够用,所以静态栈在实际中是不实用的。静态栈满了就不能扩大了,而动态栈是 malloc 出来的,不够了可以 realloc 扩容。虽然不实用,但是我们也得认识它,知道有这么一个东西,以后见到不至于觉得奇怪。
0x02 接口函数
📚 这是需要实现几个接口函数:
void StackInit(Stack* pst);
void StackDestroy(Stack* pst);
bool StackIsEmpty(Stack* pst);
void StackPush(Stack* pst, StackDataType x);
void StackPop(Stack* pst);
StackDataType StackTop(Stack* pst);
int StackSize(Stack* pst);
🔑 解读:相信细心的小伙伴发现了,StackIsEmpty 函数的类型是布尔。C语言如果想使用布尔值需要引入头文件 #include <stdbool.h> 。
三、栈的实现
0x00 初始化栈(StackInit)
💬 Stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int StackDataType;
typedef struct Stack {
StackDataType* array; //数组
int top; //栈顶
int capacity; //容量
} Stack;
void StackInit(Stack* pst);
🔑 解读:大家学到这里想必已然轻车熟路,应该知道需要引入哪些头文件了,动态内存开辟需要引入 stdlib.h,断言需要引入 assert,使用布尔值需要引入 stdbool.h 。
💬 Stack.c
/* 初始化 */
void StackInit(Stack* pst) {
assert(pst); // 防止pst为空
pst->array = NULL;
pst->top = 0; // pst->top = -1
pst->capacity = 0;
}
🔑 解析:初始化和顺序表几乎没有什么区别。首先通过结构体指针(我们定义的Stack) pst 指向 array,将数组为空。因为是初始化,所以将有效数据个数和数组时即能存数据的空间容量一并置为0。
0x01 销毁(StackDestroy)
💬 Stack.h
void StackDestroy(Stack* pst);
💬 Stack.c
/* 销毁 */
void StackDestroy(Stack* pst) {
assert(pst); // 防止pst为空
free(pst->array);
pst->array = NULL;
pst->capacity = pst->top = 0;
}
🔑 解读:首先把栈 free 掉,为了防止野指针我们手动把它置为空指针(建议养成习惯)。最后再把 capacity 和 size 全部设为0,做到空着手来,空着手去,销毁部分就实现好了。
0x02 判断栈是否为空(StackIfEmpty)
💬 Stack.h
bool StackIsEmpty(Stack* pst);
🔑 解读:布尔值,返回 true 或 false
💬 Stack.c
/* 判断栈是否为空*/
bool StackIsEmpty(Stack* pst) {
assert(pst); //防止pst为空
if (pst->top == 0)
return true;
else
return false;
}
🔑 解读:首先防止 pst 为空。思路很简单,只需要看 top 是不是 0 即可,如果 top 是 0 就说明栈内没有数据。
⚡ 这里甚至可以直接返回,巧妙地利用布尔类型的特性:
bool StackIfEmpty(Stack* pst) {
assert(pst); //防止pst为空
return pst->top == 0; //等于0就是空,就是真
}
0x03 入栈(StackPush)
💬 Stack.h
void StackPush(Stack* pst, StackDataType x);
💬 Stack.c
/* 进栈 */
void StackPush(Stack* pst, StackDataType x) {
assert(pst); // 防止pst为空
// 检查是否需要增容
if (pst->top == pst->capacity) {
int new_capacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
StackDataType* tmp_arr = realloc(pst->array, sizeof(StackDataType) * new_capacity);
// 防止realloc翻车
if (tmp_arr == NULL) {
printf("realloc failed!\n");
exit(-1);
}
// 更新
pst->array = tmp_arr;
pst->capacity = new_capacity;
}
// 填入数据
pst->array[pst->top] = x;
pst->top++;
}
🔑 解读:
这里和顺序表尾插的实现没有任何区别。首先防止 pst 为空,随后检查是否要增容,如果要增容就进行增容操作。最后再填入数据即可。
【顺序表尾插的讲解】根据我们刚才分析的三种情况,首先我们需要判断是空间是否足够。判断思路如下:如果 size == capacity(有效数据个数等于实际能存的最大空间容量),我们进行扩容操作。
如果空间不足,我们就创建一个变量 new_capacity 用来存放 "新容量" ,int new_capacity = pst->capacity 首先把 capacity 的值赋值给这个 "新容量" ,因为考虑到第一次使用 capacity 大小为0,翻倍会出问题(0乘以任何数都是0),这里巧妙地使用三目操作符:int new_capacity = pst->capacity == 0 ? 4 : pst->capacity*2 , 如果 capacity 为 0 (第一次使用大小是0),就把4赋值给它;如果不为0,就把 capacity 的值翻一倍(x2)。
0x04 出栈(StackPop)
💬 Stack.h
void StackPop(Stack* pst);
💬 Stack.c
/* 出栈 */
void StackPop(Stack* pst) {
assert(pst); //防止pst为空
//assert(pst->top > 0); //防止top为空
assert(!StackIsEmpty(pst));
pst->top--;
}
🔑 解读:
① 首先防止 pst 为空。这里要注意的是,不能让栈内没有数据,必须要有东西能 "出栈" 才行。
② 出栈是非常简单的,就是把数据吐出来。直接将 top-- ,直接一刀砍就能直接达到目的。后进先出,后进的直接被 top-- 干掉了。
0x05 返回栈顶数据(StackTop)
💬 Stack.h
StackDataType StackTop(Stack* pst);
🔑 解读:为了方便打印出数据,我们需要设计一个返回栈顶数据的接口。既然是返回数据,我们的函数类型自然是 StackDataType 了。
💬 Stack.c
/* 返回栈顶数据 */
StackDataType StackTop(Stack* pst) {
assert(pst); //防止psl为空
//assert(pst->top > 0); //防止top为空
assert(!StackIsEmpty(pst));
return pst->array[pst->top - 1];
}
🔑 解读:
① 首先防止 pst 为空。同样地,不能让栈内没有数据。
② 我们直接返回栈顶数据就可以了,pst->array[pst->top-1] 。
❓ 为什么这里要 -1?
💡 这里 -1 的原因是我们初始化栈的时候定义 top 时给的值是 0,意味着 top 指向的是栈顶数据的下一个(无数据),所以这里既然要返回的是栈顶数据,自然需要 -1。这里的代码到底要不要 -1,主要看我们初始化 top 的时候给的是什么值,如果我们当时给的是 -1,那么 top 将指向栈顶数据,自然这里就不需要 -1,就应该是 pst->array[pst->top-1] 了。
(修正:图中的 psl 应该是 pst ,笔误)
💬 Test.c
#include "Stack.h"
void TestStack1() {
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
StackPop(&st);
StackPop(&st);
StackPop(&st);
StackPop(&st);
//StackPop(&st);
//printf("%d", StackTop(&st));
StackDestroy(&st);
}
int main() {
TestStack1();
return 0;
}
0x06 计算栈的大小(StackSize)
💬 Stack.h
int StackSize(Stack* pst);
💬 Stack.c
/* 计算栈的大小 */
int StackSize(Stack* pst) {
assert(pst); //防止pst为空
// 因为我们设定 top 是指向栈顶的下一个,所以top就是size
return pst->top;
}
🔑 解读:首先防止 pst 为空。因为我们之前初始化时 top 给的是0,指向栈顶的下一个。所以 top 就是栈的大小,直接 return top 即可。
0x07 代码测试
① 全部入栈完再出栈
#include "Stack.h"
void TestStack2() {
// 入栈:1 2 3 4
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
// 出栈:4 3 2 1
while (!StackIfEmpty(&st)) {
printf("%d ", StackTop(&st));
StackPop(&st);
}
StackDestroy(&st);
}
int main() {
TestStack2();
return 0;
}
🚩 运行代码:
② 入栈的同时伴随着出栈
#include "Stack.h"
void TestStack3() {
// 入栈:1 2 3 4
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
// 提前出栈:4 3
printf("%d ", StackTop(&st));
StackPop(&st);
printf("%d ", StackTop(&st));
StackPop(&st);
StackPush(&st, 5);
StackPush(&st, 6);
// 出栈:6 5 2 1
while (!StackIfEmpty(&st)) {
printf("%d ", StackTop(&st));
StackPop(&st);
}
StackDestroy(&st);
}
int main() {
TestStack3();
return 0;
}
🚩 运行结果:
0x08 完整代码
💬 Stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int StackDataType;
typedef struct Stack {
StackDataType* array; //数组
int top; //栈顶
int capacity; //容量
} Stack;
void StackInit(Stack* pst);
void StackDestroy(Stack* pst);
bool StackIsEmpty(Stack* pst);
void StackPush(Stack* pst, StackDataType x);
void StackPop(Stack* pst);
StackDataType StackTop(Stack* pst);
int StackSize(Stack* pst);
💬 Stack.c
#include "Stack.h"
/* 初始化 */
void StackInit(Stack* pst) {
assert(pst); // 防止pst为空
pst->array = NULL;
pst->top = 0; // pst->top = -1
pst->capacity = 0;
}
/* 销毁 */
void StackDestroy(Stack* pst) {
assert(psl); // 防止pst为空
free(pst->array);
pst->array = NULL;
pst->capacity = pst->top = 0;
}
/* 判断栈是否为空*/
bool StackIsEmpty(Stack* pst) {
assert(pst); //防止pst为空
return pst->top == 0; //等于0就是空,就是真
}
/* 进栈 */
void StackPush(Stack* pst, StackDataType x) {
assert(pst); // 防止pst为空
// 检查是否需要增容
if (pst->top == pst->capacity) {
int new_capacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
StackDataType* tmp_arr = realloc(pst->array, sizeof(StackDataType) * new_capacity);
// 防止realloc翻车
if (tmp_arr == NULL) {
printf("realloc failed!\n");
exit(-1);
}
// 更新
pst->array = tmp_arr;
pst->capacity = new_capacity;
}
// 填入数据
pst->array[pst->top] = x;
pst->top++;
}
/* 出栈 */
void StackPop(Stack* pst) {
assert(pst); //防止pst为空
//assert(pst->top > 0); //防止top为空
assert(!StackIsEmpty(pst));
pst->top--;
}
/* 返回栈顶数据 */
StackDataType StackTop(Stack* pst) {
assert(pst); //防止pst为空
//assert(pst->top > 0); //防止top为空
assert(!StackIsEmpty(pst));
return pst->array[pst->top - 1];
}
/* 计算栈的大小 */
int StackSize(Stack* pst) {
assert(pst); //防止pst为空
// 因为我们设定 top 是指向栈顶的下一个,所以top就是size
return pst->top;
}
💬 Test.c(测试用)
#include "Stack.h"
void TestStack1() {
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
StackPop(&st);
StackPop(&st);
StackPop(&st);
StackPop(&st);
//StackPop(&st);
//printf("%d", StackTop(&st));
StackDestroy(&st);
}
void TestStack2() {
// 入栈:1 2 3 4
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
// 出栈:4 3 2 1
while (!StackIfEmpty(&st)) {
printf("%d ", StackTop(&st));
StackPop(&st);
}
StackDestroy(&st);
}
void TestStack3() {
// 入栈:1 2 3 4
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
// 提前出栈:4 3
printf("%d ", StackTop(&st));
StackPop(&st);
printf("%d ", StackTop(&st));
StackPop(&st);
StackPush(&st, 5);
StackPush(&st, 6);
// 出栈:6 5 2 1
while (!StackIfEmpty(&st)) {
printf("%d ", StackTop(&st));
StackPop(&st);
}
StackDestroy(&st);
}
int main() {
TestStack3();
return 0;
}
参考资料:
Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .
百度百科[EB/OL]. []. https://baike.baidu.com/.
📌 笔者:王亦优
📃 更新: 2021.11.17
❌ 勘误: 无
📜 声明: 由于作者水平有限,本文有错误和不准确之处在所难免,本人也很想知道这些错误,恳望读者批评指正!
本篇完。
相关文章
- Java打印数组的四种方式「建议收藏」
- 数据结构之数组和链表的区别
- 数组的数据结构原理
- 看得见的数据结构Android版之数组表(数据结构篇)
- Golang数组去重&切片去重
- 2022-10-27:设计一个数据结构,有效地找到给定子数组的 多数元素 。 子数组的 多数元素 是在子数组中出现 thresh
- js 数组插入删除[通俗易懂]
- 【Linux C语言编程】4种方法将bin文件生成C语言格式的头文件数组
- 数据结构001:最大子数组和
- 数据结构实验之数组二:稀疏矩阵(SDUT 3348)
- 【C 语言】二级指针作为输入 ( 指针数组 | 将 二级指针 作为函数输入 | 抽象函数业务逻辑 )
- 【Linux 内核 内存管理】分区伙伴分配器 ① ( 分区伙伴分配器源码数据结构 | free_area 空闲区域数组 | MAX_ORDER 宏定义 | 空闲区域的页最大阶数 )
- 使用JavaScript的数组实现数据结构中的队列与堆栈详解编程语言
- go语言之数组详解编程语言
- MySQL:存储数组的最佳方法(mysql存储数组)
- PHP数组基础知识小结
- js中将具有数字属性名的对象转换为数组
- PHP中使用数组实现堆栈数据结构的代码
- C#数组初始化简析
- java利用数组求平均值,最大值,最小值
- php根据分类合并数组的方法实例详解