c语言链栈

### C语言中链式栈的实现与用法 #### 1. 链式栈的基本概念 链式栈是一种基于链表的数据结构，其特点是动态分配内存空间，能够更高效地管理内存资源。相比于顺序栈（数组实现），链式栈不需要预先定义固定大小的空间[^2]。 #### 2. 链式栈的核心操作 以下是链式栈的主要功能及其对应的实现方法： - **初始化链式栈** 初始化链式栈时，创建一个头节点并将其指针设置为空。 ```c typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; } LinkStack; LinkStack* InitStack() { LinkStack *s = (LinkStack*)malloc(sizeof(LinkStack)); s->top = NULL; return s; } ``` - **入栈操作** 将新元素插入到链表头部的位置，使其成为新的栈顶元素。 ```c void Push(LinkStack *stack, int value) { StackNode *newNode = (StackNode*)malloc(sizeof(StackNode)); newNode->data = value; newNode->next = stack->top; stack->top = newNode; } ``` - **出栈操作** 删除当前栈顶元素，并返回该元素的值。如果栈为空，则抛出错误提示。 ```c int Pop(LinkStack *stack) { if (stack->top == NULL) { printf("Error: Stack is empty.\n"); exit(1); } StackNode *temp = stack->top; int poppedValue = temp->data; stack->top = temp->next; free(temp); return poppedValue; } ``` - **获取栈顶元素** 返回当前栈顶元素的值而不删除它。如果栈为空，则抛出错误提示。 ```c int GetTop(LinkStack *stack) { if (stack->top == NULL) { printf("Error: Stack is empty.\n"); exit(1); } return stack->top->data; } ``` - **判断栈是否为空** 判断栈是否有任何元素存在。 ```c bool IsEmpty(LinkStack *stack) { return stack->top == NULL; } ``` - **销毁链式栈** 清理整个链式栈所占用的内存空间。 ```c void DestroyStack(LinkStack *stack) { while (!IsEmpty(stack)) { Pop(stack); } free(stack); } ``` #### 3. 完整示例程序 以下是一个完整的链式栈实现及测试代码： ```c #include <stdio.h> #include <stdlib.h> typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; } LinkStack; // 初始化链式栈 LinkStack* InitStack() { LinkStack *s = (LinkStack*)malloc(sizeof(LinkStack)); s->top = NULL; return s; } // 入栈操作 void Push(LinkStack *stack, int value) { StackNode *newNode = (StackNode*)malloc(sizeof(StackNode)); newNode->data = value; newNode->next = stack->top; stack->top = newNode; } // 出栈操作 int Pop(LinkStack *stack) { if (stack->top == NULL) { printf("Error: Stack is empty.\n"); exit(1); } StackNode *temp = stack->top; int poppedValue = temp->data; stack->top = temp->next; free(temp); return poppedValue; } // 获取栈顶元素 int GetTop(LinkStack *stack) { if (stack->top == NULL) { printf("Error: Stack is empty.\n"); exit(1); } return stack->top->data; } // 判断栈是否为空 bool IsEmpty(LinkStack *stack) { return stack->top == NULL; } // 销毁链式栈 void DestroyStack(LinkStack *stack) { while (!IsEmpty(stack)) { Pop(stack); } free(stack); } // 测试函数 int main() { LinkStack *s = InitStack(); Push(s, 10); Push(s, 20); Push(s, 30); printf("Top element is %d\n", GetTop(s)); // 输出栈顶元素 Pop(s); // 移除栈顶元素 printf("After pop operation, top element is %d\n", GetTop(s)); DestroyStack(s); return 0; } ``` #### 4. 应用场景举例 链式栈常用于解决实际编程中的问题，例如括号匹配验证、进制转换等[^3][^5]。 ##### 括号匹配验证 通过链式栈可以轻松检测字符串中的括号是否成对闭合。 ##### 进制转换 利用链式栈可将十进制数转化为其他进制表示形式。 ---