数据结构与算法-栈与队列

谁借莪１个温暖的怀抱￠ 2022-03-21 02:56 291阅读 0赞

### 概要 ###

*   *   *  栈和队列都是特殊的线性表
         *  栈
         *   *  基本概念
             *  栈的应用-递归
             *  栈的应用-四则运算表达式求值【后缀（逆波兰）表示法】
         *  队列
         *   *  基本概念

### 栈和队列都是特殊的线性表 ###

>   [何为线性表?][Link 1]

### 栈 ###

#### 基本概念 ####

>   栈（stack）是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。  
>   栈的插入操作，叫做进栈，也称压栈、入栈。栈的删除操作，叫做出栈，也称弹栈。  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70][]

#### 栈的应用-递归 ####

*  递归的定义

>   在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数。  
>   每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

*  递归和迭代的区别

>   迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数副本、会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。

*  栈在递归实现中的应用体现

>   简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。  
>   当然，对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切都有系统代劳了。

#### 栈的应用-四则运算表达式求值【后缀（逆波兰）表示法】 ####

*  中缀表达式和后缀表达式定义

>   以【9 + (3 - 1) x 3 + 10 ÷ 2】为例，这是标准的四则运算表达式，因为所有的运算符号都在两数字的中间，所以叫做**中缀表达式**。而对于【9 3 1 - 3 \* + 10 2 / +】这样的表达式，因为所有的符号都是在要运算数字的后面出现，所以叫做**后缀表达式**。

*  逆波兰表示法步骤1：中缀表达式转后缀表达式

>   中缀表达式【9+(3-1)x3+10÷2】转化为后缀表达式【9 3 1 - 3 \* + 10 2 / +】  
>   规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
> 
> > 1.  初始化一空栈，用来对符号进出栈使用。
> > 2.  第一个字符是数字9，输出9，后面是符号“+”，进栈。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 1][]
> 
> > 1.  第三个字符是“(”，依然是符号，因其只是左括号，还未配对，故进栈。
> > 2.  第四个字符是数字3，输出，总表达式为【9 3】，接着是“-”，进栈，第五个字符是数字1，输出，总表达式为【9 3 1】。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 2][]
> 
> > 1.  第六个符号是“)”，此时，我们需要去匹配此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”，因此输出“-”。总的输出表达式为【9 3 1 -】。
> > 2.  接着是数字3，输出，总的表达式为【9 3 1 - 3】。紧接着是符号“x”，因为此时栈顶符号为“+”号，优先级低于“x”，因此不输出，“\*”进栈。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 3][]
> 
> > 1.  之后是符号“+”，此时当前栈顶元素“x”比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈），总的输出表达式为【9 3 1 - 3 \* +】。然后将当前这个符号“+”进栈。
> > 2.  紧接着数字10，输出，总的表达式变为【9 3 1 - 3 \* + 10】。后是符号“÷”，所以“/”进栈。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 4][]
> 
> > 1.  最后一个数字2，输出，总的表达式为【9 3 1 - 3 \* + 10 2】。
> > 2.  因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为【9 3 1 - 3 \* + 10 2 / +】。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 5][]

*  逆波兰表示法步骤2：将后缀表达式进行运算得出结果

>   后缀表达式【9 3 1 - 3 \* + 10 2 / +】  
>   规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
> 
> > 1.  初始化一个空栈。此栈用来对要运算的数字进出使用。
> > 2.  后缀表达式中前三个都是数字，所以9、3、1进栈。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 6][]
> 
> > 1.  接下来是“-”，所以讲栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈。
> > 2.  接着是数字3进栈。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 7][]
> 
> > 1.  后面是“\*”，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈。
> > 2.  下面是“+”，所以栈中6和9出栈，9与6相加，得到15，将15进栈。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 8][]
> 
> > 1.  接着是10与2两数字进栈。
> > 2.  接下来是符号“/”，因此栈顶的2与10出栈，10与2相除，得到5，将5进栈。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 9][]
> 
> > 1.  最后一个符号“+”,所以15与5出栈并相加，得到20，将20进栈。
> > 2.  结果是20出栈，栈变为空。  
> >     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 10][]

### 队列 ###

#### 基本概念 ####

>   队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为对头。  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 11][]

[Link 1]: https://blog.csdn.net/FTD_SL/article/details/86679825
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70]: /images/20220321/6833056346bc405884803f2b95b5c1c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 1]: /images/20220321/266921b4b90e4664892cd97d40aa38ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 2]: /images/20220321/f213bfe8c3924fb09e2a1a337b4821f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 3]: /images/20220321/63bb12a7ec354654a46807e482e5be19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 4]: /images/20220321/d184cdc4270d4fd1ae87a0cc5c888cd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 5]: /images/20220321/0dbe9ef38f884ad89c17610c4bc00a1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 6]: /images/20220321/d956099a7c9d4d4987973a65c0ace309.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 7]: /images/20220321/38d228cf558546dcb417515be87a8b34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 8]: /images/20220321/5a3ffc06a7c74994ac9ba92a1e201308.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 9]: /images/20220321/fdf9b3b958a543068dfd178e918b8e27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 10]: /images/20220321/fba7fe8031cd4f22b045cada9b7b895e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 11]: /images/20220321/27ffce1735b2426788580d04089c182d.png