数据结构（三）：栈

墨蓝 2021-09-17 08:54 350阅读 0赞

## 栈概念 ##

*  **栈是仅在表尾（栈顶）进行插入和删除操作的线性表，是后进先出的线性表，简称 LIFO 结构**，不含任何元素的栈称为空栈
 *  栈的插入操作也叫做进栈，栈的删除操作也叫做出栈

![9434708-120af29eb9e44f35.png][]

yQOsp.png

### 栈（stack）的抽象 ###

*  Data（数据元素）：同线性表，元素具有相同的类型，相邻元素具有前驱和后继关系
 *  基本操作

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center">方法</th> 
   <th style="text-align:center">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center">InitStack(*S)</td> 
   <td style="text-align:center">初始化操作，建立一个空栈 S</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">DestoryStack(*S)</td> 
   <td style="text-align:center">销毁一个栈</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">ClearStack(*S)</td> 
   <td style="text-align:center">清空栈</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">StackEmpty(S)</td> 
   <td style="text-align:center">若栈为空，返回true，否则false</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">GetTop(S,*e)</td> 
   <td style="text-align:center">若栈存在且非空，返回 S 的栈顶元素</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">Push(*S,e)</td> 
   <td style="text-align:center">插入新元素 e 到栈 s 中并成为栈顶元素</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">Pop(<em>S,</em>e)</td> 
   <td style="text-align:center">删除栈 s 中的顶元素，返回其值</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">StackLength(S)</td> 
   <td style="text-align:center">返回栈 S 元素个数</td> 
  </tr> 
 </tbody> 
</table>

### 栈的链式存储结构 ###

*  将栈顶放在链表的头部
 *  对于链表来说基本不存在栈满情况，除非没有内存可以使用

### 栈的进栈 push 与出栈 pop ###

*  进出栈操作都很简单，没有任何循环操作，时间复杂度为 O(1)
 *  **顺序栈与链表栈的区别是顺序栈需要确定长度，可能会存在内存空间浪费问题**，但优势是存取定位方便，而链表栈每个元素都有指针域，会增加一点内存开销，但栈长度无限制

## 最先进栈的一定最后出栈？ ##

*  最先进栈的不一定最后出栈，如有3个整形数字元素1、2、3依次进栈，会有以下几个出栈顺序：
    
     *  第一种：1、2、3 进，再 3、2、1 出，出栈顺序为 321
     *  第二种：1进，1出，2进，2出，3进，3出，出栈顺序为 123
     *  第三种：1进、2进，2出，1出，3进，3出，出栈顺序为 213
     *  第四种：1进，1出，2进，3进，3出，2出，出栈顺序为 132
     *  第五种：1进、2进、2出、3进、3出，1出，出栈顺序为 231

[9434708-120af29eb9e44f35.png]: /images/20210811/948d938247c04df7aa2c4404d05b4614.png