[科普中国]-扩充栈操作

简介

扩充栈操作是指对栈的基本操作（例如栈顶进行插入或删除操作）进行扩充，使栈能进行一些其他操作。扩充栈操作需要对栈的结构进行修改，并对栈有关操作重新进行定义，例如双端栈就是一种栈的变形，除了有栈一些基本操作以外，还扩充栈操作，使得栈的应用领域更加广泛。

栈亦称堆栈。计算机内存中由程序指定的一个后进先出(LIFO)存储区或CPU内部的一个LIFO寄存器组。前者称软栈，后者称硬栈.软栈的一端是固定的，另一端是浮动的，浮动的一端称为栈顶.所有信息的存入和取出都只能在栈顶进行，而且是在堆栈指示字寄存器的配合下，按LIFO原则工作的。硬栈栈顶一端是固定的，压入的数据项占据栈顶，栈中原有的数据项都依次向栈底方向移动；弹出数据时，最后进栈的数据项先被弹出，下面各级数据项依次向栈顶方向移动。软栈和硬栈功能均相同，主要作为LIFO缓冲存储器，用于中断处理、子程序嵌套及暂存数据。在程序中断时，堆栈(自动)保存程序计数器、状态寄存器及工作寄存器的内容，并在中断结束后把这些现场内容恢复到相应的寄存器中。

缓冲区溢出缓冲区溢出是指当计算机向缓冲区内填充数据位数时超过了缓冲区本身的容量，溢出的数据覆盖在合法数据上。理想的情况是：程序会检查数据长度，而且并不允许输入超过缓冲区长度的字符。但是绝大多数程序都会假设数据长度总是与所分配的储存空间相匹配，这就为缓冲区溢出埋下隐患。操作系统所使用的缓冲区，又被称为“堆栈”，在各个操作进程之间，指令会被临时储存在“堆栈”当中，“堆栈”也会出现缓冲区溢出。

双端栈栈是一种重要的数据结构， 堆栈技术被广泛应用于编译软件和程序设计中。讨论栈的结构特征与操作实现特点，有着重要的意义。在栈的应用中经常会出现需要用到栈的共享技术， 在此共享技术中最常用的是两栈的共享，即双端栈。传统的双端栈总是事先开辟定量存储空间M ，这样造成了在程序运行过程中存储空间的不足或浪费。 一般的做法是停止程序的执行，修改M 的值。若M 太大则会造成存储空间的浪费，不能实现动态扩充的目的，也无法做到对闲置空间的自动回收。 以解决此问题为目的。

传统双端栈的存储结构在传统的双端栈中，两个栈之间存在一种制约关系：两个栈中的元素总数最大可以达到M ， 如果一个栈中的元素较多，那么另一个栈中的元素就较少，两个栈中的元素总和超不过M 。 它主要利用了栈的 “栈底位置不变，而栈顶位置动态变化” 的特性。首先申请一个共享的一维数组空间S[M]，将两个栈的栈底分别设在一维数组的两端，分别是0 和M - 1。由于两个栈顶动态变化，这样可以形成互补，使得每个栈的可用的最大空间达到M 。传统双端栈的存储结构定义如下：

typedef struct

{ ElemType Stack[M];

nt top[2];

}DqStack;

在双端栈的应用中，如果数据元素有进有出，且存储在双端栈中的元素个数始终小于M-2 时，基本操作完全可行。但是在数据元素把存储空间都占满且又有元素需要入栈时，那么上述算法就无法解决了，只能出现 “溢出” ，数据元素入栈不成功。有人会认为可以在定义M 时将其放大到最大程度，但会发现M 越大，造成的空间浪费就越大；也有人会提出在空间不够用时，停止程序的执行 再将M 放大一些，但是在一些大型系统开发中，系统一旦投入运行，就很难停止下来2。

双端栈的动态存储结构针对上面的问题，可以将ElemType 定义为指针类型*Stack，而非数组，这样就不需要对双端栈设置最大存储空间M，而是给双端栈设置初始值STACK_INIT_SIZE，通过动态内存分配函数malloc，给该指针分配存储空间，且附设一个StackSize 来表示该空间的当前大小，若在程序执行中出现栈满的情况，可以通过realloc 函数对该空间进行动态扩充，使其增加STACK_INCREMENT个单元。其新的类型定义如下：

# define STACK_INIT_SIZE 5

# define STACK_INCREMENT 5

# define STACK_FREESIZE 10

# define PERCENT 0.5

typedef struct

{ ElemType *Stack;

int top[2];

int StackSize;

}DqStack;

应用回溯回溯法（backtracking）是暴力搜寻法中的一种。对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。在经典的教科书中，八皇后问题展示了回溯法的用例。（八皇后问题是在标准国际象棋棋盘中寻找八个皇后的所有分布，使得没有一个皇后能攻击到另外一个。）回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：找到一个可能存在的正确的答案；在尝试了所有可能的分步方法后宣告该问题没有答案。在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

最长回文串匹配在计算机科学中，最长回文子串或最长对称因子问题是在一个字符串中查找一个最长连续子串，这个子串必须是回文。例如“banana”最长回文子串是“anana”。最长回文子串并不能保证是唯一的，例如，在字符串“abracadabra”，没有超过三的回文子串，但是有两个回文字串长度都是三，是“ada”和“aca”。在一些应用中需要返回全部的最长回文子串(所有字串都是回文，并且不能扩展为更大的回文子串)而不是返回其中之一或是最大的回文子串的长度。