数据结构之——栈

@TOC

前言

本文主要讲述特殊的线性表——栈：

栈是什么，栈的特点

数据结构中有一种特殊的线性表叫栈。 栈有一种特点：

它允许后进入的数据先拿出来。

类似一个弹夹，或是一个装砖头的容器。

栈的基本操作有如上图：

类比一个缸，缸的底端是栈底，顶端是栈顶，放入数据称为入栈，取出数据称为出栈。

对于一个栈，其特点为后进先出Last In Fist Out 或者 先进后出Fist Out Last In

所以在实现栈这种特殊的线性表时，当我们拿出数据的时候，只需要取栈顶元素即可，存入数据时，只需往栈顶存放数据。

综合栈的特点，在实现其结构时更适合使用数组 ，而不是链表。 当然使用链表也是可行的，相比而言： 使用链表的缺点有： 1.在压栈时总需要next的指针来维护。2。出栈时需要记录上一个节点的位置，效率较低。

数组的方式可以解决上述两个问题，且无其他较为严重的缺点。

下面来实现栈的基本功能：

实现栈的基本操作

栈的相关操作声明

void StackInit(ST* ps);//初始化
void StackDestroy(ST* ps);
void CheckCapacity(ST** ps);//检查容量
void StackPush(ST* ps,STDataType x);//插入元素
void StackPop(ST* ps);//删除栈顶元素
int StackSize(ST* ps);//计算栈有多少个数据
bool StackEmpty(ST* ps);//判断栈是否为空
STDataType StackTop(ST* ps);//取栈顶元素

注：ps是指向一个结构体的指针，在main函数创建了一个结构体：
	ST st;
	并且传参传的是结构体的地址

1.创建栈

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

typedef int STDataType;
//用顺序表实现栈

typedef struct Stack
{
	STDataType* a;
	int top;//插入栈顶元素
	int capacity;//栈的容量
}ST;

解读： 定义一个结构体：使用结构体的指针来维护数组栈top表示栈顶的元素 capacity表示栈的容量大小

2.对栈进行初始化

void StackInit(ST* ps)//初始化
{
	assert(ps!=NULL);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
	//ps->top可以初始化成-1，此时先++，再赋值
	//此时指向的就是栈顶元素
}

3.销毁栈

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

4.判断栈是否为空

bool StackEmpty(ST* ps)//判断栈是否为空
{
	assert(ps);
	return ps->top == 0;
}

5.压栈操作

void CheckCapacity(ST**ps)//检查容量
{
	assert(ps != NULL);
	if ((*ps)->top == (*ps)->capacity)
	{
		STDataType newcapacity = (*ps)->capacity == 0 ? 4 : (*ps)->capacity * 2;
		STDataType* tmp = (STDataType*)realloc((*ps)->a,(sizeof(STDataType)*newcapacity));//申请的空间是存放STDataType的
		//不是用来存放结构体的
		//如果第一个参数是一个NULL，realloc的作用就跟malloc一样，所以可以传NULL
		assert(tmp != NULL);
		(*ps)->a = tmp;// 把新地址给ps->a
		(*ps)->capacity = newcapacity;
	}
}

void StackPush(ST* ps, STDataType x)//插入元素
{
	assert(ps);
	CheckCapacity(&ps);//这里如果传参传的是ps，相当于传值调用，在CheckCapacity函数内部申请的空间就无法返回来了。
	ps->a[ps->top] = x; // 先赋值，再++，因为ps->top初始化是0，就是指向栈顶元素的下一个。
	ps->top++;
}

解读：入栈时首先需要检查栈空间的容量大小，如果栈空间不足则需增容。在这里分装了一个检查容量的函数。

6.删除栈顶元素

void StackPop(ST* ps)//删除栈顶数据
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

7.取出栈顶元素

注：第六个函数仅仅删除栈顶元素并未拿到该数据这里分装函数是更方便的

STDataType StackTop(ST* ps)//取栈顶元素
{
	assert(ps);
	assert(!StackEmpty(ps)); //感叹号表达式让语句的逻辑相反

	return ps->a[ps->top - 1];
	//在这里我初始化top为0，表示指向栈顶元素的下一个位置
	//因为初始化为0时，需要先压栈，top值再++，此时就指向了下一个位置了
}

8.计算栈内存放多少个数据

int StackSize(ST* ps)//计算栈有多少个数据
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->top;
}

解读：这里直接返回top，而不是返回top-1 因为我们在初始化的时候是将top置为0，先入栈，top再++ 假如入栈三次，那么top此时就是3，但是top指向的位置是入栈的第三个元素的下一个位置。

函数基本功能如下：

总结

掌握了链表的结构之后，实现栈难度是不大的。