该系列属于计算机基础系列中的《数据结构基础》子系列，参考书《数据结构考研复习指导》(王道论坛 组编)，完整内容请阅读原书。

1.栈

1.1 栈的基本概念

1. 栈的定义

   • 栈(Stack)({\rm Stack})(Stack)：只允许在一端进行插入或删除操作的线性表；

   • 栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作；

   • 栈结构图解如下：

     

   • 栈顶(Top)({\rm Top})(Top)：线性表允许进行插入和删除操作的一端；

   • 栈底(Bottom)({\rm Bottom})(Bottom)：固定，不允许进行插入和删除操作的一端；

   • 空栈：不含任何元素的空表；

   • 假设某个栈S=(a1,a2,a3,a4,a5)S=(a_1,a_2,a_3,a_4,a_5)S=(a1​,a2​,a3​,a4​,a5​)，如上图的栈结构，根据栈顶栈底定义，可知，a1a_1a1​为栈底元素，a5a_5a5​为栈顶元素；进栈次序依次为：a1,a2,a3,a4,a5a_1,a_2,a_3,a_4,a_5a1​,a2​,a3​,a4​,a5​，出栈次序依次为：a5,a4,a3,a2,a1a_5,a_4,a_3,a_2,a_1a5​,a4​,a3​,a2​,a1​；

   • 栈的操作特性概括为：后进先出(LastInFirstOut，LIFO)({\rm Last\ In\ First\ Out，LIFO})(Last In First Out，LIFO)；

   • 栈的数学性质：nnn个不同元素进栈，出栈元素不同排列的个数为：1n+1C2nn\displaystyle\frac{1}{n+1}C_{2n}^nn+11​C2nn​，称为卡特兰(Catalan)({\rm Catalan})(Catalan)数；

2. 栈的基本操作

   • InitStack(&S){\rm InitStack(\&S)}InitStack(&S)：初始化一个空栈SSS；
   • StackEmpty(S){\rm StackEmpty(S)}StackEmpty(S)：判断一个栈是否为空，若栈SSS为空，则返回true{\rm true}true，否则返回false{\rm false}false；
   • Push(&S,x){\rm Push(\&S,x)}Push(&S,x)：进栈，若栈SSS未满，则将x{\rm x}x加入使之成为新栈顶；
   • Pop(&S,&x){\rm Pop(\&S,\&x)}Pop(&S,&x)：出栈，若栈SSS非空，则弹出栈顶元素，并用x{\rm x}x返回；
   • GetTop(S,&x){\rm GetTop(S,\&x)}GetTop(S,&x)：读栈顶元素，若栈SSS非空，则用x{\rm x}x返回栈顶元素；
   • DestroyStack(&S){\rm DestroyStack(\&S)}DestroyStack(&S)：销毁栈，并释放栈SSS占用的存储空间；

1.2 栈的顺序存储结构

1.2.1 顺序栈的实现

• 采用顺序存储的栈称为顺序栈，其利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)({\rm top})(top)指示当前栈顶元素的位置；

• 栈的顺序存储类型描述：

  #define MaxSize 50				// 定义栈中元素的最大个数
  typedef struct{Elemtype data [MaxSize];	// 存放栈中元素int top;					// 栈顶指针
  }SqStack;
  

• 栈顶指针：S.top{\rm S.top}S.top，初始时设置S.top=−1{\rm S.top=-1}S.top=−1；栈顶元素：S.data[S.top]{\rm S.data[S.top]}S.data[S.top]；

• 进栈操作：栈不满时，栈顶指针先加111，再送值到栈顶元素；

• 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减111；

• 栈空条件：S.top==−1{\rm S.top==-1}S.top==−1；栈满条件：S.top==MaxSize−1{\rm S.top==MaxSize-1}S.top==MaxSize−1；栈长：S.top+1{\rm S.top+1}S.top+1；

1.2.2 顺序栈的基本运算

• 栈顶指针和栈中元素间的关系图解如下：

  

  • 上述图解相关说明：图(a){\rm (a)}(a)为空栈，图(b){\rm (b)}(b)只有111个栈元素，图(c){\rm (c)}(c)是A、B、C、D、E{\rm A、B、C、D、E}A、B、C、D、E依次进栈的结果，图(d){\rm (d)}(d)是E、D、C{\rm E、D、C}E、D、C元素相继出栈，此时栈顶指针移至元素B{\rm B}B；

• 顺序栈常用的基本运算

  • 初始化：

    void InitStack(SqStack &S){S.top=-1;		// 初始化栈顶指针
    }
    

  • 判栈空：

    bool StackEmpty(SqStack S){if(S.top==-1)return true;		// 栈空返回trueelsereturn false;		// 栈非空返回false
    }
    

  • 进栈操作：

    bool Push(SqStack &S,ElemType x){if(S.top==MaxSize-1)return false;		// 栈满，报错S.data[++S.top]=x;		// 栈顶指针先加1，再入栈return true;
    }
    

  • 出栈操作：

    bool Pop(SqStack &S,ElemType &x){if(S.top==-1)return false;		// 栈空，报错x=S.data[S.top--];		// 先出栈，栈顶指针再减1return true;
    }
    

  • 读栈顶元素：

    // 此操作仅是读取栈顶元素，但没有出栈
    bool GetTop(SqStack S,ElemType &x){if(S.top==-1)return false;		// 栈空，报错x=S.data[S.top];		// x记录栈顶元素return true;
    }
    

1.2.3 共享栈

• 利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间中间延伸；

• 共享栈的结构图解：

  

• 两个顺序栈的栈顶指针均指向栈顶元素，top0=−1{\rm top0=-1}top0=−1时，000号栈为空；top1=MaxSize{\rm top1=MaxSize}top1=MaxSize时，111号栈为空；当两个栈顶指针相邻，即top1−top0=1{\rm top1-top0=1}top1−top0=1时，判断为栈满；

• 当000号栈进栈时，top0{\rm top0}top0先加111再赋值，111号栈进栈时，top1{\rm top1}top1先减111再赋值；出栈操作则相反；

• 共享栈目的：为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被栈满时才会发生上溢，其存取数据的时间复杂度均为O(1)O(1)O(1)；

1.3 栈的链式存储结构

• 采用链式存储的栈称为链栈；

• 链栈的优点：便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况；

• 链栈通常采用单链表实现，并规定所有操作都在单链表的表头进行；

• 链栈存储结构图解如下(此处规定链栈没有头结点，Lhead{\rm Lhead}Lhead指向栈顶元素)：

  

• 栈的链式存储类型描述：

  typedef struct Linknode{ElemType data;				// 数据域struct Linknode *next;		// 指针域
  }*LinkStack;					// 栈类型定义