数据结构——栈

栈：仅限在表尾进行插入或删除操作的线性表。表尾段称为栈顶（top），表头端称为栈底（bottom）。 特点：先进先出 栈的存储方式：顺序栈和链栈

一.栈的结构

1.顺序栈

顺序栈：利用一组地址连续的存储单元依次存放元素 一般在初始化设定空栈时不限定栈的最大容量，而是先为栈分配一个基本容量，在应用过程中，当栈的空间不够使在逐段扩大。 顺序栈的结构体定义如下：

typedef struct{ SElemType *base； SElemType *top； int stacksize；//栈的当前可使用的最大容量 }SqStack;

也可定义为如下结构体：

#define MaxSize 100; //栈的初始容量 typrdef struct{ ElemType data[MaxSize]; int top; //栈顶元素的位置 }SqStack;

2.链栈

链栈：以单链表的方式存放元素 链栈的结构体定义如下：

typedef struct node{ ElemType data; struct node *next; }LinkStack;

链栈的操作易于实现，不做讨论。

二.栈的常见应用

1.数制转换

对输入的任意一个非负十进制整数，打印输出与其等值的二进制数。

#include<stdio.h> typedef struct{ int data[100]; int top; }SqStack; SqStack St; int main(){ int N; scanf("%d",&N); St.top = 0; while(N){ St.data[++St.top] = N % 2; N = N / 2; } while(St.top){ printf("%d",St.data[St.top--]); } return 0; }

2.括号匹配检查

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即( [ ] ( ) )或[ ( [ ] [ ]) ]等为正确的格式，[( ] )或( ( ) ] )均为不正确的格式，检验括号是否匹配。

```c #include<stdio.h> typedef struct{ char data[100]; int top; }SqStack; SqStack St; int main(){ char ch; St.top = 0; while((ch = getchar()) != '\n'){ if(ch == '(' || ch == '[') St.data[++St.top] = ch; else if(ch == ')'){ if(St.data[St.top] == '('){ St.top--; } else{ printf("\n输入不合法，请重新输入\n"); St.top = 0; } } else if(ch == ']'){ if(St.data[St.top] == '['){ St.top--; } else{ printf("\n输入不合法，请重新输入\n"); St.top = 0; } } else printf("\n输入不合法，请重新输入\n"); } if(St.top == 0) printf("输入括号匹配\n"); return 0; }

（未完…）