栈的基本操作(C语言实现)

期末终于结束，接下来就会继续更新数据结构相关的内容了，本篇文章带来数据结构——栈，来实现它的基本功能。

难度偏低，因为之前我们已经实现过顺序表了，栈不过是顺序表的一种特殊形式。

一、 栈的概念与结构

概念：栈是一种特殊的线性表，其只允许在固定的一端插入和删除操作。进行数据插入和删除操作的一端为栈顶，另一端为栈底。栈中的数据元素遵守后进先出(Last In First Out)的原则。

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

出栈：栈的删除操作叫做出栈，即从栈顶删除数据。

---

二、 栈的框架定义

栈的实现可以使用数组和链表，相对而言数组的结构实现更优，因为数组在尾上插入数据的代价较小，数组的特征也更符合栈的特性。

接下来我们来看看我们栈的类型定义以及我们此次要实现的功能。

#pragma once 
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;			//标识栈顶的数据
	int capacity;		//动态型  空间不够则扩容
}ST;

void StackInit(ST* ps);            //栈的初始化
void StackDestory(ST* ps);         //栈的销毁
void StackPush(ST* ps, STDateType x); //栈的插入
void StackPop(ST* ps);           //删除数据
STDateType StackTop(ST* ps);	//取栈顶的元素
bool StackEmpty(ST* ps);		//判断栈是否为空
int StackSize(ST* ps);			//得知栈的大小

---

三、 栈的功能实现

3.1 栈的初始化

在我们创建一个自定义栈型的变量时，第一件事即是变量的初始化。

//栈的初始化
void StackInit(ST* ps)
{
	assert(ps);       
	ps->a = NULL;        
	ps->top = 0;
	ps->capacity = 0;
}

3.2 栈的销毁

栈销毁相当于栈空间的释放加上对数据的删除，其实与初始化差不多，这里也初始化一同实现。

//栈的销毁
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

3.3 插入数据

栈的关键性功能。首先，判断我们栈是否需要扩容；然后将数据插入到栈顶的位置；最后将栈顶向上移动。

这里会有两种情况：①初始设置栈顶top为0，即Top=0，那我们是先将数据插入，然后再将Top向上移动。②如果我们初始设置栈顶为-1，即Top=-1，那么我们在插入数据的时候要先+1，然后再将数据放入。这里我们采用第一种方式。 

//插入数据
void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	//如果top等于当前的容量，则扩容
	if (ps->capacity == ps->top)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* temp = (STDateType * )realloc(ps->a, sizeof(STDateType) * NewCapacity);
		if (temp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = temp;
		ps->capacity = NewCapacity;
	}
    //将值放入栈中。
	ps->a[ps->top] = x;
    //Top向上移动
	ps->top++;
}

3.4 删除数据

删除数据就非常简单了，数组的天然优势，直接将栈顶向下移动一个单位即可。

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

3.5 取栈顶元素

STDateType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

3.6 栈的判空

我们这里不用使用if语句判断，直接返回ps->top==0这句代码，会自动判断其真假。如果top==0，则直接会返回true，简洁、方便。

bool StackEmpty(ST* ps)
{
	assert(ps);
    //直接返回表达式。
	return ps->top == 0;
}

3.7 栈的大小

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

---

四、功能展示

 这里我们来尝试插入数据并将其全部输出出来，这些会用到我们上面的全部功能，以来检测这些功能是否实现成功。

 这里注意一点，栈是不能遍历的，如果我们想打印栈中的数据，则要打印一个栈顶元素，然后将其弹出，直到栈为空则停止操作。

五、 总结

对于栈我们要领会其功能和特征，其中一些细节我们不必太在乎，我们在乎的主要是它的结构和特性。

栈的使用是非常广泛的，这里我们使用数组实现栈，是因为数组的特点很利于实现栈的特性，如果之前有实现过顺序表的兄弟会发现栈的实现和顺序表非常类似，因为栈本身就是一种特殊的顺序表类型。如果大家有时间可以去尝试用链表实现栈，在之前实现过单链表来说的话，也不算太难。

---

好的，本篇文章就到此结束了，感想大家的阅读，下篇文章会带来队列的基本功能实现，我们下期再见。