栈的概念及结构

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

（封闭了一端的线性表）

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
 

图示

分析

栈是线性表，用动态数组实现更优。

需要动态开辟，需要记录有效元素个数、空间容量、还有栈顶位置。

可参考顺序表来进行理解：顺序表的实现_i跑跑的博客-CSDN博客

栈的实现

定义

起始位置，栈顶位置（用下标进行操作），容量。

typedef struct Stack
{
	Datatype* a;
	int top;   //栈顶位置
	int capacity;   //容量
}ST;

初始化

起始位置置空，容量为0，栈顶在下标为0的位置。

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

销毁

从起始位置开始释放掉，因为是连续开辟空间，释放起始位置即释放所有开辟的空间

容量和栈顶置0

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

压栈

断言后，首先得检查容量是否够用，不够需要realloc空间，空间不足时若=0，则给4个Datatype类型大小的空间，若不等于0，则给定已有空间的二倍的空间大小。

空间解决后，存入数据，并更新栈顶。

//压栈
void StackPush(ST* ps, Datatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = realloc(ps->a, newcapacity*sizeof(Datatype));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

出栈

要注意不仅要断言ps，还需要保证栈顶大于0，即栈内不为空。

因为开辟空间连续，不能单独释放，因此我们直接更新栈顶即可。

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;
}

判断栈是否为空

是空返回true，非空返回false

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

 数据个数

数据个数直接为栈顶top的下标

//数据个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

访问栈顶元素

栈顶元素是栈顶的前一个，top-1即为栈顶元素的下标

//访问栈顶数据
Datatype StackTop(ST* ps)
{
	assert(ps);
	return ps->a[ps->top-1];
}

头文件

#pragma once

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

typedef int Datatype;

typedef struct Stack
{
	Datatype* a;
	int top;   //栈顶位置
	int capacity;   //容量
}ST;

void StackInit(ST* ps);

void StackDestory(ST* ps);

void StackPush(ST* ps,Datatype x);

void StackPop(ST* ps);

//判断栈是否为空
bool StackEmpty(ST* ps);

//数据个数
int StackSize(ST* ps);

//访问栈顶数据
Datatype StackTop(ST* ps);

测试文件 

#include "Stack.h"


void TestStack()
{
	ST st;
	StackInit(&st);
	StackPush(&st,1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	while (!StackEmpty(&st))
	{
		printf("%d ",StackTop(&st));
		StackPop(&st);
	}

	StackDestory(&st);
}



int main()
{
	TestStack();
	return 0;
}