栈的简单实现-ag真人游戏

栈的概念及结构

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

（封闭了一端的线性表）

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

图示

分析

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

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

可参考顺序表来进行理解：顺序表的实现_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 
#include 
#include 
#include 
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;
}