【笔记】栈（Stack）

一、什么是栈

栈：一种特殊的线性表，其只允许在固定的一端(也就是在表尾)进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。不含任何数据元素的栈称为空栈 。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

注意：

1、栈是一个线性表，那栈就具有线性关系，即前驱后继关系。

2、定义中说是在线性表的表尾进行插入和删除操作，这里的表尾不是栈底，而是指栈顶。也就使得：栈底是固定的，最先进栈的只能在栈底。

栈的插入操作，也叫做进栈，也可以叫称为压栈，入栈。类似子弹入弹夹。

栈的删除操作，也叫做出栈，有的也叫做弹栈。类似子弹弹出弹夹。

这两种操作如下图所示。

 二、栈的顺序存储

1、栈的实现的选择

其实链表的实现可以选择数组栈或者链式栈，但相对而言数组栈的结构实现更优。因为数组在表尾上插入删除数据的代价比较小。

数组栈：

链式栈： 

2、实现栈的接口函数

(1)、定义栈

//定义静态栈
#define N 10
typedef struct Stack
{
	int a[N];//数组
	int capacity;//容量空间大小
	int top;//插入的元素的个数
}ST;

定义静态栈就直接把数组长度给定死了，过后如果有需求要修改起来十分不便，所以我们就定义一个动态的栈。

//动态栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//数组
	STDataType capacity;//容量空间大小
	STDataType top;//插入的元素的个数
}ST;

(2)、初始化栈

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

(3)、释放空间

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

(4)、进栈

void STPush(ST* ps, STDataType x)
{
	assert(ps);
    //在进栈之前先判定栈是否为满或者为空，如果栈满或空就得扩容
	if (ps->top == ps->capacity)
	{
//判定栈中空间是否为空，如果为空直接申请4个STDataType类型的空间，如果不为空就在原空间的基础上扩容2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

(5)、出栈

先断言栈是否初始化成功，其次再断言栈里面的数据个数是否大于0。如果栈中数据个数小于等于0，那top--就成负数。

void STPop(ST* ps)
{
	assert(ps);

	assert(ps->top > 0);

	--ps->top;
}

(6)、求栈的大小

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

(7)、求栈顶元素

STDataType STTop(ST* ps)
{
	assert(ps);

	assert(ps->top > 0);

	return ps->a[ps->top - 1];//因为是数组栈，如果要返回栈顶元素，则需要返回当前数组下标-1的元素
}

(8)、检查栈是否为空

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

三、完整代码

1、头文件

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

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//数组
	STDataType capacity;//容量空间大小
	STDataType top;//插入的元素的个数
}ST;

//初始化
void STInit(ST* ps);

//释放空间
void STDestroy(ST* ps);

//进栈
void STPush(ST* ps, STDataType x);

//出栈
void STPop(ST* ps);

//栈的大小
int STSize(ST* ps);

//获取栈顶元素
STDataType STTop(ST* ps);

//检查是否为空
bool STEmpty(ST* ps);

2、源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

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

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);

	assert(ps->top > 0);

	--ps->top;
}

STDataType STTop(ST* ps)
{
	assert(ps);

	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

 以上就是对栈的顺序存储的实现。如有错误，还请大家在评论区指出！！！