后进先出 (LIFO)
ADT Stack { //对象:由数据类型为StackData的元素构成 int Push (stack *S, StackData x); //进栈 int Pop (stack *S, StackData &x); //出栈 int GetTop (stack *S, StackData &x); //取栈顶 void InitStack (stack *S); //置空栈 int StackEmpty (stack *S); //判栈空否 int StackFull (stack *S); //判栈满否 }
栈的应用举例 栈在表达式计算过程中的应用 ：建立操作数栈和运算符栈。运算符有优先级。规则： 自左至右扫描表达式，凡是遇到操作数一律进操作数栈。 当遇到运算符时，如果它的优先级比运算符栈栈顶元素的优先级高就进栈。反之，取出栈顶运算符和操作数栈栈顶的连续两个操作数进行运算，并将结果存入操作数栈，然后继续比较该运算符与栈顶运算符的优先级。 左括号一律进运算符栈，右括号一律不进运算符栈，取出运算符栈顶运算符和操作数栈顶的两个操作数进行运算，并将结果压入操作数栈，直到取出左括号为止。
栈的链接表示—链式栈
1.链式栈无栈满问题，空间可扩充 2.插入与删除仅在栈顶处执行 3.链式栈的栈顶在链头 4.适合于多栈操作
下面是关于栈的一些操作
#include "LinkStack.h" #include <stdlib.h> LinkStack *Create_Stack() { LinkStack* s = (LinkStack*)malloc(sizeof(LinkStack)/sizeof(char)); if (s == NULL) { errno = MALLOC_ERROR; return NULL; } // 置空栈 s->top = NULL; return s; } int StackEmpty (LinkStack *s) { if (s == NULL) { errno = ERROR; return FALSE; } return s->top == NULL; } int Push (LinkStack *s, StackData x) { if (s == NULL) { errno = ERROR; return FALSE; } // 新建结点 Node* node = (Node*)malloc(sizeof(Node)/sizeof(char)); if (node == NULL) { errno = MALLOC_ERROR; return FALSE; } node->data = x; node->next = s->top; s->top = node; return TRUE; } int Pop (LinkStack *s, StackData *x) { if (s == NULL) { errno = ERROR; return FALSE; } if (StackEmpty(s)) { errno = EMPTY_STACK; return FALSE; } Node *p = s->top; *x = p->data; s->top = p->next; free(p); return TRUE; } int GetTop (LinkStack *s, StackData *x) { if (s == NULL) { errno = ERROR; return FALSE; } if (StackEmpty(s)) { errno = EMPTY_STACK; return FALSE; } *x = s->top->data; return TRUE; } // 销毁栈 int Destroy(LinkStack *s) { if (s == NULL) { errno = ERROR; return FALSE; } int x; while(StackEmpty(s) != TRUE) { Pop (s, &x); } free(s); return TRUE; }
