栈-C

栈(Stack)是一种限制插入和删除只能在一个位置上进行操作的表

将他抽象出来类似一个罐子，并且每次存储东西只能将新的物品堆在前一个物品之上，所以这个罐子的出口和入口是同一个，也就意味着每次操作都必须从最顶上的物品开始，最顶上的那个物品我们把它叫做栈顶

如果玩射击游戏的话可以把他理解为是一个弹夹 🔫

但是这只是他在逻辑上的形式，如果将他存储在内存中还是要使用表的形式

如果将抽象的栈转换成表的形式就会如下所示
栈顶的位置：

数组栈就是在数组的末尾
链表栈就是在链表的第一个节点(有头节点就是第二个)

栈的操作

对栈的基本操作一般只有Push(进栈)和Pop(出栈)

进栈：就相当于是插入
出栈：就相当于是删除最后插入的节点

数组栈

数据栈的结构体

typedef struct Stack {
	Elemtype elem[Stack_Size];
	int top;
}Sqstack;

elem[Stack_Size]：用来存储栈元素的数组
top：表示栈顶元素的下标

初始化

数组栈的初始化就是给结构体实例化，并且将stack这个指针指向了这个实例化的结构体，并且将栈顶设置为-1表示目前还只是一个空栈

int InitStack(Sqstack **stack) {
	if ( (*stack = (Sqstack*)malloc(sizeof(Sqstack))) == NULL) {
		return 0;
	}
	else {
		(*stack)->top = -1;
		return 1;
	}
}

进栈

int Push(Sqstack *stack,Elemtype elem) {
	if (stack->top == Stack_Size - 1) { //判断数组是否达到长度限制
		return 0;
	}
	else {
		stack->top++;
		stack->elem[stack->top] = elem;
		return 1;
	}
}

进栈的逻辑如下所示：

栈顶对应的下标+1
将elem赋值给当前栈顶所对应的下标的位置

出栈

int Pop(Sqstack *stack, Elemtype *elem) {
	if (EmptyStack(*stack)) {
		return 0;
	}
	else {
		*elem = stack->elem[stack->top];
		stack->top--;
		return 1;
	}
}

EmptyStack(*stack)用来判断是不是空栈，只需要判断top是否等于-1即可

出栈的逻辑如下所示：

将top的数据赋值给*elem
栈顶对应的下标-1，相当于将原来栈顶给隐藏掉了，将原栈顶的前一个作为新的栈顶

红色为出栈前
蓝色为出栈后

链表栈

链表栈的结构体

typedef struct StackNode {
	ElemType data;
	struct StackNode* next;
}StackNode;

typedef struct {
	StackNode* top;
}LinkStack;

初始化

链表栈的初始化就是给结构体实例化，并且将stack->top这个指针指向了这个实例化的结构体，并且将栈顶设置为NULL表示目前还只是一个空栈

1
2
3

int InitStack(LinkStack* stack) {
	stack->top = NULL;
}

进栈

int Push(LinkStack *stack,ElemType elem){
	StackNode* node = (StackNode*)malloc(sizeof(StackNode));
	node->data = elem;
	node->next = stack->top;
	stack->top = node;
}

进栈的逻辑如下所示：

实例化一个新节点node，并把数据赋值给node->data
将node->next指向top指向的节点
最后把stack->top指向node

最后呈现的结果如下图所示

出栈

int Pop(LinkStack* stack, ElemType* elem) {
	StackNode* free_node;
	if (EmptyStack(*stack)) {
		return 0;
	}
	else {
		free_node = stack->top;
		*elem = free_node->data;

		stack->top = free_node->next;

		free(free_node);
		return 1;
	}
}