数据结构中栈的C语言实现

### 数据结构中栈的C语言实现 #### 一、引言 栈是一种常见的线性数据结构，具有后进先出（LIFO, Last In First Out）的特点。在计算机科学领域，栈的应用非常广泛，比如函数调用时的局部变量存储、括号匹配问题等。本文将详细介绍如何使用C语言来实现一个动态的栈，并通过一个简单的括号匹配问题来演示栈的基本操作。 #### 二、栈的基本概念与特点 1. **定义**：栈是一种只允许在一端进行插入和删除操作的数据结构，这端称为栈顶（top），另一端称为栈底（bottom）。 2. **操作**： - 入栈（Push）：在栈顶添加一个元素。 - 出栈（Pop）：移除栈顶的元素。 - 获取栈顶元素（GetTop）：返回栈顶的元素但不移除。 3. **特性**： - 后进先出（LIFO）原则：最后进入栈的元素最先被移除。 - 栈可能会溢出（超出分配的空间）或为空。 #### 三、栈的C语言实现 1. **栈的结构体定义**： ```c typedef struct { SElemType *base; // 栈底指针 SElemType *top; // 栈顶指针 int stacksize; // 当前栈的容量大小 } SqStack; ``` - `SElemType`是栈元素的类型，这里定义为字符类型。 - `base`指向栈底，`top`指向栈顶下一个位置。 - `stacksize`表示当前栈的大小。 2. **初始化栈**： ```c Status InitStack(SqStack &s) { s.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (!s.base) exit(OVERFLOW); s.top = s.base; s.stacksize = STACK_INIT_SIZE; return OK; } ``` - 初始化栈时，首先分配初始大小的内存空间，然后设置栈顶指针为栈底指针位置。 3. **获取栈顶元素**： ```c SElemType GetTop(SqStack s) { if (s.top == s.base) return ERROR; SElemType e = *(s.top - 1); return OK; } ``` - 如果栈为空，则返回错误标识；否则返回栈顶元素。 4. **入栈操作**： ```c Status Push(SqStack &s, SElemType e) { if (s.top - s.base >= s.stacksize) { // 栈满，增加容量 s.base = (SElemType *)realloc(s.base, (s.stacksize + STACK_INCREMENT) * sizeof(SElemType)); if (!s.base) exit(OVERFLOW); s.top = s.base + s.stacksize; s.stacksize += STACK_INCREMENT; } *s.top++ = e; return OK; } ``` - 当栈满时，会自动扩大容量。 5. **出栈操作**： ```c Status Pop(SqStack &s, SElemType &e) { if (s.top == s.base) return ERROR; e = *--s.top; return OK; } ``` - 如果栈为空，则返回错误标识；否则移除栈顶元素并返回其值。 #### 四、应用实例：括号匹配问题 1. **算法思路**： - 遍历输入字符串，遇到左括号就入栈； - 遇到右括号则检查栈顶是否为对应的左括号，如果是则出栈，否则表示括号不匹配； - 遍历结束后检查栈是否为空，如果为空则表示所有括号都正确匹配。 2. **代码实现**： ```c int main() { printf("请输入一个包含括号的字符串:\n"); SqStack s; InitStack(s); // 初始化栈 char c = getchar(); while (c != '\n') { if (c == '(' || c == '[' || c == '{') Push(s, c); else if ((c == ')' && GetTop(s) == '(') || (c == ']' && GetTop(s) == '[') || (c == '}' && GetTop(s) == '{')) Pop(s, e); else if ((c == ')' && GetTop(s) != '(') || (c == ']' && GetTop(s) != '[') || (c == '}' && GetTop(s) != '{')) { printf("括号不匹配！\n"); return ERROR; } c = getchar(); } if (GetTop(s) != 0) { printf("括号不匹配！\n"); } else { printf("括号匹配！\n"); } return 0; } ``` - 这段代码首先提示用户输入包含括号的字符串，然后逐个字符处理，最后根据栈的状态判断括号是否匹配。 #### 五、总结 本文详细介绍了如何使用C语言实现栈数据结构，并通过一个具体的括号匹配问题来演示栈的操作。栈作为一种基本且重要的数据结构，在许多算法设计和程序实现中都有广泛的应用。通过本文的学习，读者可以更好地理解和掌握栈的原理及其实现方法。