【数据结构】栈的基本概念 | 从零开始实现数组栈 | 画图解析 | 数组栈与链式栈

admin • 2021-11-22 20:32 • C/C++

前言：

本章我们将学习 "栈" ，首先介绍栈的概念和结构，然后我们将着重讲解数组栈的实现。我们从零开始写数组栈的接口，并从零开始步步解读。本章旨在筑牢栈知识点的基础，对后续的刷题有着很大的帮助。

一、栈（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* psl);
void StackDestroy(Stack* psl);
bool StackIfEmpty(Stack* psl);
void StackPush(Stack* psl, StackDataType x);
void StackPop(Stack* psl);
StackDataType StackTop(Stack* psl);
int StackSize(Stack* psl);

? 解读：相信细心的小伙伴发现了，StackIfEmpty 函数的类型是布尔。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* psl);

? 解读：大家学到这里想必已然轻车熟路，应该知道需要引入哪些头文件了，动态内存开辟需要引入 stdlib.h，断言需要引入 assert，使用布尔值需要引入 stdbool.h 。

? Stack.c

/* 初始化 */
void StackInit(Stack* psl) {
	assert(psl);   // 防止psl为空
	psl->array = NULL;
	psl->top = 0;  // psl->top = -1
	psl->capacity = 0;
}

? 解析：初始化和顺序表几乎没有什么区别。首先通过结构体指针（我们定义的Stack） psl 指向 array，将数组为空。因为是初始化，所以将有效数据个数和数组时即能存数据的空间容量一并置为0。

0x01 销毁（StackDestroy）

? Stack.h

void StackDestroy(Stack* psl);

? Stack.c

/* 销毁 */
void StackDestroy(Stack* psl) {
	assert(psl);   // 防止psl为空
	
	free(psl->array);
	psl->array = NULL;
	psl->capacity = psl->top = 0;
}

? 解读：首先把栈 free 掉，为了防止野指针我们手动把它置为空指针（建议养成习惯）。最后再把 capacity 和 size 全部设为0，做到空着手来，空着手去，销毁部分就实现好了。

0x02 判断栈是否为空（StackIfEmpty）

? Stack.h

bool StackIfEmpty(Stack* psl);

? 解读：布尔值，返回 true 或 false

? Stack.c

/* 判断栈是否为空*/
bool StackIfEmpty(Stack* psl) {
	assert(psl);  //防止psl为空
	if (psl->top == 0)
		return true;
	else
		return false;
}

? 解读：首先防止 psl 为空。思路很简单，只需要看 top 是不是 0 即可，如果 top 是 0 就说明栈内没有数据。

⚡ 这里甚至可以直接返回，巧妙地利用布尔类型的特性：

bool StackIfEmpty(Stack* psl) {
	assert(psl);  //防止psl为空
	return psl->top == 0; //等于0就是空，就是真
}

0x03 入栈（StackPush）

? Stack.h

void StackPush(Stack* psl, StackDataType x);

? Stack.c

/* 进栈 */
void StackPush(Stack* psl, StackDataType x) {
	assert(psl); // 防止psl为空

	// 检查是否需要增容
	if (psl->top == psl->capacity) {
		int new_capacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		StackDataType* tmp_arr = realloc(psl->array, sizeof(StackDataType) * new_capacity);
		// 防止realloc翻车
		if (tmp_arr == NULL) {
			printf("realloc failed!n");
			exit(-1);
		}
		// 更新
		psl->array = tmp_arr;
		psl->capacity = new_capacity;
	}

	// 填入数据
	psl->array[psl->top] = x;
	psl->top++;
}

? 解读：

这里和顺序表尾插的实现没有任何区别。首先防止 psl 为空，随后检查是否要增容，如果要增容就进行增容操作。最后再填入数据即可。

【顺序表尾插的讲解】根据我们刚才分析的三种情况，首先我们需要判断是空间是否足够。判断思路如下：如果 size == capacity（有效数据个数等于实际能存的最大空间容量），我们进行扩容操作。

如果空间不足，我们就创建一个变量 new_capacity 用来存放 "新容量" ，int new_capacity = psl->capacity 首先把 capacity 的值赋值给这个 "新容量" ，因为考虑到第一次使用 capacity 大小为0，翻倍会出问题（0乘以任何数都是0），这里巧妙地使用三目操作符：int new_capacity = psl->capacity == 0 ? 4 : psl->capacity*2 ，如果 capacity 为 0 （第一次使用大小是0），就把4赋值给它；如果不为0，就把 capacity 的值翻一倍（x2）。

0x04 出栈（StackPop）

? Stack.h

void StackPop(Stack* psl);

? Stack.c

/* 出栈 */
void StackPop(Stack* psl) {
	assert(psl);  //防止psl为空
	//assert(psl->top > 0);  //防止top为空
	assert(!StackIfEmpty(psl));
	
	psl->top--;
}

? 解读：

① 首先防止 psl 为空。这里要注意的是，不能让栈内没有数据，必须要有东西能 "出栈" 才行。

② 出栈是非常简单的，就是把数据吐出来。直接将 top-- ，直接一刀砍就能直接达到目的。后进先出，后进的直接被 top-- 干掉了。

0x05 返回栈顶数据（StackTop）

? Stack.h

StackDataType StackTop(Stack* psl);

? 解读：为了方便打印出数据，我们需要设计一个返回栈顶数据的接口。既然是返回数据，我们的函数类型自然是 StackDataType 了。

? Stack.c

/* 返回栈顶数据 */
StackDataType StackTop(Stack* psl) {
	assert(psl);  //防止psl为空
	//assert(psl->top > 0);  //防止top为空
	assert(!StackIfEmpty(psl));

	return psl->array[psl->top - 1];
}

? 解读：

① 首先防止 psl 为空。同样地，不能让栈内没有数据。

② 我们直接返回栈顶数据就可以了，psl->array[psl->top-1] 。

❓ 为什么这里要 -1？

? 这里 -1 的原因是我们初始化栈的时候定义 top 时给的值是 0，意味着 top 指向的是栈顶数据的下一个（无数据），所以这里既然要返回的是栈顶数据，自然需要 -1。这里的代码到底要不要 -1，主要看我们初始化 top 的时候给的是什么值，如果我们当时给的是 -1，那么 top 将指向栈顶数据，自然这里就不需要 -1，就应该是 psl->array[psl->top-1] 了。

? 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* psl);

? Stack.c

/* 计算栈的大小 */
int StackSize(Stack* psl) {
	assert(psl);  //防止psl为空
	
	// 因为我们设定 top 是指向栈顶的下一个，所以top就是size
	return psl->top; 
}

? 解读：首先防止 psl 为空。因为我们之前初始化时 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* psl);
void StackDestroy(Stack* psl);
bool StackIfEmpty(Stack* psl);
void StackPush(Stack* psl, StackDataType x);
void StackPop(Stack* psl);
StackDataType StackTop(Stack* psl);
int StackSize(Stack* psl);

? Stack.c

#include "Stack.h"

/* 初始化 */
void StackInit(Stack* psl) {
	assert(psl);   // 防止psl为空
	psl->array = NULL;
	psl->top = 0;  // psl->top = -1
	psl->capacity = 0;
}

/* 销毁 */
void StackDestroy(Stack* psl) {
	assert(psl);   // 防止psl为空
	
	free(psl->array);
	psl->array = NULL;
	psl->capacity = psl->top = 0;
}

/* 判断栈是否为空*/
bool StackIfEmpty(Stack* psl) {
	assert(psl);  //防止psl为空

	return psl->top == 0; //等于0就是空，就是真
}

/* 进栈 */
void StackPush(Stack* psl, StackDataType x) {
	assert(psl); // 防止psl为空

	// 检查是否需要增容
	if (psl->top == psl->capacity) {
		int new_capacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		StackDataType* tmp_arr = realloc(psl->array, sizeof(StackDataType) * new_capacity);
		// 防止realloc翻车
		if (tmp_arr == NULL) {
			printf("realloc failed!n");
			exit(-1);
		}
		// 更新
		psl->array = tmp_arr;
		psl->capacity = new_capacity;
	}

	// 填入数据
	psl->array[psl->top] = x;
	psl->top++;
}


/* 出栈 */
void StackPop(Stack* psl) {
	assert(psl);  //防止psl为空
	//assert(psl->top > 0);  //防止top为空
	assert(!StackIfEmpty(psl));
	
	psl->top--;
}

/* 返回栈顶数据 */
StackDataType StackTop(Stack* psl) {
	assert(psl);  //防止psl为空
	//assert(psl->top > 0);  //防止top为空
	assert(!StackIfEmpty(psl));

	return psl->array[psl->top - 1];
}

/* 计算栈的大小 */
int StackSize(Stack* psl) {
	assert(psl);  //防止psl为空
	
	// 因为我们设定 top 是指向栈顶的下一个，所以top就是size
	return psl->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

❌ 勘误：无

? 声明：由于作者水平有限，本文有错误和不准确之处在所难免，本人也很想知道这些错误，恳望读者批评指正！

本篇完。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

数据结构

二维码

C语言每日一练——第61天：掷骰子游戏

< <上一篇

《结构体在内存中的对齐规则》多图易理解

下一篇>>

搜索内容

【数据结构】栈的基本概念 | 从零开始实现数组栈 | 画图解析 | 数组栈与链式栈

前言：

一、栈（stack）

0x00 栈的概念

0x01 栈的结构

0x02 数组栈和链式栈

二、栈的定义

0x00 动态栈

0x01 静态栈

0x02 接口函数

三、栈的实现

0x00 初始化栈（StackInit）

0x01 销毁（StackDestroy）

0x02 判断栈是否为空（StackIfEmpty）

0x03 入栈（StackPush）

0x04 出栈（StackPop）

0x05 返回栈顶数据（StackTop）

0x06 计算栈的大小（StackSize）

0x07 代码测试

0x08 完整代码

最新文章

分类

标签云