C语言——栈的实现

时间：2024-05-02 13:46:51

栈（Stack）是一种基于先进后出（LIFO）原则的数据结构，类似于我们平常堆放书籍或者盘子的方式。

栈通常是从高地址向低地址增长的，也就是说，栈顶位于较高的内存地址，而栈底位于较低的内存地址。这种结构通常被称为“向下生长的栈”或者“递减栈”。

下面是入栈的示意图，出栈可以理解为是入栈的逆过程。

按照我们现有的知识来看，我们可以用顺序表也可以使用链表，那么对于栈来说，删除和增加尾部元素比较频繁因为是先入先出，并且访问简单，结构简单，所以我们可以考虑使用顺序表（当然也可以使用链表，这里用顺序表举例）。

首先是栈的创建和初始化，销毁函数：

struct Stacklist {
	char* val;
	int size;
	int cap;
};
void StackInit(struct Stacklist* stack){
	stack->cap = 0;
	stack->size = 0;
	stack->val = NULL;
}
void StackDes(struct Stacklist* stack) {
	free(stack->val);
	stack->val = NULL;
}

这里的 size 是Stack已有元素的个数，cap 是Stack的容量，val 是储存的字符。这三个函数还是比较容易理解的。

接下来是栈的空间检查和入栈函数（尾插函数，因为是先入后出，后入先出）：

void StackCheck(struct Stacklist* stack) {
	if (stack->cap == stack->size) {
		if (stack->cap == 0) {
			stack->cap = 4;
			stack->val = (char*)malloc(sizeof(char) * stack->cap);
		}
		else {
			stack->val = (char*)realloc(stack->val,sizeof(char)*stack->cap*2);
			stack->cap = stack->cap * 2;
		}
	}
}
void StackPush(struct Stacklist* stack,char a) {
	StackCheck(stack);
	(stack->val)[stack->size] = a;
	stack->size++;
}

在 StackCheck 函数中，如果cap和size都为空，那么就默认创建4个char字符空间给stack->val，
如果cap和size虽然相等但都不为0，那么就默认扩容两倍，stack->val = (char*)realloc(stack->val,sizeof(char)*stack->cap*2);

在StackPush入栈函数中，先检查空间是否足够，然后赋值，size++，

接下来是出栈函数：

char StackPop(struct Stacklist* stack) {
	stack->size--;
	return (stack->val)[stack->size];
}

 让size--，返回 char 字符，这里需要注意：前面的代码当压入栈第一个数据时size是1，出栈时是要用size--访问的，所以先自减，再直接返回就是栈顶的值。

最后是Print函数：

void StackPrint(struct Stacklist* stack) {
	for (stack->size; stack->size>0;) {
		printf("%c ", StackPop(stack));
	}
}

这就是文章的全部内容了，感谢阅读，如有错误欢迎指出。

相关文章