栈和队列

栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、在另一端进行删除操作。因而，栈和队列也可以被称为操作受限的线性表

栈

栈stack是一种只允许在一端进行插入和删除操作的线性表，它是一种操作受限的线性表。在表中允许进行插入和删除的一端称为栈顶，另一端称为栈底。栈的插入操作通常称为入栈或进栈而栈的删除操作则称为出栈或退栈当栈中无数据元素时，称为空栈

根据栈的定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素;后进先出

多栈共享邻接空间

G在计算机系统软件中，各种高级语言的编译系统都离不开栈的使用。常常一个程序中要用到多个栈，若采用顺序栈，会因为所需的栈空间大小难以准确估计，导致出现有的栈空间溢出、有的栈空间空闲的情况。为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间，但实际中很难准确地估计。另一方面，若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。紧张。若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使其存储空间互补。这就是栈的共享邻接空间。

应用

1. 算术表达式求值

计值的实现可以通过设置两个栈来完成。
操作数栈OPRD: 用来存放处理表达是过程中的操作数
运算符栈OPTR: 存放处理表达式过程中的运算符，开始时，先在运算符栈栈底压入一个表达式的结束符*#*
计算机系统在处理表达式时，从左到右依次读出表达式中的各个符号（操作数或运算符），每读出一个符号后，根据运算规则做如下的处理。假如是操作数，则将其压入操作数栈，并依次读下一个符号。假如是运算符，则与运算符栈的栈顶运算符进行优先级比较，并做以以下处理

• 假如读出的运算符的优先级高于运算符栈栈顶运算符的优先级，则将其压入运算符栈，并依次读下一个符号
• 假如读出的运算符的优先级等于运算符栈栈顶运算符的优先级，说明左右括号相遇，只需将栈顶运算符退栈即可
• #假如读出的运算符的优先级低于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，从运算符栈中退出一个运算符，然后做相应的运算，并将运算结果压入操作数栈
• 假如读出的是表达式结束符*#，且运算符栈栈顶的运算符也为#*，则表达式处理结束，最后的表达式的计算结果在操作数栈的栈顶位置

表1 表达式3+4*2计算过程栈区变化表

栈与递归过程

栈的一个重要应用是在程序设计语言中实现递归过程。递归即在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调用自己，则称其为“直接递归函数”。如果一个函数经过一系列中间调用语句，通过其他函数间接调用自己，则称其为“间接递函数归”

有很多数学函数是递归定义的，如阶乘函数的定义
$$n! = \begin{cases}1 \qquad n = 0 \\n \times n - 1 \qquad n \neq 0\end{cases}$$

long factint n{    ifn == 0    {        return 1;    } else {        return n * factn -1;    }}

递归算法的设计步骤如下

1. 将规模较大的原问题分解为一个或多个规模更小，但具有类似于原问题特性的子问题，即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题
2. 确定一个或多个无须分解，可直接求解的最小子问题（称为“递归的终止条件”）

递归算法有两个基本的特征：递归归纳和递归终止。首先能将问题转化为比原问题规模小的同类问题，归纳出一般递推公式，故所处理的对象要有规律地递增或递减；当规模小到一定的程度应结束递归调用，逐层返回

队列

它只允许插入在表的一端进行，而删除在表的另一端进行，允许插入的一端叫队尾（rear），而允许删除的一端叫队头（front）。队列的插入操作通常称为“入队”或“进队”，而队列的删除操作则称为“出队”或“退队”;队”。当队列中无数据元素时，称为“空队列”。根据队列的定义可知，队头元素总是最先进队列，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（first in first out FIFO）的原则组织数据的，因此，队列也被称为“先进先出”表

分治法

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并

任何一个可以用计算机求解的问题，其所需的计算时间都与规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少

分治法所能解决的问题一般具有以下几个特征。

• 该问题的规模缩小到一定的程度就可以容易地解决。
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
• 利用该问题分解出的子问题的解可以合并为该问题的解。
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

分治法在每一层递归上都有如下三个步骤

1. 分解：将原问题分解为若干个规模较小、相互独立，且与原问题形式相同的子问题。
2. 解决：若子问题规模较小且容易被解决则直接解，否则递归地解各个子问题。
3. 合并：将各个子问题的解合并为原问题的解。

原文地址