引言
堆栈是计算机科学中一种基本的数据结构，它遵循后进先出（LIFO）的原则。在C语言编程中，堆栈的应用非常广泛，从简单的函数调用到复杂的算法实现，都离不开堆栈的支持。本文将通过实战例题解析，帮助读者深入理解C语言堆栈的原理与应用，轻松掌握数据结构精髓。
堆栈基础知识
1.1 栈的定义
栈是一种线性数据结构，它支持两种基本操作：入栈（push）和出栈（pop）。栈中的元素按照插入顺序排列，最后插入的元素最先被移除。
1.2 栈的实现
在C语言中，栈可以通过数组或链表实现。数组实现的栈称为顺序栈，链表实现的栈称为链栈。
1.3 栈的属性
- 栈是先进后出的数据结构。
- 栈具有固定的容量，超过容量将无法继续添加元素。
- 栈的操作包括：初始化、入栈、出栈、判断是否为空、判断是否已满等。
顺序栈的实现
顺序栈使用数组实现，以下是一个简单的顺序栈实现示例：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int top;
} SeqStack;
// 初始化栈
void InitStack(SeqStack *s) {
s->top = -1;
}
// 判断栈是否为空
int IsEmpty(SeqStack *s) {
return s->top == -1;
}
// 判断栈是否满
int IsFull(SeqStack *s) {
return s->top == MAXSIZE - 1;
}
// 入栈
void Push(SeqStack *s, int x) {
if (IsFull(s)) {
printf("栈满，无法入栈。\n");
return;
}
s->data[++s->top] = x;
}
// 出栈
int Pop(SeqStack *s) {
if (IsEmpty(s)) {
return -1;
}
return s->data[s->top--];
}
链栈的实现
链栈使用链表实现，以下是一个简单的链栈实现示例：
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} LsNode;
typedef struct {
LsNode *base;
LsNode *top;
int stackSize;
} LStack;
// 创建栈
LStack *CreateLsStack() {
LStack *s = (LStack *)malloc(sizeof(LStack));
s->base = (LsNode *)malloc(sizeof(LsNode));
if (!s->base) {
printf("内存分配失败。\n");
exit(0);
}
s->base->next = NULL;
s->top = s->base;
s->stackSize = 0;
return s;
}
// 元素进栈
int Pus
// 初始化栈
void StackInit(ST *ps) {
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
// 入栈
int Push(ST *ps, Datatype x) {
if (ps->top == ps->capacity - 1) {
return ERROR;
}
ps->arr[++ps->top] = x;
return OK;
}
// 出栈
int Pop(ST *ps, Datatype *x) {
if (ps->top == -1) {
return ERROR;
}
*x = ps->arr[ps->top--];
return OK;
}
// 销毁栈
void StackDestroy(ST *ps) {
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
实战例题解析
例题1：实现一个函数，判断一个字符串是否为有效的括号序列。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
typedef struct {
char data[MAXSIZE];
int top;
} SeqStack;
void InitStack(SeqStack *s) {
s->top = -1;
}
int IsEmpty(SeqStack *s) {
return s->top == -1;
}
int IsFull(SeqStack *s) {
return s->top == MAXSIZE - 1;
}
void Push(SeqStack *s, char x) {
if (IsFull(s)) {
printf("栈满，无法入栈。\n");
return;
}
s->data[++s->top] = x;
}
char Pop(SeqStack *s) {
if (IsEmpty(s)) {
return -1;
}
return s->data[s->top--];
}
int isValid(char *s) {
SeqStack stack;
InitStack(&stack);
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
Push(&stack, s[i]);
} else if (s[i] == ')' || s[i] == '}' || s[i] == ']') {
if (IsEmpty(&stack)) {
return 0;
}
char c = Pop(&stack);
if ((s[i] == ')' && c != '(') || (s[i] == '}' && c != '{') || (s[i] == ']' && c != '[')) {
return 0;
}
}
}
return IsEmpty(&stack);
}
int main() {
char *s1 = "{[]}";
char *s2 = "{[)]}";
printf("s1: %s\n", isValid(s1) ? "有效" : "无效");
printf("s2: %s\n", isValid(s2) ? "有效" : "无效");
return 0;
}
例题2：实现一个函数，计算逆波兰表达式（后缀表达式）的值。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int top;
} SeqStack;
void InitStack(SeqStack *s) {
s->top = -1;
}
int IsEmpty(SeqStack *s) {
return s->top == -1;
}
int IsFull(SeqStack *s) {
return s->top == MAXSIZE - 1;
}
void Push(SeqStack *s, int x) {
if (IsFull(s)) {
printf("栈满，无法入栈。\n");
return;
}
s->data[++s->top] = x;
}
int Pop(SeqStack *s) {
if (IsEmpty(s)) {
return -1;
}
return s->data[s->top--];
}
int precedence(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*' || op == '/') {
return 2;
}
return 0;
}
int evaluate(char *exp) {
SeqStack stack;
InitStack(&stack);
for (int i = 0; exp[i] != '\0'; i++) {
if (isdigit(exp[i])) {
Push(&stack, exp[i] - '0');
} else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') {
int a = Pop(&stack);
int b = Pop(&stack);
int result = 0;
switch (exp[i]) {
case '+':
result = b + a;
break;
case '-':
result = b - a;
break;
case '*':
result = b * a;
break;
case '/':
result = b / a;
break;
}
Push(&stack, result);
}
}
return Pop(&stack);
}
int main() {
char *exp1 = "3+5*8";
char *exp2 = "3+5*8-2/4";
printf("exp1: %d\n", evaluate(exp1));
printf("exp2: %d\n", evaluate(exp2));
return 0;
}
总结
通过以上实战例题解析，相信读者已经对C语言堆栈的原理与应用有了更深入的理解。在实际编程中，熟练掌握堆栈数据结构，将有助于解决各种复杂问题。