实现一个可以动态增长的栈以及栈的基本操作

头文件:

#pragma once
#include<stdio.h>
#include<windows.h>
#include<assert.h>
#include<malloc.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 StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

一些基本操作:

栈的初始化与销毁:

//栈的初始化

void StackInit(Stack* ps){
	assert(ps);
	ps->_a = (STDataType*)malloc(sizeof(STDataType)* 3);
	if (NULL == ps->_a){
		assert(0);
		return;
	}
	ps->_capacity = 3;
	ps->_top = 0;
}


//栈的销毁

void StackDestroy(Stack* ps){
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}

入栈(需要判断栈是否满了,满了则需要对栈扩容)

//栈满了申请新的空间
void BuySize(Stack*ps){
	//1.申请新空间
	int newsize = (ps->_capacity) * 2;
	STDataType*new_a = (STDataType*)malloc(sizeof(STDataType)*newsize);
	if (NULL==new_a){
		assert(0);
		return ;
	}
	//2.数据的拷贝
	new_a = (STDataType*)memcpy(new_a, ps->_a, ps->_capacity);
	//3.释放旧空间
	free(ps->_a);
	ps->_a = new_a;
	//4.新空间的使用
	ps->_capacity = newsize;
}

void StackInit(Stack* ps){
	assert(ps);
	ps->_a = (STDataType*)malloc(sizeof(STDataType)* 3);
	if (NULL == ps->_a){
		assert(0);
		return;
	}
	ps->_capacity = 3;
	ps->_top = 0;
}


static int StactFull(Stack*ps){
	return ps->_capacity == ps->_top;
}

//入栈
void StackPush(Stack* ps, STDataType data){
	if (StactFull(ps))
	{
		//如果栈满了则需要扩容
		BuySize(ps);
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}

出栈(需要判断栈是否为空): 

//判断栈是否为空
int StackEmpty(Stack* ps){
	assert(ps);
	return 0==ps->_top;
}


//出栈
void StackPop(Stack* ps){
	if (StackEmpty(ps))
	{
		return;
	}
	ps->_top--;
}

获取栈顶元素:

// 获取栈顶元素 
STDataType StackTop(Stack* ps){
	assert(!StackEmpty(ps));
	return ps->_a[ps->_top-1];
}

获取栈中有效元素的个数:

// 获取栈中有效元素个数 
int StackSize(Stack* ps){
	return ps->_top;
}

上一篇:ps -ef|grep详解


下一篇:如何修改网页源代码