栈的简单实现及应用_栈的实现

什么是栈？

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

做个简单的比喻：我们的栈就相当于一个弹夹，入栈操作就相当向弹夹之中压入子弹；出栈操作就相当将弹夹里面的子弹取出来；而这个压入子弹和取出子弹都只有一个口；这个口就是栈顶，出入数据都从栈顶进行；

压栈和出栈：

栈的分类

栈主要分为两类：
1、顺序栈；（用顺序表实现的栈）
2、链式栈；（用链表实现的栈）

日常情况下，我们通常会选用顺序表来实现栈？
为什么？
因为如果我们将顺序表的尾作为栈顶的话，入栈（尾插）、出栈（尾删）效率很高就是O（1）；
当然理论上我们也可以将顺序表的头作为栈顶，但是没人会这样高，因为入栈（头插）、出栈（头删）效率很低，时间复杂度是O（N^2）是一种事倍功半的操作；

那既然这样的话，我们为什么不选单链表的头做为栈顶，这样的话入栈（头插）、出栈（头删）效率也很高啊，时间复杂度也是O（1）；
那么为什么不选它嘞？
我们目前来看是这样，但是具体实现起来，我们就得用一个栈顶指针来维护这个栈，那么就需要考虑很多特俗情况，同时参数这块也需要传二级指针，因为我的栈顶指针（链表头节点指针）是会变的；

而如果利用顺序表实现的话，就不会存在传二级指针的问题，也不需要考虑过多的特殊情况；
为此我们强烈推荐利用顺序表来实现栈！！！

栈的数据结构

为了维护这一个栈，我们利用一个结构体来维护栈；

这里我们只需与顺序表区分一下top指针，top指针是专门用来维护栈顶元素的；

栈的基本操作

栈的初始化

刚开是一定是空栈，这点毋庸置疑；
所以我们结构体里面的nums置空，容量capcity也应该置空；
但是这里的top指针有两种初始化方式：
1、top=-1；
2、top=0；
这两种初始化方式对应着后面的操作有些不同；
如果top初始化为-1，那么我的栈顶元素是那个？
是不是就是nums[top],我的top每次都是指向上一次的空间的，为此我们每一次入栈，都要先将top++，在将数据放入top所指位置；为此我的top指针就指向最后一个空间（栈顶位置）；
如果我的top指针初始化为0的话，我就不需要先++top了，直接在top位置插入数据就可以了，因为此时top位置就是待插入数据的位置，为此我们数据插入完毕过后需要++top，而此时的top表示的是栈顶元素的下一个位置top-1才表示栈顶元素的位置，这时的top也就相当于顺序表里面元素个数也就相当于顺序表里面的size；
本文采用top=0；的初始化方式：

//初始化栈
void InitStack(ST* ps)
{
	assert(ps);//防止乱传
	ps->capcity = 0;
	ps->top = 0;
	ps->nums = NULL;
}
1
2
3
4
5
6
7
8

栈的销毁

销毁与初始化操作通常都是连载一起的，我们在初始化操作实现完成过后便可直接实现销毁操作：

//销毁栈
void DestroyStack(ST*ps)
{
	assert(ps);
	ps->capcity = 0;
	ps->top = 0;
	free(ps->nums);
}
1
2
3
4
5
6
7
8

入栈操作

入栈操作对于顺序表来说就是尾插，既然是要插入数据，我们就要首先检查一下容量够不够，不免容量不够而出现插入失败的情况：
检查容量：

//检查扩容，不提供给用户，由程序自己完成
static void Check_Capcity(ST* ps)
{
	assert(ps);
	if (ps->capcity == ps->top)//需要扩容
	{
		int len = (ps->capcity == 0) ? 4 : ps->capcity * 2;
		DataType* tmp = (DataType*)realloc(ps->nums,len*sizeof(DataType));
		if (!tmp)
		{
			printf("realloc fail!\n");
			exit(EXIT_FAILURE);
		}
		ps->nums = tmp;
		ps->capcity = len;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

当然这个检查容量的操作是由程序自己完成的，我们使用者是用不到的，为此我们可以将这个函数加以static关键字加以修饰，以此切断它的外部链接属性，不把它暴露给用户，加强其封装性！！！
容量问题现在解决了，接下来便是插入数据（入栈）：

//入栈
void StackPush(ST* ps,DataType x)
{
	assert(ps);
	Check_Capcity(ps);
	ps->nums[ps->top] = x;
	ps->top++;
}
1
2
3
4
5
6
7
8

出栈和栈空的判断

当然出栈的操作，必然伴随着数据的删除，为此我们必须保证有数据可删才行！！数据都没了，那还删个der！为此我们需要先实现一下栈的判空：
由于我么初始化的时候选择的是将top初始化为0，那么top的数据就是元素个数，为此top==0是便是栈为空，我们便返回真；栈不为空，便返回假：

//判断栈是否为NULL
bool StackEmpty(ST* ps)
{
	assert(ps);
	return !ps->top;
}
1
2
3
4
5
6

接下来我们保证了数据有的删，那我们直接移动top指针就行了，让计算机访问不到，不用真的删除并释放，同时free也不支持只释放不完整的空间；

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//判空
	ps->top--;
}
1
2
3
4
5
6
7

获取栈顶元素

同理可得，我们获取元素，那也得要栈里面有元素才行，栈都为空，就没必要再去取元素了：
为此，我们首先要先判断一下栈是不是为NULL：

//获取栈顶元素
DataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//栈不为空，我们才有元素获取;
	return ps->nums[ps->top - 1];
}
1
2
3
4
5
6
7

获取栈的元素个数

我们初始化的时候top初始化的0，为此，我们top所表示的意义和元素个数等价，为此我们只需返回top即可：

//统计栈的元素
size_t StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
1
2
3
4
5
6

头文件

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef char DataType;
typedef struct Stack
{
	DataType* nums;
	int capcity;
	int top;
}ST;
//初始化栈
void InitStack(ST* ps);
//销毁栈
void DestroyStack(ST* ps);
//入栈
void StackPush(ST* ps,DataType x);
//出栈
void StackPop(ST*ps);
//判断栈是否为NULL
bool StackEmpty(ST* ps);
//统计栈的元素
size_t StackSize(ST* ps);
//获取栈顶元素个数
DataType StackTop(ST*ps);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

总结

或许有的读者会疑惑，我们为什么要单独对栈顶元素和栈的元素个数专门写个函数呢？我们直接一句printf不就搞定了嘛。比如：我直接printf(“%d\n”,st.top);不就是栈的元素嘛，为啥还要专门写个函数；
我们现在是知道top是初始化为0，然后top就直接就表示元素个数，那如果我初始化top为-1，那么此时我的top就不再等价表示顺序表元素个数了，top+1才是表示元素个数，这也就意味着我需要去查看源码到底是怎么初始化top的，很是麻烦，而且难免有时候看错声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】