栈的实现

栈

1.栈的概念及结构

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

2.栈的实现

栈的实现一般使用数组和链表，相对而言使用数组更优一些，因为数据在尾插时的代价小一些。
当然。栈也可以用链表实现，但注意，单链表实现栈顶只可以是头，如果不这样写起来会很麻烦。但是双向链表栈顶可以是头也可以是尾。

下面用数组的方式实现一个栈。

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

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;   //存储数据的数组
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
//栈的释放
void Destroy(Stack* ps);
//删除一个元素（尾删）
void STpop(Stack* ps);
//统计栈中的元素个数
int STsize(Stack* ps);
//获取栈顶元素
STDataType STTop(Stack* ps);
//判断栈是否为空
bool STEmpty(Stack* ps);

栈的初始化

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

初始化top时要注意，如果令top=-1，那代表top指向栈顶元素。如果top=0，那么则指向栈顶的后一个元素

向栈顶插入数据

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)    //如果栈的空间不够了就进行扩容
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tem = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tem == NULL)    //扩容失败
		{
			perror(ps);
			return;

		}
		ps->a = tem;
		ps->capacity = newcapacity;

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

释放栈顶元素

void STpop(Stack* ps)
{
	assert(ps);
	assert(ps->capacity > 0);
	assert(ps->top>0);
	ps->top--;
}

销毁栈

void Destroy(Stack* ps)
{
	assert(ps);
	free(ps->a);

	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;

}

由于是数组栈，所以只要释放掉结构体就可以

判断栈是否为空

bool STEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

获取栈顶元素

int  STTop(Stack* ps)
{
	assert(ps);
	return ps->a[ps->top - 1];

}

统计栈中元素个数

int STsize(Stack* ps)
{
	assert(ps);
	return ps->top;

}