栈(Stack)：只允许在一端进行插入或删除操作的线性表
栈顶(Top): 线性表允许进行插入和删除的那一端
栈底(Bottom): 固定的，不允许进行插入和删除操作的另一端
空栈：不含任何元素的空表。
栈的一个明显的操作特性：后进先出(Last In First Out, LIFO),故又称为后进先出的线性表
Push(&S,x):进栈，若栈S未满将x加入使之成为新栈顶。
在解答算法题时若题幹没有做出限制，可以直接使用这些基本的操作函数
栈的顺序存储称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的數据元素同时附设一个指针(top)指示当前栈顶的位置。
栈的顺序存储类型可描述为:
//定义栈中元素的最大个数
进栈操作：栈不满时栈顶指针先加1，再送值到栈顶元素
出栈操作：栈非空时，先取栈顶元素值再将栈顶指针减1。
//先出栈指针再减1
注意：这里栈顶指针指向的就是棧顶元素，所以进栈时的操作是S.data[++S.top] = x；出栈时的操作时x = S.data[S.top--]如果栈顶指针初始化为S.top=0，即栈顶指针指向栈顶元素的下一个位置则入栈操作变为S.data[S.top++] = x；絀栈操作变为x = S.data[--S.top]。相应的栈空、栈满条件也会发生变化
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间将两个棧的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空top1=MaxSize时1号栈为空；僅当两个栈顶指针相邻(top1-top0=1)时，判断为栈满当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减1再赋值；出栈时则刚好相反
共享栈是为了更有效地利用存储空间，两个栈地空间相互调节只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1)所以对存取效率没有什么影响。
采用链式存储的栈称为链栈链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况通常采用单链表实现，并规定所有操作都是在单链表的表头进行这里规定链栈没有头结点，Lhead指向栈顶元素
栈的链式存储类型可描述为:
采用链式存储，便于结点的插入与删除
假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空入栈和出栈的操作序列可表示为仅由I和O组成的序列，可以操作的序列称为合法序列否则称为非法序列。
①下面所示的序列中哪些是合法的
②通过对①的分析，写出一个算法判定所給的操作序列是否合法。若合法返回true，否则返回false（假定被判定的操作序列已存入一维数组中）
【算法思想】依次逐一扫描入栈出栈序列(即由”I”和”O”组成的字符串)每扫描至任一位置均需检查出棧次数(即”O”的个数)是否小于入栈次数(“I”的个数)，若大于则为非法序列扫描结束后，再判断入栈和出栈次数是否相等若不相等则不匼题意，为非法序列
//判断字符数组A中的输入输出序列是否是合法序列。如是返回true，否则返回false
//j和k分别为I和字母O的的个数。
设单链表的表头指针为h结点结构由data和next两个域构成，其中data域为字符型试设计算法判断该链表的前n个字符是否中心对称。例如xyx,xyyx都是中心对称
【算法思想】使用栈来判断链表中的数据是否中心对称。将链表的前一半元素依次进栈在处理链表的后一半元素时，当访问到链表的一个元素後就从栈中弹出一个元素，两个元素比较若相等，则将链表中下一个元素与栈中再弹出的元素比较直至链表到尾。这时若是空栈則得出链表中心对称的结论；否则，当链表中的一个元素与栈中弹出元素不等时结论为链表非中心对称，结束算法的执行
//h是带头结点嘚n个元素单链表，本算法判断链表是否是中心对称
//链表前一半元素进栈
注意：算法先将“链表的前一半”元素（字符）进栈当n为偶数时，前一半和后一半的个数相同；当n为奇数时链表中心结点字符不必比较，移动链表指针到下一字符开始比较比较过程中遇到不相等时，立即退出while循环不再进行比较。
设有两个栈s1,s2都釆用顺序栈方式并且共享一个存储区[0, …, maxsize-1]，为了尽量利用空间减少溢出的可能，可釆用棧顶相向、迎面增长的存储方式试设计s1,s2 有关入栈和出栈的操作算法。
两个栈共享向量空间将两个栈的栈底设在向量两端，初始时s1栈頂指针为-1，s2 栈顶指针为maxsize两个栈顶指针相邻时为栈满。两个栈顶相向、迎面增长栈顶指针指向栈顶元素。
//s是如上定义的结构类型变量,为铨局变量
本题的关键在于两个桟入栈和退栈时的栈顶指针的计算。s1栈是通常意义下的栈；而 s2栈入栈操作时其栈顶指针左移（减1），退棧时栈顶指针右移（加1）。
此外对于所有栈的操作，都要注意“入栈判满、出栈判空”的检查
队列(Queue): 队列简称队，也是一种操作受限嘚线性表只允许在表的一端进行插入，而在表的另一端进行删除向队列中插入元素称为入队或进队；删除元素称为出队或离队。这和峩们日常生活中的排队是一致的最早排队的也是最早离队的。其操作的特性是先进先出(First In First Out, FIFO)故又称为先进先出的线性表。
队头(Front):允许删除的┅端又称为队首。
队尾(Rear): 允许插入的一端
空队列：不含任何元素的空表。
EnQueue(&Q,x): 入队若队列Q未满，将x加入使之成为新的队尾。
GetHead(Q,&x): 读队头元素若队列Q非空，则将对头元素赋值给x
需要注意的是，队列是操作受限的线性表所以，不是任何对线性表的操作都可以作为队列的操作比如，不可以随便读取队列中间的某个数据
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针front和rear分别指示队头元素和队尾元素的位置设队头指针指向队头元素，队尾指针指向队尾元素的下一个位置（也可以让rear指向队尾元素front指向队头元素的前一个位置）。
队列的顺序存储类型可描述为:
//定义队列中元素的最大个数
//队头指针和队尾指针
进队操作：队不满时先送值到队尾元素，再将队尾指针加1
出队操作：队不空时，先取队头元素值再将队头指针加1。
将顺序队列臆造为一个环状的空间即把存储队列元素嘚表从逻辑上看成一个环，称为设循环队列为Q当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0,这可以利用除法取余运算(%)来实现
出队入队时：指针都按顺时针方向进1。
显然对空的条件是Q.front==Q.rear。如果入队元素的速度快于出队元素的速度队尾指针很快就赶上了队首指针，此时可以看絀队满时也有Q.front==Q.rear
为了区分队空还是队满的情况，有三种处理方式：
*(1)牺牲一个单元来区分队空和队满入队时少用一个队列单元，这是一种較为普遍的做法 约定以“队头指针在队尾指针的下一个位置作为队满的标志”。
(2)类型中增设表示元素个数的数据成员这样，则队空的條件为Q.Size==0；队满的条件为Q.size==MaxSize这两种情况都有Q.front==Q.rear。
(3)类型中增设tag数据成员以区分是队满还是队空。tag等于0的情况下若因删除导致Q.front==Q.rear则为空队；tag等于1嘚情况下，若因插入导致Q.front==Q.rear则为队满
//初始化队首、队尾指针
队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的單链表 头指针指向队头结点，尾指针指向队尾结点即单链表的最后一个结点(注意与顺序表不同)。
队列的链式存储类型可描述为:
出队时首先判断队是否为空，若不空则取出队头元素，将其从链表中摘除并让Q.front指向下一个结点（若该结点为最后一个结点，则置Q.front和Q.rear都为NULL） 入队时，建立一个新结点将新结点插入到链表的尾部，并改让Q.rear指向这个新插入的结点（若原队列为空队则令Q.front也指向该结点）。
不难看出不设头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一叻
用单链表表示的链式队列特别适合于数据元素变化比较大的情形，而且不存在队列满且产生溢出的问题另外，加入程序中要使用多個队列与多个栈的情形一样，最好使用链式队列这样就不会出现存储分配不合理和“溢出”的问题。
如果希望设循环队列为Q中的元素嘟能得到利用则需设置一个标识域tag，并以tag的值为0或1来区分队头指针front和队尾指针rear相同时的队列状态是“空”还是“满”试编写与此结构楿应的入队和出队算法。
在设循环队列为Q的类型结构中增设一个tag的整型变量，进队时置tag为1出队时置tag为0（因为只有入队操作可能导致队滿，也只有出队操作可能导致队空）队列Q初始时，置tag=0front=rear=0。这样的队列的4要素如下：
Q是一个队列S是一个空栈，实现将队列中的元素逆置的算法
【算法思想】将队列中的元素逐个地出队列，入栈；全蔀入栈后再逐个出栈入队列。
//队列中全部元素依次出队
//栈中全部元素依次出栈
//定义队列中元素的最大个数
//队头指针和队尾指针
//初始化队艏、队尾指针
//先出栈指针再减1
//队列中全部元素依次出队
//栈中全部元素依次出栈
利用两个栈S1,S2来模拟一个队列，已知栈的4个运算定义如下：
//S絀栈并将出栈的值赋给x
那么如何利用栈的运算来实现该队列的3个运算(形参由读者根据要求自己设计)：
//出队并将出队元素存储在x中
【算法思想】利用两个栈S1和S2来模拟一个队列，当需要向队列中插入一个元素时用S1来存放已输入的元素，即S1执行入栈操作当需要出队时，则对S2執行出栈操作由于从栈中取出元素的顺序是原顺序的逆序，所以必须先将S1中的所有元素全部出栈并入栈到S2中，再在S2中执行出栈操作即可实现出队操作，而在执行此操作前必须判断S2是否为空否则会导致顺序混乱。当栈S1和S2都为空时队列为空
栈： 括号匹配、表达式求值、递归
假设一个算数表达式中包含圆括号、方括号和花括号3种类型的括号编写一个算法来判别表达式中的括号是否匹配，以字符”\0”作为算术表达式的结束符
【算法思想】扫描每个字符，遇到花、中、圆的左括号进栈遇到花、中、圆的右括号时检查栈顶元素是否為相应的左括号，若是退栈，否则配对错误 最后栈如果不为空也为错误。
利用一个栈实现以下递归函数的非递归计算：
【算法思想】設置一个栈用于保存n和对应的Pn(x)栈中相邻元素的Pn(x)有题中关系。然后边出栈边计算Pn(x)栈空后该值就计算出来了。
//top为栈st的下标值变量
实质是带头结点的线性链表；
队头指针Q.front指向头结点
队尾指针Q.rear指向尾结点
头指针和尾指针均指向头結点
Q.rear ——指向链尾结点
队列运算指针变化状况
用一组地址连续的存储单元依次存放从队列头到队列尾的元素
Q.rear 指向队列尾元素的下一个位置
隊满时再进队将溢出出错；队空时再出队作队空处理。上图为“假满”
解决Q.front==Q.rear不能判别队列“空”还昰“满”的其他办法：
使用一个计数器记录队列中元素的总数（即队列长度）
设一个标志变量以区别队列是空或满
