首页 > 编程学习 > 数据结构之栈的实现

数据结构之栈的实现

发布时间:2022/11/13 5:08:53

文章目录

  • 前言
  • 1.栈的相关介绍
    • 1.栈的概念
    • 2.栈结构实现方式
  • 2.具体代码实现栈
    • 1.栈的相关接口
    • 2.栈结构的定义声明和栈的初始化
    • 3.栈数据的处理
      • 1.入栈
      • 2.出栈
    • 4.栈判空和获取栈中元素个数以及栈销毁
  • 3.总结

前言

之前介绍了链表的实现,现在接着介绍另一种线性结构—栈。栈和链表一样,都是很经典的数据结构。通过学习栈,为以后学习其他数据结构打下坚实的基础。


1.栈的相关介绍

1.栈的概念

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。出栈:栈的删除操作叫做出栈。出数据也在栈顶。

栈的概念可以联想到桌子上放的书。我们将书一本书放另一本书上,若干本书这样挨个往上放,当我们取书时,是从最上面开始拿,如果想拿最下面的书,就得将这本书上面的书都拿下来,才能拿到最下面的书,这个放书的过程就像入栈,拿书的过程就像出栈。
在这里插入图片描述


2.栈结构实现方式

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

在这里插入图片描述

我们知道栈入数据和出数据都是从栈顶开始,如果用数组表示栈,那么入数据就相当于尾插,出数据就相当于尾删,这样的操作对数组来说是十分友好的。如果是链表来实现栈找栈顶还需要遍历,双向循环链表不用遍历可以快速找到栈顶,但是这未免有些麻烦了一点,数组用起来简单方便一点。


2.具体代码实现栈

1.栈的相关接口

void StackInit(Stack* ps);// 初始化栈
void StackPush(Stack* ps, STDataType x);//入栈
void StackPop(Stack* ps);//出栈
STDataType StackTop(Stack* ps);//获取栈顶元素
int StackSize(Stack* ps);// 获取栈中有效元素个数
int StackEmpty(Stack* ps); //检测栈是否为空,如果为空返回非零结果,如果不为空返回0
void StackDestroy(Stack* ps);//销毁栈

其实栈的实现有点像之前我们实现的顺序表,最大的区别就是栈的数据只能栈顶出或者进。所以栈的数据只能尾插尾删,同时还有个函数专门用来获取栈顶数据。这是根据栈的特性来决定栈中数据存取方式。


2.栈结构的定义声明和栈的初始化

typedef int STDataType;
typedef struct Stack
{
	STDataType* data;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

刚才说了,栈的实现是和顺序表有点像,因为顺序表一般也是用数组来实现的。我们这里采用动态顺序表的实现方式,实现动态栈。当栈中空间不够时,可申请动态内存空间进行增容。
代码中的top其实有点像实现通讯录时中的sz(表示存储联系人信息的个数),知识都是相通的,灵活应用很重要。


栈的初始化

void StackInit(Stack* ps)//初始化
{
	assert(ps);
	ps->data = (STDataType*)malloc(sizeof(STDataType)*4);
	ps->top = 0;
	ps->capacity=4;
	return;
}

栈顶初始化,为栈开辟一段空间用来存储数据。因为栈中没有数据top初始化为0,因为只是申请了4个结构体大小的空间,所以就没有就行判断空处理。这里注意一下,栈的数据是从栈顶开始存放的,数组的下标索引是从0开始的,没有数据时,top就是0,意味着top是指向栈顶元素的下一个位置。在实现代码时注意这一点就好了。


3.栈数据的处理

1.入栈

void StackPush(Stack* ps, STDataType x)//入栈
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
     STDataType* tem = 
    (STDataType*)realloc
    (ps->data, ps->capacity*2*sizeof(STDataType));
		if (tem == NULL)
		{
			perror("StackPush:");
			exit(-1);
		}
		ps->data = tem;
		ps->capacity *= 2;
	}

	ps->data[ps->top] = x;
	ps->top++;
	return;
}

入栈就是尾插数据,也就是按顺序插入数据。因为刚才说了top是指向栈顶元素下一个位置,初始化top为0表示的是空栈,但是数组索引从0开始,因此先插入数据,然后top自增,这样做的另一个好处就是top就是栈中元素个数。空间扩容就不多说了,之前博客有介绍。


2.出栈

出栈就相当于尾删,然后top(栈顶)往下降一个单位。但是,出栈肯定是要得到某个数据,就是将栈中的数据弹出来,然后栈顶往下降。因此还需要个函数来获取栈顶的元素。

栈顶元素获取

STDataType StackTop(Stack* ps)//获取栈顶元素
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->data[ps->top - 1];
}

因为top是指向栈顶元素下一个位置的,所以栈顶元素的索引应该是top-1.还有一点当栈为空时,就不能获取元素,所以要断言一下。


出栈

void StackPop(Stack* ps)//出栈
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

出栈就相当于尾删,和顺序表的尾插一样,都很简单。


4.栈判空和获取栈中元素个数以及栈销毁

栈判空非常简单,top为0就是空栈。如果top大于0就不是空栈。

栈判空

int StackEmpty(Stack* ps)//栈判空
{    assert(ps);
	return ps->top == 0;
}

其实栈判空应该用布尔值来表示比较好,c语言中用布尔值需要用到相应的头文件,这个之前的博客也提到过。


获取栈中元素个数也很简单,刚才说了top的值就是栈中元素个数

栈中数据个数


int StackSize(Stack* ps)//获取栈中有效元素个数
{  
	aseert(ps);
	return ps->top;
}

因为数组索引是0开始的,而top又是指向栈顶元素下一个位置的,刚好top就是栈元素个数。


销毁栈还是和销毁动态顺序表一样,用free释放掉申请的动态内存空间即可

销毁栈

void StackDestroy(Stack* ps)//销毁栈
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
	return;
}

释放掉空间后,该置空的置空,该置0的置0,实现起来还是比较简单的。


3.总结

  • 1.栈的实现相对比较简单,但是在使用栈时要注意,先获取栈顶元素,在进行出栈处理。如果先出栈,就找不到之前的栈顶元素了,如果不需要用到栈顶元素,那就不用关心这点,直接出栈就好了。
  • 2.以上内容,如有错误,欢迎指出!谢谢!
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式