栈（Stack）是一种基础的数据结构，遵循后进先出（LIFO，Last In First Out）的原则。它被广泛应用于函数调用、表达式求值、括号匹配等问题中。在这篇技术博客中，我们将详细介绍如何使用C语言实现一个栈，并涵盖基本的操作以及实战应用。
什么是栈？
栈是一种特殊的线性表，只允许在一端进行插入和删除操作。这一端被称为栈顶（Top）。栈的基本操作包括：
Push: 将元素压入栈顶。
Pop: 从栈顶移除元素。
Peek/Top: 查看栈顶元素而不移除。
IsEmpty: 判断栈是否为空。
IsFull: 判断栈是否已满（对于有固定容量的栈）。
栈的实现方法
在C语言中，栈的实现可以分为基于数组和基于链表两种方法。我们将分别介绍这两种实现方式。
1. 基于数组实现栈
基于数组的栈实现通常适用于固定大小的栈。以下是代码示例：
#include
#include
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
// 初始化栈
void initStack(Stack *stack) {
stack->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack *stack) {
return stack->top == -1;
}
// 判断栈是否已满
int isFull(Stack *stack) {
return stack->top == MAX_SIZE - 1;
}
// 压栈操作
void push(Stack *stack, int value) {
if (isFull(stack)) {
printf("Stack overflow! Cannot push %d\n", value);
return;
}
stack->data[++stack->top] = value;
}
// 弹栈操作
int pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack underflow! Cannot pop\n");
return -1;
}
return stack->data[stack->top--];
}
// 查看栈顶元素
int peek(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty! Cannot peek\n");
return -1;
}
return stack->data[stack->top];
}
// 打印栈中元素
void printStack(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return;
}
printf("Stack elements: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->data[i]);
}
printf("\n");
}
int main() {
Stack stack;
initStack(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printStack(&stack);
printf("Popped: %d\n", pop(&stack));
printStack(&stack);
printf("Top element: %d\n", peek(&stack));
return 0;
}
核心特点：
使用数组存储数据。
通过top变量管理栈顶位置。
操作简单但存在固定容量的限制。
2. 基于链表实现栈
链表实现的栈不需要固定大小，动态分配内存，适用于需要灵活容量的场景。
#include
#include
typedef struct Node {
int data;
struct Node *next;
} Node;
// 初始化栈
Node* initStack() {
return NULL;
}
// 判断栈是否为空
int isEmpty(Node *top) {
return top == NULL;
}
// 压栈操作
void push(Node **top, int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed! Cannot push %d\n", value);
return;
}
newNode->data = value;
newNode->next = *top;
*top = newNode;
}
// 弹栈操作
int pop(Node **top) {
if (isEmpty(*top)) {
printf("Stack underflow! Cannot pop\n");
return -1;
}
Node *temp = *top;
int value = temp->data;
*top = temp->next;
free(temp);
return value;
}
// 查看栈顶元素
int peek(Node *top) {
if (isEmpty(top)) {
printf("Stack is empty! Cannot peek\n");
return -1;
}
return top->data;
}
// 打印栈中元素
void printStack(Node *top) {
if (isEmpty(top)) {
printf("Stack is empty!\n");
return;
}
printf("Stack elements: ");
Node *current = top;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
Node *stack = initStack();
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printStack(stack);
printf("Popped: %d\n", pop(&stack));
printStack(stack);
printf("Top element: %d\n", peek(stack));
return 0;
}
核心特点：
动态分配内存，无容量限制。
通过链表节点表示栈元素。
实现更加灵活，但需要注意内存管理。
实战案例：括号匹配问题
栈可以用于解决括号匹配的问题。以下是一个简单的实现：
#include
#include
#include
#define MAX_SIZE 100
typedef struct {
char data[MAX_SIZE];
int top;
} CharStack;
// 初始化字符栈
void initCharStack(CharStack *stack) {
stack->top = -1;
}
// 判断栈是否为空
int isCharStackEmpty(CharStack *stack) {
return stack->top == -1;
}
// 压栈操作
void pushChar(CharStack *stack, char ch) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack overflow! Cannot push %c\n", ch);
return;
}
stack->data[++stack->top] = ch;
}
// 弹栈操作
char popChar(CharStack *stack) {
if (isCharStackEmpty(stack)) {
printf("Stack underflow! Cannot pop\n");
return '\0';
}
return stack->data[stack->top--];
}
// 检查括号匹配
int isBalanced(const char *expr) {
CharStack stack;
initCharStack(&stack);
for (int i = 0; i < strlen(expr); i++) {
char ch = expr[i];
if (ch == '(' || ch == '{' || ch == '[') {
pushChar(&stack, ch);
} else if (ch == ')' || ch == '}' || ch == ']') {
if (isCharStackEmpty(&stack)) {
return 0; // 多余的右括号
}
char top = popChar(&stack);
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '[')) {
return 0; // 括号不匹配
}
}
}
return isCharStackEmpty(&stack);
}
int main() {
const char *expr = "{[()]}";
if (isBalanced(expr)) {
printf("The expression is balanced.\n");
} else {
printf("The expression is not balanced.\n");
}
return 0;
}
总结
通过这篇博客，我们从基础概念到代码实现，深入探讨了如何使用C语言实现栈。无论是数组还是链表方法，各有优缺点。栈的应用范围广泛，是编程中不可或缺的工具。希望这篇文章能帮助您更好地理解和掌握栈的实现与应用！
参考链接
探索C语言中的栈：原理、实现与实战
栈