[教程]掌握C语言栈，轻松应对编程挑战

引言在编程语言中，栈（Stack）是一种常用的数据结构，它遵循后进先出（LIFO）的原则。C语言作为一种基础且强大的编程语言，提供了栈的多种实现方式。掌握C语言栈的使用，可以帮助程序员在解决编程挑战时...

引言

在编程语言中，栈（Stack）是一种常用的数据结构，它遵循后进先出（LIFO）的原则。C语言作为一种基础且强大的编程语言，提供了栈的多种实现方式。掌握C语言栈的使用，可以帮助程序员在解决编程挑战时更加得心应手。本文将详细介绍C语言栈的概念、实现方法以及在实际编程中的应用。

一、栈的基本概念

1.1 定义

栈是一种线性数据结构，允许在表的开始端进行插入和删除操作。这种数据结构被称为“栈”是因为它的操作方式类似于堆叠盘子：盘子只能放在另一个盘子上面或下面。

1.2 特性

• 后进先出（LIFO）原则：最后进入栈的元素将最先被取出。
• 限制性访问：栈中的元素只能在表的一端进行插入和删除操作。

二、C语言中的栈实现

2.1 使用数组实现栈

#include 
#include 
#include 
#define MAX_SIZE 100
typedef struct { int data[MAX_SIZE]; int top;
} Stack;
void initStack(Stack *s) { s->top = -1;
}
bool isFull(Stack *s) { return s->top == MAX_SIZE - 1;
}
bool isEmpty(Stack *s) { return s->top == -1;
}
void push(Stack *s, int value) { if (isFull(s)) { printf("Stack is full.\n"); return; } s->data[++s->top] = value;
}
int pop(Stack *s) { if (isEmpty(s)) { printf("Stack is empty.\n"); return -1; } return s->data[s->top--];
}
int peek(Stack *s) { if (isEmpty(s)) { printf("Stack is empty.\n"); return -1; } return s->data[s->top];
}

2.2 使用链表实现栈

#include 
#include 
#include 
typedef struct Node { int value; struct Node *next;
} Node;
typedef struct { Node *top;
} Stack;
void initStack(Stack *s) { s->top = NULL;
}
bool isFull(Stack *s) { // 链表实现栈时，通常不限制栈的大小 return false;
}
bool isEmpty(Stack *s) { return s->top == NULL;
}
void push(Stack *s, int value) { Node *newNode = (Node *)malloc(sizeof(Node)); newNode->value = value; newNode->next = s->top; s->top = newNode;
}
int pop(Stack *s) { if (isEmpty(s)) { printf("Stack is empty.\n"); return -1; } Node *temp = s->top; int value = temp->value; s->top = s->top->next; free(temp); return value;
}
int peek(Stack *s) { if (isEmpty(s)) { printf("Stack is empty.\n"); return -1; } return s->top->value;
}

三、栈的应用实例

3.1 求逆序

#include 
#include 
#include 
#define MAX_SIZE 100
typedef struct { int data[MAX_SIZE]; int top;
} Stack;
// ...（省略栈的基本操作函数）
void reverseArray(int arr[], int size) { Stack s; initStack(&s); for (int i = 0; i < size; i++) { push(&s, arr[i]); } for (int i = 0; i < size; i++) { arr[i] = pop(&s); }
}
int main() { int arr[] = {1, 2, 3, 4, 5}; int size = sizeof(arr) / sizeof(arr[0]); reverseArray(arr, size); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); return 0;
}

3.2 表达式求值

#include 
#include 
#include 
#include 
#define MAX_SIZE 100
typedef struct { int data[MAX_SIZE]; int top;
} Stack;
// ...（省略栈的基本操作函数）
int precedence(char op) { switch (op) { case '+': case '-': return 1; case '*': case '/': return 2; default: return 0; }
}
int evaluate(int a, int b, char op) { switch (op) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; default: return -1; }
}
int evaluateExpression(char *expression) { Stack values, ops; initStack(&values); initStack(&ops); for (int i = 0; expression[i] != '\0'; i++) { if (expression[i] == ' ') { continue; } else if (expression[i] == '(') { push(&ops, expression[i]); } else if (isdigit(expression[i])) { int value = 0; while (i < strlen(expression) && isdigit(expression[i])) { value = value * 10 + (expression[i] - '0'); i++; } push(&values, value); i--; } else if (expression[i] == ')') { while (!isEmpty(&ops) && ops.data[ops.top] != '(') { int val2 = pop(&values); int val1 = pop(&values); char op = (char)pop(&ops); push(&values, evaluate(val1, val2, op)); } if (!isEmpty(&ops)) { pop(&ops); } } else { while (!isEmpty(&ops) && precedence(ops.data[ops.top]) >= precedence(expression[i])) { int val2 = pop(&values); int val1 = pop(&values); char op = (char)pop(&ops); push(&values, evaluate(val1, val2, op)); } push(&ops, expression[i]); } } while (!isEmpty(&ops)) { int val2 = pop(&values); int val1 = pop(&values); char op = (char)pop(&ops); push(&values, evaluate(val1, val2, op)); } return pop(&values);
}
int main() { char expression[] = "3 + 5 * 6 - 4"; printf("Result: %d\n", evaluateExpression(expression)); return 0;
}

四、总结

通过本文的介绍，相信您已经对C语言栈有了深入的了解。栈作为一种基础且重要的数据结构，在编程中有着广泛的应用。熟练掌握栈的使用，将有助于您在解决各种编程挑战时更加得心应手。在实际编程中，可以根据具体需求选择合适的栈实现方式，并结合其他数据结构，实现更加复杂的算法和程序。