栈的操作实现

栈的概念

栈是一种后进先出（LIFO）的线性数据结构，只允许在一端（栈顶）进行插入和删除操作。新元素总是添加到栈顶，而删除也总是从栈顶移除最上面的元素。栈常用于函数调用、表达式求值、括号匹配等场景。

代码实现---顺序存储（Array-based Stack）

#include <stdio.h>	// 标准输入输出库，用于 printf 等函数
#include <stdbool.h>// 布尔类型库，提供 bool、true、false
#include <stdlib.h> // 标准库，提供 malloc/calloc/free 和 exit 等函数
// 定义栈元素的类型为 int
typedef int DataType_t; 
// 定义栈的元素结构体
typedef struct SequenceStack 
{
	DataType_t *Bottom;
	unsigned int Size;
	int 	 Top;
} SeqStack_t;
SeqStack_t* SeqStack_init(unsigned int size)
{
	//calloc 返回的是 void * 类型指针，可以隐式转换为任何其他指针类型（如 int*、char*），所以强制类型转换不是必须的
	SeqStack_t *Manager = (SeqStack_t *)calloc(1,sizeof(SeqStack_t));
	if(Manager == NULL){
	perror("calloc for Manager is failed!\n");
	exit(-1);
	}
	Manager->Bottom = (DataType_t *)calloc(size,sizeof(DataType_t));
	
	if(Manager->Bottom == NULL){
	perror("calloc for stackEelement is failed\n");
	free(Manager);
	exit(-1);
	}
	Manager->Size = size; 
	Manager->Top = -1;//没有元素，初始化为-1，新增一个元素后下标就可以等于0
	return Manager;
}
//判断栈是不是满
bool SeqStackIsfull(SeqStack_t *Manager)
{
	//假设stacksize是8，Top的值已经为7，则栈满
	return (Manager->Top+1 == Manager->Size)?true:false;
}
//判断栈是不是空
bool SeqStackIsEmpty(SeqStack_t *Manager)
{
	//Top初始值为-1，下次判断依然是-1则栈是空
	return (Manager->Top == -1)?true:false;
}
//入栈
bool SeqStack_Push(SeqStack_t *Manager,DataType_t data)
{	
	//添加元素需要先判断栈有没有满
	if(SeqStackIsfull(Manager)){
	printf("SeqStack is Full!\n");
	return false;
	}
	Manager->Bottom[++Manager->Top] = data;
	return true;
}
//出栈
DataType_t SeqStack_Pop(SeqStack_t *Manager)
{
	if (SeqStackIsEmpty(Manager)) {
 printf("SeqStack is Empty!\n");
 return; 
	}
	//栈顶元素出栈，Top-1
	DataType_t temp = Manager->Bottom[Manager->Top--];
	
	return temp; 
}
//遍历栈
void SeqStack_Print(SeqStack_t *Manager)
{
	for(int i=0;i<= Manager->Top;i++){
	printf("Stack Element[%d] = %d\n",i,Manager->Bottom[i]);
	}
}
int main(int argc, char const *argv[])
{
 // 初始化大小为 4 的栈
 SeqStack_t *stack = SeqStack_init(4);
 // 测试空栈出栈
 printf("尝试从空栈出栈:\n");
 SeqStack_Pop(stack);
 // 入栈测试
 printf("入栈: 10, 20, 30\n");
 SeqStack_Push(stack, 10);
 SeqStack_Push(stack, 20);
 SeqStack_Push(stack, 30);
 // 打印栈
 printf("当前栈内容:\n");
 SeqStack_Print(stack);
 // 测试栈满
 printf("继续入栈: 40, 50\n");
 SeqStack_Push(stack, 40);
 SeqStack_Push(stack, 50); // 应提示栈满
 // 出栈两次
 printf("出栈两次:\n");
 printf("出栈元素: %d\n", SeqStack_Pop(stack));
 printf("出栈元素: %d\n", SeqStack_Pop(stack));
 // 再打印栈
 printf("出栈后内容:\n");
 SeqStack_Print(stack);
 return 0;
}

运行结果

代码实现---链式存储（Linked Stack）

/**
 * @fire name:Linkedstack.c
 * @brief:/**
 * @fire name:SeqList.c
 * @brief:这个程序实现栈的入栈、出栈（链式存储）
 * @author:13642563766@163.com
 * @date:2025/7/18
 * @version:1.0
 * @note:None
 * Copyright (c) 2021-2022 13642563766@163.com All right Reserved
 */
#include <stdio.h>
#include <stdlib.h>
// 定义栈中存储的数据类型为 int
typedef int DataType;
// 链栈的节点结构体：每个节点包含数据和指向下一个节点的指针
typedef struct StackNode {
	DataType	data;
	struct StackNode *next;
}StackNode;
// 链栈管理结构体：用于管理整个栈的状态
typedef struct{
	int size;
	StackNode *top;// 指向栈顶节点的指针（NULL 表示空栈）
}LinkedStack;
// 为 LinkedStack* 定义别名 Stack，表示一个栈的指针
typedef LinkedStack* Stack;
/**
 * 初始化栈
 * @param s 指向栈指针的指针（二级指针），用于返回栈的地址
 * @return 成功返回 1，失败返回 0
 */
int InitStack(Stack *s)
{
	*s = (Stack)malloc(sizeof(LinkedStack));
	if(*s == NULL){
	return 0;
	}
	(*s)->top = NULL;
	(*s)->size = 0;
	return 1;
}
/**
 * 入栈操作：将一个新元素压入栈顶
 * @param s 栈指针
 * @param data 要入栈的数据
 * @return 成功返回 1，失败返回 0
 */
int Push(Stack s, DataType data) 
{
	if (s == NULL) {
 return 0; // 指针无效
 }
 StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
 if (newNode == NULL) {
 return 0; // 指针无效
 }
 // 设置新节点的数据和指针
 newNode->next = s->top;/
 newNode->data = data;
 s->top = newNode;//更新top指向新结点
 s->size++;//每入栈一个元素size++
 return 1;
}
/**
 * 出栈操作：弹出栈顶元素，并通过指针返回其值
 * @param s 栈指针
 * @param data 用于接收出栈元素值的输出参数
 * @return 成功返回 1，栈为空或指针无效返回 0
 */
int Pop(Stack s, DataType *data)
{
	if(s == NULL || s->top == NULL){
	return 0; // 栈为空或栈指针无效，无法出栈
	}
 // 保存当前栈顶节点，便于后续释放
	StackNode *Temp = s->top;
 // 将栈顶指针移动到下一个节点
	s->top = s->top->next;
	*data = Temp->data;
	free(Temp);
	s->size--;
	return 1;
}
//获得栈顶元素的值
int GetTop(Stack s, DataType *data)
{
	if(s == NULL || s->top == NULL){
	return 0; // 栈为空或栈指针无效
	}
	*data = s->top->data;
	return 1;
}
int IsEmpty(Stack s) 
{
	if(s == NULL){
	 return 1;
	}
	return(s->top == NULL);
}
/**
 * 销毁整个栈，释放所有内存
 * @param s 指向栈的指针的指针
 */
void DestroyStack(Stack *s) {
 if (s == NULL || *s == NULL) {
 return;
 }
 StackNode *current = (*s)->top;
 StackNode *next;
 // 逐个释放节点
 while (current != NULL) {
 next = current->next;
 free(current);
 current = next;
 }
 // 释放栈结构本身
 free(*s);
 *s = NULL; // 防止野指针
}
int main() {
 Stack myStack;
 DataType value;
 // 1. 初始化栈
 if (!InitStack(&myStack)) {
 printf("初始化栈失败！\n");
 return -1;
 }
 printf("栈初始化成功。\n");
 // 2. 入栈操作
 printf("入栈: 10, 20, 30\n");
 Push(myStack, 10);
 Push(myStack, 20);
 Push(myStack, 30);
 // 3. 查看栈顶元素
 if (GetTop(myStack, &value)) {
 printf("当前栈顶元素: %d\n", value);
 } else {
 printf("栈为空，无法获取栈顶元素。\n");
 }
 // 4. 出栈操作
 printf("开始出栈:\n");
 while (!IsEmpty(myStack)) {
 if (Pop(myStack, &value)) {
 printf("弹出: %d\n", value);
 }
 }
 // 5. 再次尝试出栈 (栈已空)
 if (Pop(myStack, &value)) {
 printf("弹出: %d\n", value);
 } else {
 printf("栈已空，无法弹出元素。\n");
 }
 // 6. 销毁栈
 DestroyStack(&myStack);
 printf("栈已销毁。\n");
 return 0;
}

运行结果