Stack Structures

栈（LIFO结构）

1. 定义：仅在表尾（栈顶top）插入&删除的后进先出==线性表==

   1. 特点：线性表（栈元素具有线性关系，即前驱后继关系）、有栈顶top和栈底bottom、空栈
   2. 入（压）栈、出（弹）栈
   3. 进出栈变化形式：有位置限制，无时间限制
   4. 栈抽象数据类型（Stack）：类似线性表（P78~P79）

2. 顺序栈

   1. 空栈：top = -1；【数组元素从0开始】

   2. top：栈顶指针

   3. StackSize：栈长度

   4. top < StackSize

   5. 栈结构定义

      1 2 3 4 5 6

      typedef int SElemType; typedef struct { SElemType data[MAXSIZE]; //存放数据的数组 int top; //初始化栈顶指针，一般为 int top=-1； }SqStack;

   6. 进栈操作Push

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

      /* 1. 判断栈满 2. top++ 3. 数据赋值 */ Status Push(SqStack *S,SElemType e) { if(S->top == MAXSIZE -1) { return ERROR; //1 } S->top++; //2 S->data[S->top]=e; //3 return OK; }

   7. 出栈操作Pop

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

      /* 1. 判断栈空 2. 取出栈顶元素e 3. 栈顶top-- */ Status Pop(SqStack *S,SElemType *e) { if(S->top == -1) { return ERROR; //1 } *e=S->data[S->top]; //2 S->top--; //3 return OK; }

   8. 共享栈（==管道对接==）【节约空间】

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

      /* 共享栈空间结构定义： */ typedef struct { SElemType data[MAXSIZE]; int top1,top2; }SqDoubleStack; /* 入栈Push： ++top1 --top2 1. 判断栈满：top1 + 1==top2 2. 记录元素stackNumber判断 top1++ 或 top2-- 3. 元素赋值 S->data[ ++S->top1 || --S->top2 ]=e； */ Status Push(SqDoubleStack *S,SElemType e,int stackNumber) { if(S->top1+1 == S->top2) { return ERROR; } if(StackNumber == 1) { S->data[++S->top1] = e; } else if(stackNumber==2) { S->data[--S->top2] = e; } return OK; } /* (栈顶元素)出栈Pop： top1-- top2++ 1.记录元素stackNumber判断top1或top2 2.异常判断栈空： top1 == -1 top2 == MAXSIZE 3.取出栈顶元素*e=S->data[S->top1-- || S->top2++] */ Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber) { if(stackNumber == 1) { if(S->top1==-1) { ERROR; //栈1空，异常 }*e=S->data[S->top1--]; } else if(stackNumber ==2) { if(S->top2==MAXSIZE) { ERROR; //栈2空，异常 }*e=S->data[S->top2++]; } return OK; }

   9. 堆栈溢出：缺乏栈满判断，持续入栈，超出MAXSIZE

3. 链栈

   1. 特点：链栈不需要头结点（头指针和栈顶指针合二为一），由内存提供动态空间，不存在溢出问题，只存在系统崩溃死机问题

   2. 链栈结构定义

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

      /* 定义数据结点，由data+next组成 定义top指针，计数元素count 空链栈：top == NULL 时 */ typedef struct StackNode { SElemType data; //数据域 struct StackNode *next; //后继 }StackNode,*LinkStackPtr; typedef struct { LinkStackPtr top; int count; }LinkStack;

   3. 链栈进栈操作：动态生成结点s，赋值元素e，s->next指向当前top指针指向的结点；top指向新结点s作为新栈顶；计数++

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

      /* 1. 动态申请内存空间生成链栈结点 2. 数据域赋值 3. next指向当前栈顶指针top指向的结点 4. 成为新栈顶 5. 链栈count++ */ Status Push(LinkStack *S,SElemType e) { LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); //动态生成结点 s->data=e; s->next=S->top; S->top=s; S->count++; return OK; }

   4. 链栈出栈操作：取出栈顶结点给变量p，指针下移，释放p

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

      /* 1.生成指针变量p 2.异常判断，栈S是否存在 3.取出栈顶top的数据域data 4.p指向top结点 5.top的下移一位作为新top结点 6.释放p指向的结点原top 7.计数count-- */ Status Pop(LinkStack *S,SElemType *e) { LinkStackPtr p; //1 if(StackEmpty(*S)) { return ERROR; //2 } *e=S->top->data; //3 p=S->top; //4 S->top=S->top->next; //5 free(p); //6 S->count--; //7 return OK; }

4. 栈的应用

   1. 递归
      1. 定义：把自己当函数调用（递归：选择结构；迭代：循环结构）（弊端：频繁调用函数，占内存）
      2. (递归)栈操作：递归调用阶段 –> 压/入栈；递归回退阶段 –> 弹/出栈
      3. 实例：斐波那契数列（P86~88）
   2. 四则运算表达式求值（中缀+后缀）
      1. 括号成对出现，（遇左括号）左括号进栈，（遇右括号）将左括号出栈
      2. 中缀表达式转后缀：栈用来进出运算的==符号==
      3. 后缀表达式进行计算：栈用来进出运算的==数字==