c-数据结构第3章栈和队列

第3章栈和队列《数据结构(C#语言描述)》配套PPT2引入《数据结构(C#语言描述)》配套PPT栈和队列是软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其不同之处在于，栈和队列的相关操作具有特殊性，它们只是线性表相关操作的一个子集。更准确地说，一般线性表上的插入、删除操作不受限制，而栈和队列上的插入、删除操作均受某种特殊限制。因此，栈和队列也称作操作受限的线性表。

33.1栈（stack）《数据结构(C#语言描述)》配套PPT3.1.1栈的概念及操作特征1栈是线性表的一个特例栈只能对线性表的固定一端进行插入和删除操作栈数据的主要特点是“后进先出”（LastInFirstOut，LIFO）或“先进后出”（FirstInLastOut，FILO）的43.1栈（stack）《数据结构(C#语言描述)》配套PPT3.1.1栈的概念及操作栈顶（Top）是栈中允许进行数据插入和删除的那一端。栈底（Bottom）是栈中无法进行数据操作的那一端。栈上溢（Full）：在栈内空间已存满数据时，如果仍然希望能做压栈动作，就会产生“上溢出”。栈下溢（Empty）：在栈内空间已无数据时，如果仍然希望能做出栈动作，就会产生“下溢出”。基本概念2栈顶压栈an．．．a3a2a1出栈栈底53.1栈（stack）《数据结构(C#语言描述)》配套PPT3.1.1栈的概念及操作基本操作3进栈或入栈（Push）栈顶栈底ABCPush(A)Push(B)Push(C)63.1栈（stack）《数据结构(C#语言描述)》配套PPT3.1.1栈的概念及操作基本操作3弹出或出栈（Pop）栈顶栈底ABCPop()Pop()Pop()73.1栈（stack）《数据结构(C#语言描述)》配套PPT3.1.2System.Collections.Stack例3-1Stack.cs83.1栈（stack）《数据结构(C#语言描述)》配套PPT3.1.3栈的应用栈可广泛用于解决表达式求值、进制转换、括号匹配、迷宫、递归调用等满足“先进后出”原则的问题，这里仅介绍如何用栈解决进制转换问题。【例3-1Demo3-1.cs】进制转换93.2队列（Queue）《数据结构(C#语言描述)》配套PPT3.2.1队列的概念及操作队列的定义1队列（Queue）是只允许在一端进行插入，在另一端进行删除的线性表。它所有的插入均限定在表的一端进行，该端称为队尾，所有的删除则限定在表的另一端进行，该端则称为队头。

入队出队a1a2…an队头队尾103.2队列（Queue）《数据结构(C#语言描述)》配套PPT3.2.1队列的概念及操作队头（Head）是队列中允许数据删除的那一端。队尾（Tail）是队列中允许数据插入的那一端。队上溢（Full）：在队内空间存满数据时，如果仍然希望做入队动作，就会产生“上溢出”，这是一种空间不足的出错状态。队下溢（Empty）：在队内空间已无数据时，如果仍然希望做出队动作，就会产生“下溢出”，这是一种数据不足的出错状态。基本概念2入队出队a1a2…an队头队尾113.2队列（Queue）《数据结构(C#语言描述)》配套PPT3.2.1队列的概念及操作基本操作3入队（Enqueue）队头队尾ABCEnqueue(A)Enqueue(B)Enqueue(C)123.2队列（Queue）《数据结构(C#语言描述)》配套PPT3.2.1队列的概念及操作基本操作3出队（Dequeue）队头队尾ABCDequeue()133.2队列（Queue）《数据结构(C#语言描述)》配套PPT3.2.2循环队列由于数组在删除元素时，需要花费大量时间移动大量元素，因此基于数组的队列在队头数据执行出队操作时，速度较慢，很少有实际应用，所以多采用循环队列方式。为了避免大量的数据移动，通常将一维数组中的各个元素看成是一个首尾相接的封闭的圆环，即第一个元素是最后一个元素的下一个元素，这种形式的顺序队列称为循环队列

运行虚拟循环队列演示程序143.2队列（Queue）《数据结构(C#语言描述)》配套PPT3.2.3System.Collections.Queue153.3本章小结《数据结构(C#语言描述)》配套PPT栈和队列的基本操作都是单个元素的“进”、“出”操作，栈的操作是进栈和出栈，队列的操作是进队和出队。所不同的是栈是一种“先进后出”的数据结构而队列是一种“先进先出”的数据结构。C#中实现了栈的集合类是Stack和Stack<T>两种，实现了队列的集合类是Queue和Queue<T>两种。16顺序表及其特点顺序表及其特点顺序表是指线性表的存储结构是连续的，用一块地址连续的空间依次存储线性表中的数据元素。顺序表的特点是访问速度快由于线性表中每个元素所占用的空间是相同的，只需按照公式计算便可以快速地访问指定元素。假设顺序表中第一个元素的位置是Loc，每个数据元素所占用的存储空间为n：a1a2．．．ai．．．线性存储空间下标位置01i-1存储地址LocLoc+nLoc+(i–1)*n17数组数组是最基本的线性表，在System命名空间中。C#中的数组一维数组多维数组参数数组锯齿状数组数组的缺点是不能动态改变集合的大小18动态数组ArrayList数组的集合大小可以改变，属于System.Collections命名空间。ArrayList的Capacity属性值是数组元素的数量，初始值是16，，如果不够则加倍。ArrayList用Object存储对象19ArrayList类中的成员Add():AddsanelementtotheArrayList.AddRange():AddstheelementsofacollectiontotheendoftheArrayList.Capacity:StoresthenumberofelementstheArrayListcanhold.Clear():RemovesallelementsfromtheArrayList.Contains():DeterminesifaspecifieditemisintheArrayList.CopyTo():CopiestheArrayListorasegmentofittoanarray.Count:ReturnsthenumberofelementscurrentlyintheArrayList.GetEnumerator():ReturnsanenumeratortoiterateovertheArrayList.GetRange():ReturnsasubsetoftheArrayListasanArrayList.20IndexOf():Returnstheindexofthefirstoccurrenceofthespecifieditem.Insert():InsertanelementintotheArrayListataspecifiedindex.InsertRange():InsertstheelementsofacollectionintotheArrayListstartingatthespecifiedindex.Item():Getsorsetsanelementatthespecifiedindex.Remove():Removesthefirstoccurrenceofthespecifieditem.RemoveAt():Removesanelementatthespecifiedindex.Reverse():ReversestheorderoftheelementsintheArrayList.Sort():Alphabetic