数据结构之栈

片头

嗨! 小伙伴们,大家好! 今天我们来一起学习栈这个数据结构吧! 准备好了吗? 我要开始咯!

一、栈

1.1 栈的基本概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除操作。进入数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。我们可以想象成吃羊肉串，最先穿进去的羊肉块是被压在最下面，最后一个羊肉块是在最上面的。

压栈：栈的插入操作叫做进栈/压栈/入栈,从栈顶插入数据。

出栈：栈的删除操作叫做出栈，出数据也在栈顶。

1.2 栈的实现

栈的实现一般可以通过用数组实现栈或者用链表实现栈，二者取其优，相对而言使用数组结构实现栈更简便高效。

因为在前面顺序表的增删改查接口实现中（数据结构之顺序表）我们使用数组的结构来尾插尾删十分的方便,所以在栈的实现中我们把数组尾部定义为栈顶,头部定义成栈底即可。

二、栈的接口实现

栈和顺序表一样，可以设计成定长的静态栈或者动态增长的栈。因为定长栈局限性大，实际中不实用，所以我们主要实现支持动态增长的栈。

和前面的顺序表/链表接口实现相同,我们先创建一个头文件"Stack.h"和2个源文件"Stack.c" 和"Test.c",具体的作用为:

我们先展示"Stack.h" 的完整代码,不要忘记在2个源文件中引用"Stack.h"

#pragma once				//防止头文件被二次引用
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int ElemType;		//如果要修改存储的数据类型可直接在此修改
typedef struct Stack {
	ElemType* arr;			//动态数组
	int top;				//栈顶
	int capacity;			//容量
}Stack;


void StackInit(Stack* ps);//初始化栈

void StackPush(Stack* ps, ElemType x);//入栈

void StackPop(Stack* ps);//出栈

ElemType StackTop(Stack* ps);//获取栈顶元素

int StackSize(Stack* ps);//获取栈中有效元素的个数

int StackEmpty(Stack* ps);//检测栈是否为空,如果为空返回非零结果,如果不为空返回0

void StackDestroy(Stack* ps);//销毁栈

其中,"top"的含义是由初始数值决定的,下面会细讲。接下来我们开始实现接口。

（1）初始化栈

//初始化栈
void StackInit(Stack* ps) {
	assert(ps);		//断言,防止传入空指针
	ps->arr = NULL; //初始化数组,置空
	ps->capacity = 0;//top指向栈顶元素的下一个位置
	ps->top = 0;	 //初始化容量
}

为了方便理解，我们将结构体中的top近似理解为数组的下标。如果我们在初始化栈时将top初始化为0,此时栈中没有数据,top指向栈顶数据的下一个位置

如果我们将top初始化为-1时,top则会指向栈顶数据的位置。这里我们初始化成0更好，因为方便添加元素和删除元素。

（2）入栈

//入栈
void StackPush(Stack* ps, ElemType x) {
	//扩容
	if (ps->capacity == ps->top) //容量已满,需要扩容
	{
		//如果容量为0,则扩容到4; 否则扩大2倍
		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		//创建一个临时指针变量来存储新空间地址,防止开辟失败
		ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
		if (temp == NULL) //防止开辟失败出现空指针
		{
			perror("realloc fail!\n");
			exit(1);
		}
		ps->arr = temp;	  //将临时指针变量中存放的新空间地址赋给arr
		ps->capacity = newCapacity;//空间容量更新
	}
	ps->arr[ps->top] = x;//将数据存放进栈顶元素的下一个位置
	ps->top++;//位置更新
}

  因为栈和顺序表有差别，不能直接遍历打印，因此我们要打印栈中的元素，需要使用 StackEmpty函数 和 StackPop函数, 后面会讲到。

（3）出栈

//出栈
void StackPop(Stack* ps) {
	assert(ps);			//断言,防止传入空指针
	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
}

（4）获取栈顶元素

//获取栈顶元素
ElemType StackTop(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	assert(ps->top);		//断言,防止栈为空
	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
}

（5）获取栈中有效的元素个数

//获取栈中有效元素的个数
int StackSize(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	return ps->top;			//top即为有效元素的个数
}

（6） 检测栈是否为空

//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	return ps->top == 0;	//如果top==0, 说明栈为空
}

这就是为什么前面断言中的StackEmpty要加逻辑取反操作符的原因,如果栈为空,StackEmpty返回true,取反为false才能证明栈里面有元素。

（7）销毁栈

//销毁栈
void StackDestroy(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	if (ps->arr)			//如果动态数组有效
	{
		free(ps->arr);		//释放arr
		ps->arr = NULL;		//将arr置空
	}
	ps->capacity = 0;		//数组的容量为0
	ps->top = 0;			//数组的栈顶top为0

}

所有接口都完成后，我们在Test.c中测试一下代码:

我们再多测试一下:

完全没问题,恭喜你完成了栈的接口实现!

片尾

今天我们学习了栈这个数据结构,是不是比链表简单多了? 哈哈哈哈哈,希望看完这篇文章能对友友们有所帮助 !   !   !

求点赞收藏加关注 !   !   !

谢谢大家 !   !   !