数据结构笔记：栈

• 栈的抽象数据类型

  ADT 栈（stack）
  Data
  operation
      InitStack(*S): 初始化操作，建立一个空栈S
      DestroyStack(*S): 若栈存在，则销毁它
      ClearStack(*S): 将栈清空
      StackEmpty(S): 若栈为空，返回true，否则返回false
      GetTop(S, *e): 若栈存在且非空，用e返回S的栈顶元素
      Push(*S, e): 若栈S存在，插入新元素e到栈S中并成为栈顶元素
      Pop(*S, e): 删除栈S中栈顶元素，并用e返回其值
      StackLength(S): 返回栈S的元素个数
  endADT

• 栈的顺序存储结构

  • 栈的结构

    1 typedef int SElemType; // SElemType类型根据实际情况而定，这里假设为int
    2 typedef struct {
    3     SElemType data[MAXSIZE];
    4     int top; // 用于栈顶指针
    5 } SqStack;

  • 进栈

    1 // 插入元素e为新的栈顶元素
    2 Status Push(SqStack *S, SElemType) { // 栈满
    3     if (S->top == MAXSIZE - 1)
    4         return ERROR;
    5     s->top++; // 栈顶指针增加一
    6     s->data[S->top] = e; // 将新插入元素赋值给栈顶空间
    7     return OK;
    8 }

  • 出栈

    1 // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR
    2 Status Pop(SqStack *S, SElemType *e) {
    3     if (S->top == -1)
    4         return ERROR;
    5     *e = S->data[S->top]; // 将要删除的栈顶元素赋值给e
    6     s->top--; // 栈顶指针减一
    7     return OK;
    8 }

• 两栈共享空间

  • 两栈共享空间结构

    1 typedef struct {
    2     SElemType data[MAXSIZE];
    3     int top1; // 栈1栈顶指针
    4     int top2; // 栈2栈顶指针
    5 } SqDoubleStack;

  • 进栈

     1 // 插入元素e为新的栈顶元素
     2 Status Push(SqDoubleStack *S, SElemType e, int stack Number) {
     3     if (S->top1+1 == S->top2) // 栈已满，不能再push新元素了
     4         return ERROR;
     5     if (stackNumber == 1) // 栈1有元素进栈
     6         S->data[++S->top1] = e; // 若栈1则先top1+1后给数组元素赋值
     7     else if (stackNumber == 2) // 栈2有元素进栈
     8         S->data[--S->top2] = e; // 若栈2则先top2-1后给数组元素赋值
     9     return OK;
    10 }

  • 出栈

     1 // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
     2 Status Pop(SqDouble *S, SElemType *e, int stackNumber) {
     3     if (stackNumber == 1) {
     4         if (S->top1 == -1)
     5             return ERROR; // 说明栈1已经是空栈，溢出
     6         *e = S->data[S->top1--]; // 将栈1的栈顶元素出栈
     7     }
     8     else if (stackNumber == 2) {
     9         if (S->top2 == MAXSIZE)
    10             return ERROR; // 说明栈2已经是空栈，溢出
    11         *e = S->data[S->top2++]; // 将栈2的栈顶元素出栈
    12     }
    13     return OK;
    14 }

• 栈的链式存储结构

  • 链栈的结构

    1 typedef struct StackNode {
    2     SElemType data;
    3     struct StackNode *next;
    4 } StackNode, *LinkStackPtr;
    5 
    6 typedef struct LinkStack {
    7     LinkStackPtr top;
    8     int count;
    9 } LinkStack;

  • 进栈

    1 // 插入元素e为新的栈顶元素
    2 Status Push(LinkStack *S, SElemType e) {
    3     LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    4     s->data = e;
    5     s->next = S->top; // 把当前的栈顶元素赋值给新结点的直接后继
    6     S->top = s; // 将新的结点s赋值给栈顶指针
    7     S->count++;
    8     return OK;
    9 }

  • 出栈

     1 // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
     2 Status Pop(LinkStack *S, SElemType *e) {
     3     LinkStackPtr p;
     4     if (StackEmpty(*S))
     5         return ERROR;
     6     *e = S->top->data;
     7     p = S->top; // 将栈顶结点赋值给p
     8     S->top = S->top->next; // 栈顶指针下移一位，指向后一结点
     9     free(p); // 释放结点p
    10     S->count--;
    11     return OK;
    12 }