大话数据结构之 ＜ 栈＞（C语言）

引言：栈（Stack）是一种重要的线性数据结构，它遵循 **“后进先出”（Last In, First Out，简称 LIFO）** 的原则，即最后放入栈中的元素会最先被取出。这种特性使得栈在很多场景中都有广泛应用，比如程序调用的栈帧管理、表达式求值、括号匹配等。本章介绍栈，包括其实现。

• 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈：栈的删除操作叫做出栈。出数据也在栈顶

2.栈的实现

数组实现（静态顺序栈）

#include <stdio.h>
#include <stdbool.h>#define MAX_SIZE 100  // 栈的最大容量// 数组实现的栈结构
typedef struct {int data[MAX_SIZE];  // 静态数组存储栈元素int top;             // 栈顶指针
} ArrayStack;// 初始化栈
void initArrayStack(ArrayStack *stack) {stack->top = -1;  // 初始化为-1表示空栈
}// 判断栈是否为空
bool isArrayStackEmpty(ArrayStack *stack) {return stack->top == -1;
}// 判断栈是否已满
bool isArrayStackFull(ArrayStack *stack) {return stack->top == MAX_SIZE - 1;
}// 入栈操作
bool pushArrayStack(ArrayStack *stack, int value) {if (isArrayStackFull(stack)) {printf("栈已满，无法入栈！\n");return false;}stack->data[++stack->top] = value;return true;
}// 出栈操作
bool popArrayStack(ArrayStack *stack, int *value) {if (isArrayStackEmpty(stack)) {printf("栈为空，无法出栈！\n");return false;}*value = stack->data[stack->top--];return true;
}// 获取栈顶元素
bool peekArrayStack(ArrayStack *stack, int *value) {if (isArrayStackEmpty(stack)) {printf("栈为空！\n");return false;}*value = stack->data[stack->top];return true;
}// 打印栈内容
void printArrayStack(ArrayStack *stack) {if (isArrayStackEmpty(stack)) {printf("栈为空！\n");return;}printf("栈内容(从栈底到栈顶): ");for (int i = 0; i <= stack->top; i++) {printf("%d ", stack->data[i]);}printf("\n");
}

链表实现（静态链表栈）

#include <stdio.h>
#include <stdbool.h>#define MAX_NODES 100  // 最大节点数// 链表节点结构
typedef struct StackNode {int data;int next;  // 使用数组下标代替指针
} StackNode;// 链表实现的栈结构
typedef struct {StackNode nodes[MAX_NODES];  // 节点池int top;                     // 栈顶节点下标int freeList;                // 空闲节点链表头int size;                    // 当前栈大小
} LinkedStack;// 初始化栈
void initLinkedStack(LinkedStack *stack) {stack->top = -1;  // 空栈stack->size = 0;// 初始化空闲链表for (int i = 0; i < MAX_NODES - 1; i++) {stack->nodes[i].next = i + 1;}stack->nodes[MAX_NODES - 1].next = -1;  // 结束标记stack->freeList = 0;  // 第一个空闲节点
}// 从空闲链表分配一个节点
int allocateNode(LinkedStack *stack) {if (stack->freeList == -1) {return -1;  // 没有空闲节点}int nodeIndex = stack->freeList;stack->freeList = stack->nodes[nodeIndex].next;return nodeIndex;
}// 释放节点到空闲链表
void freeNode(LinkedStack *stack, int nodeIndex) {stack->nodes[nodeIndex].next = stack->freeList;stack->freeList = nodeIndex;
}// 判断栈是否为空
bool isLinkedStackEmpty(LinkedStack *stack) {return stack->top == -1;
}// 判断栈是否已满
bool isLinkedStackFull(LinkedStack *stack) {return stack->freeList == -1;
}// 入栈操作
bool pushLinkedStack(LinkedStack *stack, int value) {if (isLinkedStackFull(stack)) {printf("栈已满，无法入栈！\n");return false;}int newNode = allocateNode(stack);stack->nodes[newNode].data = value;stack->nodes[newNode].next = stack->top;stack->top = newNode;stack->size++;return true;
}// 出栈操作
bool popLinkedStack(LinkedStack *stack, int *value) {if (isLinkedStackEmpty(stack)) {printf("栈为空，无法出栈！\n");return false;}int topNode = stack->top;*value = stack->nodes[topNode].data;stack->top = stack->nodes[topNode].next;freeNode(stack, topNode);stack->size--;return true;
}// 获取栈顶元素
bool peekLinkedStack(LinkedStack *stack, int *value) {if (isLinkedStackEmpty(stack)) {printf("栈为空！\n");return false;}*value = stack->nodes[stack->top].data;return true;
}// 打印栈内容
void printLinkedStack(LinkedStack *stack) {if (isLinkedStackEmpty(stack)) {printf("栈为空！\n");return;}printf("栈内容(从栈顶到栈底): ");int current = stack->top;while (current != -1) {printf("%d ", stack->nodes[current].data);current = stack->nodes[current].next;}printf("\n");
}

这两种静态实现方式都不使用动态内存分配(malloc/free)，适合在资源受限的环境中使用，如嵌入式系统。 

推荐优先使用动态数组实现栈，除非：
1. 栈大小变化极其剧烈且不可预测
2. 元素非常大（移动成本高）
3. 有严格的无上限要求
动态数组实现提供了更好的综合性能，而现代内存分配器和扩容策略（如倍增法）已经大大减少了其缺点。在C语言中，通过合理的realloc策略可以实现高效的动态数组栈。

选择哪种实现取决于具体应用场景、性能要求和资源限制。在大多数现代应用中，动态实现更为常用，因为它提供了更大的灵活性。而在嵌入式系统或对性能有严格要求的场景中，静态实现可能更合适。下面我们来看一下动态实现栈：

3. 动态实现栈（数组）

 #include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//基本操作： 
// 1.初始化
// 2.销毁
// 3.判空
// 4.压栈
// 5.出栈
// 6.返回栈顶元素
// 7.返回栈中元素个数 //用顺序表实现栈
//栈的性质：后进先出 typedef int STDataType;typedef struct stack{STDataType* a;//指向栈底位置        int top;//已有栈顶元素的个数           int capacity;// 栈容量           }ST;//栈的初始化-- 和顺序表的一系列操作差不多 
void STInit(ST* ps)
{assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType)*4);if(ps->a == NULL){perror("malloc fail");return;} ps->capacity = 4;//初始化容量为4 ，不够再扩容//ps->top = 0;//top是栈顶元素下一个 ps->top = -1;//top是栈顶元素 }//栈的销毁 
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a=NULL;ps->top=ps->capacity = 0;}//判空 
bool STEmpty(ST* ps)
{assert(ps);return ps->a[ps->top] == 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if(ps->top + 1 == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType)*ps->capacity*2);if(tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2; }ps->a[ps->top+1] = x;ps->top++;
}//出栈 
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;}//栈中元素个数 
int STSize(ST* ps)
{assert(ps);return ps->top+1;
}//栈顶元素 
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));	return ps->a[ps->top];
}int main()
{ST st;STInit(&st);//初始化//压栈-- 向栈中放入数据STPush(&st,1); STPush(&st,2); STPush(&st,3); STPush(&st,4); STPush(&st,5); //取栈顶元素//根据栈的性质  top == 5 // 打印出来看一下printf("%d\n",STTop(&st));//出栈--弹出栈顶元素STPop(&st);STPop(&st);//Pop两次 -- 那么此时栈顶的元素应该为 3//打印出来看一下printf("%d\n",STTop(&st));STPop(&st);//此时栈中应该只有两个元素了//打印栈中元素的个数printf("%d\n",STSize(&st));//最终结果为 5 //           3//			   2 //销毁栈STDestroy(&st);//以上为一个栈从创建到销毁的完整的过程//能够完成栈的基本操作 return 0;}