数据结构（栈的实现）

栈

栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对的另一端即为栈底。栈的模型：
数据结构（栈的实现）
栈的实现：

  #define _CRT_SECURE_NO_WARNINGS 1
    #include <stdlib.h>
    #include <stdio.h>
    #include <assert.h>
    
    typedef int STDataType;
    typedef struct Stack
    {
    STDataType* _a;
	int _top;
	int _capacity;
}Stack;

void StackInit(Stack* ps);     //初始化 
void StackDestory(Stack* ps);     // 销毁

void StackPush(Stack *ps, STDataType x);    //插入
void StackPop(Stack* ps);     //删除
STDataType  StackTop(Stack* ps);    //取栈顶元素
int StackEmpty(Stack* ps);    //置空

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

void StackPush(Stack *ps, STDataType x)
{
	assert(ps);
	if (ps->_top == ps->_capacity)   //栈满扩容
	{
		size_t newcapacity = (ps->_capacity == 0 ? 4 : ps->_capacity * 2);
		ps->_a = (STDataType*)realloc(ps->_a, sizeof(STDataType)*newcapacity);
		ps->_capacity = newcapacity;
	}
	ps->_a[ps->_top] = x;   //x放在栈顶
	ps->_top++;       // top指向栈顶元素的下一个位置
}

void StackPop(Stack* ps)
{
	assert(ps&&ps->_top>0);      //assert判断栈不为空
	ps->_top--;
}

STDataType  StackTop(Stack* ps)
{
	assert(ps&&ps->_top>0);
	return ps->_a[ps->_top - 1];    //取栈顶元素注意top的位置
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->_top == 0)
		return 0;
	else return 1;
}

数据结构（栈的实现）

栈

相关推荐