C语言数据结构之栈简单操作
什么是栈？
栈（Stack）是一种线性数据结构，它具有“后进先出”（Last-In-First-Out）的特性。栈顶是栈的一端，另一端称为栈底。每次只能从栈顶插入数据（入栈）或者从栈顶取出数据（出栈）。
栈的简单操作
栈的简单操作包括：
- 初始化栈
- 判断栈是否为空
- 判断栈是否已满
- 入栈操作
- 出栈操作
- 获取栈顶元素
栈的初始化
栈的初始化可以通过动态分配内存的方式来实现。代码如下：
#define MAXSIZE 100
typedef int ElemType;
typedef struct {
ElemType data[MAXSIZE]; // 存放栈数据
int top; // 栈顶指针
} SqStack;
// 初始化栈
void InitStack(SqStack *S) {
S->top = -1; // 栈顶指针初始化为-1，表示栈为空
}
判断栈是否为空
栈是否为空可以通过栈顶指针判断。如果栈顶指针等于-1，表示栈为空，否则栈不为空。代码如下：
// 判断栈是否为空
int IsEmpty(SqStack S) {
if (S.top == -1) {
return 1; // 栈为空
}
return 0; // 栈不为空
}
判断栈是否已满
静态数组实现的栈可以通过数组下标来判断栈是否已满。如果栈顶指针等于MAXSIZE-1，表示栈已满，否则栈未满。代码如下：
// 判断栈是否已满
int IsFull(SqStack S) {
if (S.top == MAXSIZE-1) {
return 1; // 栈已满
}
return 0; // 栈未满
}
入栈操作
入栈操作是将一个元素压入栈顶。入栈操作需要先判断栈是否已满。如果栈未满，将元素插入到栈顶，并将栈顶指针加1。代码如下：
// 入栈操作
int Push(SqStack *S, ElemType x) {
if (IsFull(*S)) {
return 0; // 栈已满，入栈失败
}
S->top++; // 栈顶指针加1
S->data[S->top] = x; // 将元素压入栈顶
return 1; // 入栈成功
}
出栈操作
出栈操作是将栈顶元素弹出。出栈操作需要先判断栈是否为空。如果栈非空，将栈顶元素弹出，并将栈顶指针减1。代码如下：
// 出栈操作
int Pop(SqStack *S, ElemType *x) {
if (IsEmpty(*S)) {
return 0; // 栈为空，出栈失败
}
*x = S->data[S->top]; // 将栈顶元素弹出
S->top--; // 栈顶指针减1
return 1; // 出栈成功
}
获取栈顶元素
获取栈顶元素是返回栈顶元素的值，但不弹出栈顶元素。获取栈顶元素需要先判断栈是否为空。如果栈非空，返回栈顶元素的值。代码如下：
// 获取栈顶元素
int GetTop(SqStack S, ElemType *x) {
if (IsEmpty(S)) {
return 0; // 栈为空，获取栈顶元素失败
}
*x = S.data[S.top]; // 返回栈顶元素的值
return 1; // 获取栈顶元素成功
}
示例说明
示例1：用栈模拟简单计算器
现在有一个简单的计算器，只支持+、-、*、/四则运算，不支持括号，我们需要用栈来模拟它。假设用户输入的表达式存放在一个字符数组exp中，我们可以通过以下步骤来实现：
- 初始化栈S。
- 从左到右遍历exp，依次读取每个字符。
- 如果字符是数字字符，则将其转换为整数，并入栈S。
- 如果字符是操作符，则从栈S中弹出两个操作数，进行计算，将计算结果压入栈S。
- 最后栈顶就是表达式计算结果。
具体实现可以参考以下代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int top;
} SqStack;
void InitStack(SqStack *S) {
S->top = -1;
}
int IsEmpty(SqStack S) {
if (S.top == -1) {
return 1;
}
return 0;
}
int IsFull(SqStack S) {
if (S.top == MAXSIZE-1) {
return 1;
}
return 0;
}
int Push(SqStack *S, int x) {
if (IsFull(*S)) {
return 0;
}
S->top++;
S->data[S->top] = x;
return 1;
}
int Pop(SqStack *S, int *x) {
if (IsEmpty(*S)) {
return 0;
}
*x = S->data[S->top];
S->top--;
return 1;
}
int GetTop(SqStack S, int *x) {
if (IsEmpty(S)) {
return 0;
}
*x = S.data[S.top];
return 1;
}
int main() {
SqStack S;
InitStack(&S);
char exp[MAXSIZE];
printf("请输入表达式：");
fgets(exp, MAXSIZE, stdin);
int len = strlen(exp);
int i, num1, num2, result;
for (i = 0; i < len; i++) {
if (exp[i] >= '0' && exp[i] <= '9') { // 如果是数字字符
int num = exp[i] - '0';
Push(&S, num);
} else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') { // 如果是操作符
Pop(&S, &num2);
Pop(&S, &num1);
switch (exp[i]) { // 根据操作符进行计算
case '+':
result = num1 + num2;
break;
case '-':
result = num1 - num2;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num1 / num2;
break;
}
Push(&S, result);
}
}
GetTop(S, &result);
printf("计算结果：%d\n", result);
return 0;
}
示例2：判断括号是否匹配
现在有一个括号字符串，我们需要用栈来判断其中的括号是否匹配。假设括号字符串存放在一个字符数组str中，我们可以通过以下步骤来实现：
- 初始化栈S。
- 从左到右遍历str，依次读取每个字符。
- 如果字符是左括号，入栈S。
- 如果字符是右括号，从栈S中弹出一个左括号，判断两者是否匹配。
- 遍历完成后，如果栈S非空，则括号不匹配，否则括号匹配。
具体实现可以参考以下代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
typedef struct {
char data[MAXSIZE];
int top;
} SqStack;
void InitStack(SqStack *S) {
S->top = -1;
}
int IsEmpty(SqStack S) {
if (S.top == -1) {
return 1;
}
return 0;
}
int IsFull(SqStack S) {
if (S.top == MAXSIZE-1) {
return 1;
}
return 0;
}
int Push(SqStack *S, char x) {
if (IsFull(*S)) {
return 0;
}
S->top++;
S->data[S->top] = x;
return 1;
}
int Pop(SqStack *S, char *x) {
if (IsEmpty(*S)) {
return 0;
}
*x = S->data[S->top];
S->top--;
return 1;
}
int GetTop(SqStack S, char *x) {
if (IsEmpty(S)) {
return 0;
}
*x = S.data[S.top];
return 1;
}
int main() {
SqStack S;
InitStack(&S);
char str[MAXSIZE];
printf("请输入括号字符串：");
fgets(str, MAXSIZE, stdin);
int len = strlen(str);
int i;
char ch, top;
for (i = 0; i < len-1; i++) {
ch = str[i];
if (ch == '(' || ch == '[' || ch == '{') { // 如果是左括号
Push(&S, ch);
} else if (ch == ')' || ch == ']' || ch == '}') { // 如果是右括号
if (IsEmpty(S)) {
printf("括号不匹配\n");
return 0;
}
Pop(&S, &top);
if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) {
printf("括号不匹配\n");
return 0;
}
}
}
if (!IsEmpty(S)) {
printf("括号不匹配\n");
return 0;
}
printf("括号匹配\n");
return 0;
}
总结
本文主要介绍了栈（Stack）的基本概念和简单操作，包括栈的初始化、判断栈是否为空、判断栈是否已满、入栈操作、出栈操作、获取栈顶元素等。栈是一种非常常用的数据结构，它可以用于解决很多实际问题，例如用栈模拟计算器、用栈判断括号是否匹配等。通过本文的介绍，相信读者已经对栈有了更深入的了解，可以更加灵活地使用栈来解决实际问题。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言数据结构之栈简单操作 - Python技术站
微信扫一扫 
支付宝扫一扫 