1. 栈的概念及结构

栈是一种特殊的线性结构, 只允许在固定的一端插入或者删除数据, 其固定的一端叫做栈顶, 另一端叫做栈底

插入删除数据操作在栈中，叫做入栈和出栈

栈中的数据元素遵守后进先出原则

2. 栈的实现

栈可以用数组或者链表，但是相较而言, 栈更适合用数组实现, 如下图

dys指向动态开辟的空间, capacity表示容量,不够时增容, top表示栈顶

下面具体实现

定义结构及接口

typedef int STDataType;
typedef struct stack
{
	STDataType* dys;
	int capacity;
	int top;
}stack;

// 初始化
void STInit(stack* ps);
// 销毁
void STDestroy(stack* ps);
// 入栈
void STPush(stack* ps, STDataType data);
// 出栈
void STPop(stack* ps);
// 取栈顶数据
STDataType STTop(stack* ps);
// 计算数据个数
void STSize(stack* ps);
// 判空
bool isSTEmpty(stack* ps);

栈初始化和销毁

// 初始化
void STInit(stack* ps)
{
	assert(ps);
	STDataType* tmp = (STDataType*)malloc(sizeof(STDataType) * 3);
	if (NULL == tmp)
	{
		perror("STInit::malloc fail");
		return;
	}
	ps->dys = tmp;
	ps->capacity = 3;
	ps->top = 0;
}
// 销毁
void STDestroy(stack* ps)
{
	assert(ps);
	free(ps->dys);
	ps->dys = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

判栈是否为空

top为0则表示栈为空

// 判空
bool isSTEmpty(stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

入栈和出栈

// 入栈
void STPush(stack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->dys, sizeof(STDataType) * ps->capacity * 2);
		if (NULL == tmp)
		{
			perror("STPush::realloc fail");
			return;
		}
		ps->dys = tmp;
		ps->capacity *= 2;
	}
	ps->dys[ps->top] = data;
	ps->top++;
}
// 出栈
void STPop(stack* ps)
{
	assert(ps);
	assert(!isSTEmpty(ps));
	ps->top--;
}

取栈顶元素

这里注意, top-1才是栈顶空间, top是下一个数据的空间

// 取栈顶数据
STDataType STTop(stack* ps)
{
	assert(ps);
	assert(!isSTEmpty(ps));
	return ps->dys[ps->top - 1];
}

完整代码

stack.h

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

typedef int STDataType;
typedef struct stack
{
	STDataType* dys;
	int capacity;
	int top;
}stack;

// 初始化
void STInit(stack* ps);
// 销毁
void STDestroy(stack* ps);
// 入栈
void STPush(stack* ps, STDataType data);
// 出栈
void STPop(stack* ps);
// 取栈顶数据
STDataType STTop(stack* ps);
// 计算数据个数
void STSize(stack* ps);
// 判空
bool isSTEmpty(stack* ps);

stack.c

 #include "stack.h"

// 初始化
void STInit(stack* ps)
{
	assert(ps);
	STDataType* tmp = (STDataType*)malloc(sizeof(STDataType) * 3);
	if (NULL == tmp)
	{
		perror("STInit::malloc fail");
		return;
	}
	ps->dys = tmp;
	ps->capacity = 3;
	ps->top = 0;
}
// 销毁
void STDestroy(stack* ps)
{
	assert(ps);
	free(ps->dys);
	ps->dys = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
// 入栈
void STPush(stack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->dys, sizeof(STDataType) * ps->capacity * 2);
		if (NULL == tmp)
		{
			perror("STPush::realloc fail");
			return;
		}
		ps->dys = tmp;
		ps->capacity *= 2;
	}
	ps->dys[ps->top] = data;
	ps->top++;
}
// 出栈
void STPop(stack* ps)
{
	assert(ps);
	assert(!isSTEmpty(ps));
	ps->top--;
}
// 取栈顶数据
STDataType STTop(stack* ps)
{
	assert(ps);
	assert(!isSTEmpty(ps));
	return ps->dys[ps->top - 1];
}
// 计算数据个数
void STSize(stack* ps)
{
	assert(ps);
	return ps->top;
}
// 判空
bool isSTEmpty(stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

test.c

 #include "stack.h"
int main()
{
	stack st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	while (!isSTEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st, 4);
	}
}

JZTXT

栈