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));
	}
}

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