第3章 栈与队列

第3章栈与队列BasicSortingAlgorithms2引言栈和队列是软件设计中常用的两种数据结构;它们的逻辑结构和线性表相同。其不同之处在于，栈和队列的相关操作具有特殊性，它们只是线性表相关操作的一个子集。一般线性表上的插入、删除操作不受限制，而栈和队列上的插入、删除操作均受某种特殊限制。因此，栈和队列也称作操作受限的线性表。3栈（stack）栈的概念栈是线性表的一个特例栈只能对线性表的固定一端进行插入和删除操作栈数据的主要特点是“后进先出”（LastInFirstOut，LIFO）或“先进后出”（FirstInLastOut，FILO）的4栈（stack）栈的基本概念栈顶（Top）是栈中允许进行数据插入和删除的那一端。栈底（Bottom）是栈中无法进行数据操作的那一端。栈上溢（Full）：在栈内空间已存满数据时，如果仍然希望能做压栈动作，就会产生“上溢出”。栈下溢（Empty）：在栈内空间已无数据时，如果仍然希望能做出栈动作，就会产生“下溢出”。栈顶压栈an．．．a3a2a1出栈栈底5栈（stack）栈的操作——进栈或入栈（Push）栈顶栈底ABCPush(A)Push(B)Push(C)6栈（stack）栈的操作——弹出或出栈（Pop）栈顶栈底ABCPop()Pop()Pop()7栈（stack）其它操作取数（peek）清除（clear）计数（count）Stack类的模拟实现（教材中的CStack）读代码，回答问题p_index变量的作用？CStack.Count是如何实现的？CStack的应用——判定是否是“回文”在字符串中截取字符的两种实现方法：substring和数组8栈（stack）C#中的Stack类System.Collections.StackStack构造器方法StackmyStack=newStack();Stack<string>myStack=newStack<string>();string[]names=newstring[]{"Raymond","David","Mike"};StacknameStack=newStack(names);StackmyStack=newStack(25);主要操作Push（）Pop（）Peek（）Clear（）CopyTo（array，n）ToArray（）9实例简单运算（P52-53）——问题？十进制转换（P55）修改程序可以进行“十→二，十→八，十→十六”三种进制转换staticvoidMulBase(intn,intb){StackDigits=newStack();intremainder;do{remainder=n%b;if(remainder<=9)Digits.Push(remainder);elseDigits.Push((char)(remainder+55));//A的ASC码是65n/=b;}while(n!=0);while(Digits.Count>0)Console.Write(Digits.Pop());Console.Read();}10队列（Queue）队列的定义队列（Queue）是只允许在一端进行插入，在另一端进行删除的线性表。它所有的插入均限定在表的一端进行，该端称为队尾，所有的删除则限定在表的另一端进行，该端则称为队头。入队出队a1a2…an队头队尾11基本概念队头（Head）是队列中允许数据删除的那一端。队尾（Tail）是队列中允许数据插入的那一端。队上溢（Full）：在队内空间存满数据时，如果仍然希望做入队动作，就会产生“上溢出”，这是一种空间不足的出错状态。队下溢（Empty）：在队内空间已无数据时，如果仍然希望做出队动作，就会产生“下溢出”，这是一种数据不足的出错状态。入队出队a1a2…an队头队尾12基本操作入队（Enqueue）队头队尾ABCEnqueue(A)Enqueue(B)Enqueue(C)13基本操作出队（Dequeue）队头队尾ABCDequeue()14Queue类的实现（教材中的CQueue）读代码publicclassCQueue{privateArrayListpqueue;publicCQueue(){pqueue=newArrayList();}publicvoidEnQueue(objectitem){pqueue.Add(item);}publicvoidDeQueue(){pqueue.RemoveAt(0);}publicobjectPeek(){returnpqueue[0];}publicvoidClearQueue(){pqueue.Clear();}publicintCount(){returnpqueue.Count;}}15System.Collections.Queue的应用实例化Queue<int>numbers=newQueue<int>();QueuemyQueue=newQueue(32,3);QueuemyQueue=newQueue(100);默认初始容量是32。初始容量和增长倍数可以设定队列的应用舞池管理用队列排序数据_基数排序优先队列基数排序，也叫桶排序第一步：根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中。将这些桶子中的数值重新串接起来，形成新的数列。第二步：再进行一次分配，这次是根据十位数来分配。接下来将这些桶子中的数值重新串接起来举例：9446851592353122进桶、出桶重排16基数排序算法实现数据结构10个队列构成的数组Queue[]que用于存放数据的整数数组int[]n取数取个位数n[x]%10取十位数n[x]/1017进桶18staticvoidRSort(Queue[]que,int[]n,DigitTypedigit){intsnum;for(intx=0;x<=n.GetUpperBound(0);x++){if(digit==DigitType.ones)snum=n[x]%10;elsesnum=n[x]/10;que[snum].Enqueue(n[x]);}}19出桶staticvoidBuildArray(Queue[]que,int[]n){inty=0;for(intx=0;x>=9;x++)while(que[x].Count>0){n[y]=Int32.Parse(que[x].Dequeue().ToString());y++;}}基数排序算法改进教材中的程序仅能对两位数进行基数排序，如何改进程序可以能多位整数进行基数排序教材中程序使用队列，不用队列这种数据结构可以吗？202122优先队列优先级高的数据项先出队列基本思想首先将队列项写入一个数组；然后遍历数组找到最高优先级的数据项；最后用这个标记过的数组重建队列，被标记的项目被留下不用。23补充内容——正则表达式正则表达式是指一个用来描述或者匹配一系列符合某个句法规则的字符串的单个字符串。在很多文本编辑器或其他工具里，正则表达式通常被用来检索或替换那些符合某个模式的文本内容。C#中的正则表达式包含在.NET基础类库的一个名称空间下，这个名称空间就是System.Text.RegularExpressions。该名称空间包括8个类，1个枚举，1个委托。Regex：编译后的表达式的实例。24Regex类中还包含一些静态的方法：Escape:对字符串中的regex中的转义符进行转义；IsMatch:如果表达式在字符串中匹配，该方法返回一个布尔值；Match:返回Match的实例；Matches:返回一系列的Match的方法Replace:用替换字符串替换匹配的表达式Unescape:不对字符串中的转义字符转义。

25元字符描述$匹配行结束符。例如正则表达式weasel$能够匹配字符串“He‘saweasel”的末尾，但是不能匹配字符串"Theyareabunchofweasels."^匹配一行的开始。例如正则表达式^Whenin能够匹配字符串"Wheninthecourseofhumanevents"的开始，但是不能匹配"WhatandWheninthe"*匹配0或多个正好在它之前的那个字符。例如正则表达式.*意味着能够匹配任意数量的任何字符。\这是引用符，用来将这里列出的这些元字符当作普通的字符来进行匹配。例如正则表达式\$被用来匹配美元符号，而不是行尾，类似的，正则表达式\.用来匹配点字符，而不是任何字符的通配符。\<\>匹配词（word）的开始（\<）和结束（\>）。例如正则表达式\<the\>能够匹配字符串"forthewise"中的"the"，但是不能匹配字符串"otherwise"中的"the"。注意：这个元字符不是所有的软件都支持的。\(\)将\(和\)之间的表达式定义为“组”（group），并且将匹配这个表达式的字符保存到一个临时区域（一个正则表达式中最多可以保存9个），它们可以用\1到\9的符号来引用。|将两个匹配条件进行逻辑“或”（Or）运算。例如正则表达式(him|her)匹配"itbelongstohim"和"itbelongstoher"，但是不能匹配"itbelongstothem."。注意：这个元字符不是所有的软件都支持的。+匹配1或多个正好在它之前的那个字符。例如正则表达式9+匹配9、99、999等。注意：这个元字符不是所有的软件都支持的。?匹配0或1个正好在它之前的那个字符。注意：这个元字符不是所有的软件都支持的。\{i\}

\{i,j\}匹配指定数目的字符，这些字符是在它之前的表达式定义的。例如正则表达式A[0-9]\{3\}能够匹配字符"A"后面跟着正好3个数字字符的串，例如A123、A348等，但是不匹配A1234。而正则表达式[0-9]\{4,6\}匹配连续的任意4个、5个或者