#include
010 #include
011 #include
012 #include
/*------------------------------------------------------------
12 // 栈结构的定义
13 ------------------------------------------------------------*/
14 typedef struct Stack
15 {
16 ElemType *base; // 栈基址
17 ElemType *top; // 栈顶
18 int stacksize; // 栈存储空间的尺寸
19 } SqStack;
20
21 /*------------------------------------------------------------
22 // 栈的基本操作
23 ------------------------------------------------------------*/
24
25 bool InitStack(SqStack *S);
26 void DestroyStack(SqStack *S);
27 bool StackEmpty(SqStack S);
28 int StackLength(SqStack S);
29 bool GetTop(SqStack S, ElemType *e);
30 void StackTraverse(SqStack S, void (*fp)(ElemType));
31 bool Push(SqStack *S, ElemType e);
32 bool Pop(SqStack *S, ElemType *e);
33 bool bracketMatch(SqStack *S,const char *arr);
const int STACK_INIT_SIZE = 100; // 初始分配的长度
016 const int STACKINCREMENT = 10; // 分配内存的增量
017
018 /*------------------------------------------------------------
019 操作目的： 初始化栈
020 初始条件： 无
021 操作结果： 构造一个空的栈
022 函数参数：
023 SqStack *S 待初始化的栈
024 返回值：
025 bool 操作是否成功
026 ------------------------------------------------------------*/
027 bool InitStack(SqStack *S)
028 {
029 S->base = (ElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));
030 if(S ->base == NULL)
031 return false;
032 S ->top = S ->base;
033 S->stacksize = STACK_INIT_SIZE;
034 return true;
035 }
036
037 /*------------------------------------------------------------
038 操作目的： 销毁栈
039 初始条件： 栈S已存在
040 操作结果： 销毁栈S
041 函数参数：
042 SqStack *S 待销毁的栈
043 返回值：
044 无
045 ------------------------------------------------------------*/
046 void DestroyStack(SqStack *S)
047 {
048 assert(S != NULL);
049 free(S ->base);
050 S->base = S->top = NULL;
051 }
052
053 /*------------------------------------------------------------
054 操作目的： 判断栈是否为空
055 初始条件： 栈S已存在
056 操作结果： 若S为空栈，则返回true，否则返回false
057 函数参数：
058 SqStack S 待判断的栈
059 返回值：
060 bool 是否为空
061 ------------------------------------------------------------*/
062 bool StackEmpty(SqStack S)
063 {
064 assert((S.base != NULL)&&(S.top != NULL));
065 return (S.base == S.top);
066 }
067
068 /*------------------------------------------------------------
069 操作目的： 得到栈的长度
070 初始条件： 栈S已存在
071 操作结果： 返回S中数据元素的个数
072 函数参数：
073 SqStack S 栈S
074 返回值：
075 int 数据元素的个数
076 ------------------------------------------------------------*/
077 int StackLength(SqStack S)
078 {
079 assert((S.base != NULL)&&(S.top != NULL));
080 return (S.top - S.base);
081 }
082
083 /*------------------------------------------------------------
084 操作目的： 得到栈顶元素
085 初始条件： 栈S已存在
086 操作结果： 用e返回栈顶元素
087 函数参数：
088 SqStack S 栈S
089 ElemType *e 栈顶元素的值
090 返回值：
091 bool 操作是否成功
092 ------------------------------------------------------------*/
093 bool GetTop(SqStack S, ElemType *e)
094 {
095 assert((S.base != NULL) && (S.top != NULL));
096 if(S.top == S.base)
097 exit(0);
098 *e = *(S.top - 1);
099 return true;
100 }
101
102 /*------------------------------------------------------------
103 操作目的： 遍历栈
104 初始条件： 栈S已存在
105 操作结果： 依次对S的每个元素调用函数fp
106 函数参数：
107 SqStack S 栈S
108 void (*fp)() 访问每个数据元素的函数指针
109 返回值：
110 无
111 ------------------------------------------------------------*/
112 void StackTraverse(SqStack S, void (*fp)(ElemType))
113 {
114 assert((S.base != NULL) && (S.top != NULL));
115 while(S.base < S.top)
116 {
117 (*fp)(*S.base);
118 S.base++;
119 }
120 }
121
122 /*------------------------------------------------------------
123 操作目的： 压栈——插入元素e为新的栈顶元素
124 初始条件： 栈S已存在
125 操作结果： 插入数据元素e作为新的栈顶
126 函数参数：
127 SqStack *S 栈S
128 ElemType e 待插入的数据元素
129 返回值：
130 bool 操作是否成功
131 ------------------------------------------------------------*/
132 bool Push(SqStack *S, ElemType e)
133 {
134 if(S == NULL)
135 return false;
136 assert((S->base != NULL) && (S ->top != NULL));
137 if(S ->top - S ->base >= S->stacksize)
138 {
139 S ->base = (ElemType *)realloc(S ->base,(S ->stacksize + STACKINCREMENT) * sizeof(ElemType));
140 if(! S ->base)
141 exit(0);
142 S ->top = S->base + S ->stacksize;
143 S ->stacksize += STACKINCREMENT;
144 }
145 *(S ->top++) = e;
146 return true;
147 }
148
149 /*------------------------------------------------------------
150 操作目的： 弹栈——删除栈顶元素
151 初始条件： 栈S已存在且非空
152 操作结果： 删除S的栈顶元素，并用e返回其值
153 函数参数：
154 SqStack *S 栈S
155 ElemType *e 被删除的数据元素值
156 返回值：
157 bool 操作是否成功
158 ------------------------------------------------------------*/
159 bool Pop(SqStack *S, ElemType *e)
160 {
161 if((* S).top == (*S).base)
162 return false;
163 *e = * --(* S).top;
164 return true;
165 }
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024