数据结构中的栈和队列和串20.7.2

栈

栈的定义

栈是只能在表的一端进行插入、删除的线性表。栈中允许插入、删除的一端称为栈顶相反，栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素不含任何数据元素的栈称为空栈。栈的特点为后进先出(Last In First Out，LIFO)。下图为一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映栈的当前位置。

栈的基本操作

栈的基本操作主要有以下六种。

1. InitStack(&S):初始化操作，构造一个空栈S.
2. StackEmpty(S):若栈S为空栈，返回1，否则返回0.
3. Push(&S,e):插入元素e为新的栈顶元素。
4. Pop(&S,&e):删除S的栈顶元素，并用e返回其值。
5. GetTop(S,&e):用e返回S的栈顶元素。
6. ClearStack(&S):将S清为空栈。

栈的存储结构

栈的顺序存储用向量作为栈的存储结构，向量S表示栈，m表示栈的大小，用指针top指向栈顶位置，S[top]表示栈顶元素，当在栈中进行插入、删除操作时，都要移动栈指针；而当top=m-1时，则栈满，当top=-1时，表示栈空。同时为了避免浪费空间可以采用双栈机制，即向量的两端为栈底。

栈的链式存储结构

栈的链式存储也叫链栈，我们把插入和删除均在链表表头进行的链表称为链栈。链栈也分有头节点和无头节点两种。带头节点的链根操作比较方便。

栈的应用

栈具有广泛的应用，例如，求表达式的值及递归到非递归等。
例如,表达式求值
计算机在处理算术表达式时，可将表达式先转换为后缀形式，然后利用栈进行计算。例如，表达式46+5*(120-37)的后缀表达式形式为46 5 120 37-*+(当然啦你要先知道这个是怎么来的)，计算后缀表达式时，从左至右扫描表达式：若遇到运算对象，则压入栈中；遇到运算符，则从栈顶弹出运算对象进行计算，并将运算结果压入栈中。

重复以上过程，直到后缀表达式结束。例如，后缀表达式46512037-*+

1. 依次将46，5，120，37压入栈中。
2. 遇到-，弹出37和120，计算120-37，得83，将其压入栈中。
3. 遇到*，弹出83和5，计算5*83，得415，将其压入栈中。
4. 遇到+，弹出415和46，计算46+415，得461，将其压入栈中。
5. 表达式结束，计算完成，栈顶为计算结果。

要注意的是遵循先乘除后加减然后把运算符放到数字后面

队列

队列的定义

队列(queue)是一种只允许在一端进行插入，而在另一端进行删除的线性表，是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾(rear)，只允许进行删除的一端称为队头(ront)。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。

由队列的定义可知，队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（First In First Out，FIFO）的原则组织数据的，因此，队列也被称为“先进先出”表。

队列的基本操作

队列的基本操作主要有以下六种。

1. InitQueue(&Q):初始化操作，构造一个队列Q.
2. QueueEmpty(Q)：若栈Q为空队列，则返回1，否则返回0.
3. EQueue(&Q,e):插入元素e到队列Q的尾.
4. OQueue(&Q，&e):删除Q的队首元素，并用e返回其值。
5. GetQhead(Q,&e):用e返回Q的队首元素。
6. ClearQueue(&Q):将Q清空为空队。

队列的顺序存储结构

顺序存储结构采用一维数组（向量）实现，设队列头指针front和队列尾指针rear，并且假设front指向队头元素的前一位置，rear指向队尾元素。若不考虑队满，则入队操作语句为Q[rear++]=x；若不考虑队空，则出队操作语句为x=Q[++front]。当然，出队时，并不一定需要队头元素（与退栈类似)。

按上述的做法，有可能出现假溢出，即队尾已到达一维数组的高端，不能再入队，但因为连续出队，队列中元素个数并未达到最大值。解决这种问题，可用循环队列。在循环队列中，需要区分队空和队满：仍用front=rear表示队列空，在牺牲一个单元的前下，用front==(rear+1)%MAX表示队列满。在这种约定下，入队操作的语句为：rear=(rear+1)%MAX,MAX,Q[rear]=x;出队操作语句为：front=(front+1)%MAX。

队列的链式存储结构

队列的链接实现称为链队，链队实际上是一个同时带有头指针和尾指针的单链表。头指针指向队头节点，尾指针指向队尾节点即单链表的最后一个节点。为了简便，链队设计成一个带头节点的单链表。

循环队列中的边界条件判别准则

判别循环队列的“空”或“满”不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一个布尔变量来区别队列的空和满；二是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满；三是设置一个计数器
记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

双端队列的作用

双端队列是限定插入和删除操作在线性表的两端进行，可将其看成是栈底连在一起的两个栈，但其与两个栈共享存储空间是不同的。共享存储空间中的两个栈的栈顶指针是向两端扩展的，因而每个栈只需一个指针；而双端队列允许两端进行插入和删除元素，因而每个端点必须设立两个指针，如下图所示

串

字符串(string)是一串文字及符号的简称，是一种线性表。字符串中的元素是字符，计算机中非数值问题处理的对象经常是字符串，如在汇编和高级语言的编译程序中，源程序和目标程序都是字符串；在事务处理程序中，姓名、地址等一般也是作为字符串处理的。

串的定义及基本运算

串是仅由字符构成的有限序列，是取值受限的线性表。一般记为S=a1a2…a，其中S是申名，单引号括起来的字符序列是串值。

基本术语

• 串长：即串的长度，指字符串中的字符个数、
• 空串：长度为0的串，空串不包含任何字符。
• 空格串：由一个或多个空格组成的串。虽然空格是一个空白符，但它也是一个字符，计算串长度时要将其计算在内。
• 子串：由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串的位置。空串是任意串的子串。
• 串相等：指两个串长度相等且对应序号的字符也相同。
• 串比较：两个串比较大小时以字符的ASCIl码值作为依据。比较操作从两个串的第一个字符开始进行，字符的ASCI码值大者所在的串为大；若其中一个串结束，则以较长的串为大。

串的基本操作

①赋值操作StrAssign(s,t):将串t的值赋给串s。
②连接操作Concat（s.t)：将串t接续在串s的尾部，形成一个新串。
③求串长StrLength(s):返回串s的长度。
④串比较StrCompare(st):比较两个串的大小，返回值-1、0和1分别表示sct、st和s>t三种情况。
⑥求子串SubString(s,start.len):返回串s中从stat开始的、长度为en的字符序列。

串的存储结构

串可以采用顺序存储或链式存储。

1. 串的顺序存储。单的顺序存储是指用一组地址连续的存储单元来存储串值的字行序列。由于串中的元素为字符，所以可通过程序语言提供的字符数组定义串的存储空间，也可以根据串长的需要动态申请字符串的空间。
2. 串的链式存储。字符串也可以采用链表作为存储结构，当用链表存储串中的字符时，需要考虑存储密度问题，每个结点中可以存储一个字符，也可以存储多个字符。用结点大小为4的链表表示字符串"abcdefghij",如下图所示。
   
   在链式存储结构中，结点大小的选择和顺序存储方法中数组空间大小的选择一样重要，它直接影响串运算的效率。

CET4P223

• mature
• weekly
• grind
• riot
• reality
• fee
• risk
• relationship
• column
• curiosity
• provided
• lamb
• harmony
• reality