C语言实现栈

1.栈的实现

这个栈是基于单向链表实现的 并且由于是对单向链表的头部指向相关的增删改查操作 所以复杂度都为O(1)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 我的栈是基于单向链表实现的 然后是在头部这一段进行相关栈的操作的
// 定义一个节点类
typedef struct Node {
	// 数据域
	int data;
	// 指针域
	struct Node* next;
}Node;
// 初始化栈
Node* initStack() {
	Node* stack = (Node*)malloc(sizeof(Node));
	stack->data = 0;
	stack->next = NULL;
	return stack;
}
// 压栈操作
void push(int data, Node* stack) {
	// 其实就是头插
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = stack->next;
	stack->next = node;
	// 更新栈的长度
	stack->data++;
}
// 弹栈操作
int pop(Node* stack) {
	// 首先的话 如果栈为空的话 那就弹栈失败
	if (stack->data == 0)return -1;
	// 获取待删除节点
	Node* node = stack->next;
	int delete = node->data;
	// 直接让虚拟头节点指向待删除节点的下一节点即可
	stack->next = node->next;
	// 销毁待删除节点的内存
	free(node);
	// 更新栈的长度
	stack->data--;
	// 返回待删除节点值
	return delete;
}
// 对栈进行判空操作
bool isEmpty(Node* stack) {
	return stack->data == 0;
}
// 对栈进行打印操作
void printStack(Node* stack) {
	Node* cur = stack->next;
	while (cur) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
// 定义一个主函数
int main() {
	// 将栈看成一个只能在头部进行操作的链表 其相关操作的时间复杂度为O(1)
	Node* stack = initStack();
	push(1, stack);// 1
	push(2, stack);// 2 1
	push(3, stack);// 3 2 1
	push(4, stack);// 4 3 2 1
	printStack(stack);// 4 3 2 1
	printf("%d\n", pop(stack));// 4
	printf("%d\n", pop(stack));// 3
	printStack(stack);// 2 1
	printf("%d\n", isEmpty(stack));// 0
	return 0;
}

测试是可以顺利通过的