下载文档原格式
stack的知识点1. 栈的定义和特点栈（Stack）是一种具有特殊限制的线性数据结构，它的特点是“后进先出”（Last In First Out，LIFO）。
栈在计算机科学中有着广泛的应用，是一种非常重要的数据结构。
2. 栈的基本操作栈的基本操作包括入栈（push）和出栈（pop）两个操作。
•入栈操作：将元素添加到栈的顶部，使其成为新的栈顶元素。
•出栈操作：移除栈顶的元素，并返回被移除的元素。
除了入栈和出栈操作外，栈还支持其他操作，如获取栈顶元素（top）、判断栈是否为空（empty）、获取栈的大小（size）等。
3. 栈的实现方式栈可以使用数组或链表来实现。
•数组实现：使用数组来存储栈中的元素，通过一个指针来指示栈顶元素的位置。
入栈操作将元素添加到数组的末尾，出栈操作将指针向前移动一位。
•链表实现：使用链表来存储栈中的元素，每个节点包含一个数据元素和一个指向下一个节点的指针。
入栈操作将新元素插入链表的头部，出栈操作将头节点移除。
4. 栈的应用场景栈在计算机科学中有许多应用场景，以下是一些常见的应用场景。
•函数调用栈：在函数调用时，参数、局部变量和返回地址等信息会被压入栈中，函数返回时再从栈中弹出这些信息。
•表达式求值：栈可以用于解析和计算数学表达式，如中缀表达式的转换和后缀表达式的计算。
•括号匹配：栈可以用于检查表达式中的括号是否匹配，如圆括号、方括号和花括号等。
•浏览器的前进和后退功能：浏览器使用栈来记录用户访问的网页历史，通过栈的出栈和入栈操作实现前进和后退功能。
5. 栈的复杂度分析栈的入栈和出栈操作都只涉及到栈顶元素，所以这两个操作的时间复杂度都是O(1)。
而获取栈顶元素、判断栈是否为空和获取栈的大小等操作也都可以在O(1)时间内完成。
6. 总结栈是一种非常重要的数据结构，具有广泛的应用场景。
它的特点是“后进先出”，支持入栈和出栈等基本操作。
栈可以使用数组或链表来实现，常见的应用场景包括函数调用栈、表达式求值、括号匹配和浏览器的前进后退功能等。
1.第四篇数据结构2.早期的程序设计主要偏重于数值计算领域，采用的数据结构相对简单。
例如FORTRan语言仅定义了数组（包括多维数组）和复数两种结构型数据，这两种数据类型足以应付当时多数的科学计算问题。
但是随着现代科技的发展，计算机逐渐应用于数据处理和非数值计算问题，从客观事物中抽象出的数据日益显现出多样化的特征，简单的数据类型已远远不能满足需要，各数据元素之间的复杂联系已经不是普通的数学方程式所能表达的了。
在这种背景下，一种专门研究数据之间结构关系的学科—数据结构便应运而生。
数据结构专门研究各种数据的表示、数据的类型以及它们之间关系的集合，其研究范围主要包括各种数据结构的性质，即它们的逻辑结构、物理结构以及施于其上的操作。
数据结构的类型种类繁多，可以从不同的角度来划分：3.⑴如果从数据元素的值在使用时具有不可分割的性质或者是它可以由更基本的成份组成这个角度来划分，数据结构可以分成简单类型和构造类型两大类；4.⑵如果从数据所占据的内存空间在程序执行期间是否发生变化这个角度来划分，数据结构又可以分成静态结构和动态结构两大类；5.⑶如果从数据结点后继关系的多少和是否具有层次性的角度划分，数据结构还可以分成线性结构和非线性结构两大类。
通常高级程序设计语言都提供了各种简单类型、静态构造类型和动态构造类型的数据结构。
例如PASCAL就提供了１２种类型的定义。
这１２种类型中除了文件和指针属于动态结构的构造类型外，其余１０种均属于简单类型和静态构造类型。
在上表的数据结构中，像数组、栈、串和队列等数据结构属于线性数据结构，而树和图属于非线性数据结构。
线性数据结构易于表示各结点之间的联系，其存储方式相对简单；非线性数据结构往往能比较形象地反映各结点之间的层次关系。
无论是线性结构或非线性结构，若采用数组方式存储，则属于静态数据类型；若采用指针类型存储，则属于动态数据类型。
考虑到篇幅限制和读者具备了PASCAL语言的基础，我们侧重讲解线性结构和非线性结构两种。
顺序栈的基本运算顺序栈是一种经典的数据结构，它是基于数组实现的一种数据结构，具有先进后出（LIFO）的特点。
顺序栈在计算机科学和软件开发中有广泛的应用，是我们学习数据结构和算法的重要基础。
顺序栈的基本运算主要包括入栈、出栈、判空和获取栈顶元素。
下面我们将逐一介绍这些运算。
1. 入栈：入栈即向顺序栈中添加一个元素。
入栈操作需要把元素放入数组中的下一个空闲位置，并更新栈顶指针。
当数组已满时，无法进行入栈操作，这种情况称为栈溢出。
2. 出栈：出栈即从顺序栈中移除栈顶元素。
出栈操作实际上是将栈顶指针减一，并返回栈顶元素的值。
当栈为空时，无法进行出栈操作，这种情况称为栈下溢。
3. 判空：判空操作是判断顺序栈中是否没有任何元素。
可以通过检查栈顶指针是否为-1来判断栈是否为空。
4. 获取栈顶元素：获取栈顶元素是通过返回栈顶指针指向的元素来实现的。
获取栈顶元素不会改变栈的状态。
以上就是顺序栈的基本运算，通过这些运算，我们可以方便地进行栈的操作。
顺序栈的使用可以帮助我们解决许多实际问题。
顺序栈在实际中有许多应用。
例如，我们可以使用顺序栈来实现浏览器的前进和后退功能。
每次访问一个新的网页时，我们可以将当前网页的信息入栈；当点击后退按钮时，我们可以出栈以获取上一个访问过的网页信息。
另一个例子是编辑器中的撤销操作，我们可以使用顺序栈来存储每次操作的历史记录，当需要进行撤销操作时，可以通过出栈操作来获取前一个状态。
在编程中使用顺序栈时，我们要注意栈溢出和栈下溢的情况。
为了避免栈溢出，我们应该在进行入栈操作之前判断栈是否已满；为了避免栈下溢，我们应该在进行出栈操作之前判断栈是否为空。
总结而言，顺序栈是一种简单而有效的数据结构，可以帮助我们解决许多实际问题。
通过掌握顺序栈的基本运算，我们可以更好地理解数据结构和算法的原理，为软件开发和问题解决提供有力支持。
数据结构--栈和队列基础知识⼀概述栈和队列，严格意义上来说，也属于线性表，因为它们也都⽤于存储逻辑关系为 "⼀对⼀" 的数据，但由于它们⽐较特殊，因此将其单独作为⼀篇⽂章，做重点讲解。
既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这些内容都会在本章做详细讲解。
使⽤栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使⽤队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队列。
⼆栈2.1 栈的基本概念同顺序表和链表⼀样，栈也是⽤来存储逻辑关系为 "⼀对⼀" 数据的线性存储结构，如下图所⽰。
从上图我们看到，栈存储结构与之前所了解的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：1. 栈只能从表的⼀端存取数据，另⼀端是封闭的；2. 在栈中，⽆论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。
拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。
因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。
因此，我们可以给栈下⼀个定义，即栈是⼀种只能从表的⼀端存取数据且遵循 "先进后出" 原则的线性存储结构。
通常，栈的开⼝端被称为栈顶；相应地，封⼝端被称为栈底。
因此，栈顶元素指的就是距离栈顶最近的元素，拿下图中的栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，下中的栈底元素为元素 1。
2.2 进栈和出栈基于栈结构的特点，在实际应⽤中，通常只会对栈执⾏以下两种操作：向栈中添加元素，此过程被称为"进栈"（⼊栈或压栈）；从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；2.3 栈的具体实现栈是⼀种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种⽅式：1. 顺序栈：采⽤顺序存储结构可以模拟栈存储数据的特点，从⽽实现栈存储结构。
栈是一种特殊的线性表，特殊之处在于插入和删除操作的位置受到限制，若插入和删除操作只允许在线性表的一端进行，则是栈，特点是后进先出。
栈的抽象数据模型：栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，允许操作的一端称为栈顶（top）不允许操作的一端称谓栈底（Bottom）,栈中插入元素操作称为入栈（push）,删除元素的操作称为出栈（pop）,没有元素的栈称为空栈、例如对数据序列｛A,B,C,D｝执行操作序列｛入栈，出栈，入栈，入栈，出栈，出栈。
出栈｝,出栈序列为｛B,D,C,A｝栈机器状态如图：由于栈的插入和删除操作只允许在栈顶进行，每次入栈元素即成为栈顶元素，每次出栈元素总是最后一个入栈元素，因此栈的特点是后进先出（Last In First Out）,就像一落盘子，每次将只有一个盘子在最上面，从最上面取走一个盘子，不能从中间插入或者插出。
栈的基本操作有创建栈，判断是否为空，入栈，出栈，和取出栈顶元素等。
栈不支持对指定位置的插入，删除等。
顺序栈采用顺序存储结构的栈称为顺序栈｛Sequential Stack｝,声明顺序栈如下，实现栈接口，使用顺序表作为成员变量实现栈，约定null不能入栈。
其中，入栈和出栈操作实现为顺序表尾部插入和尾部删除，时间复杂度为O(1),顺序表的插入方法已经实现自动扩充数组容量，当需要扩充容量时，入栈的时间复杂度为O(n)栈和线性表是不同的数据抽象类型，栈概念不依赖于线性表而存在，我们只是使用顺序表进行设计，也可以使用数组实现。
链式栈采用连式存储结构的栈称为链式栈（Linked Stack），单链表结构的链式栈及入栈，出栈操作如图，设单链表（不带头节点）头指针top指向第一个元素节点（栈顶），入栈操作是头插入，在栈顶节点之前插入节点，出栈操作是头删除，删除栈顶节点并返回栈顶元素，再使top指向新的栈顶节点。
声明链式栈类如下，实现栈接口。
使用单链表作为成员变量实现栈。
栈与队列实现先进先出和后进先出的数据结构数据结构是计算机科学中一门重要的基础课程，其中栈（Stack）和队列（Queue）是常用的数据结构。
栈和队列都具有不同的特点和应用场景，能够满足先进先出（FIFO）和后进先出（LIFO）的要求。
一、栈的实现先进先出栈是一种线性数据结构，具有后进先出（LIFO）的特点。
在栈中，只能在栈的一端进行操作，称为栈顶。
栈的基本操作包括入栈（Push）和出栈（Pop）。
1. 入栈（Push）操作：当要向栈中添加元素时，将新元素放置在栈顶，并将栈顶指针向上移动一位。
该操作保证了后添加的元素会处于栈顶的位置。
2. 出栈（Pop）操作：当要从栈中移除元素时，将栈顶的元素弹出，并将栈顶指针向下移动一位。
该操作保证了最后添加的元素会最先被移除。
栈的实现可以使用数组或链表来存储元素。
使用数组实现时，需要指定栈的最大容量。
使用链表实现时，栈的容量可以动态扩展。
二、队列的实现先进先出队列是一种线性数据结构，具有先进先出（FIFO）的特点。
在队列中，元素从队尾入队，从队头出队。
队列的基本操作包括入队（Enqueue）和出队（Dequeue）。
1. 入队（Enqueue）操作：当要向队列中添加元素时，将新元素放置在队尾，并将队尾指针向后移动一位。
该操作保证了后添加的元素会处于队列的尾部。
2. 出队（Dequeue）操作：当要从队列中移除元素时，将队头的元素弹出，并将队头指针向后移动一位。
该操作保证了最早添加的元素会最先被移除。
队列的实现也可以使用数组或链表。
与栈不同的是，队列的实现更适合使用链表，因为链表可以实现在队头和队尾高效地执行插入和删除操作。
三、使用栈和队列实现先进先出和后进先出为了实现先进先出和后进先出的数据结构，可以使用一种特殊的数据结构：双端队列（Double-ended Queue），也称为双端栈（Deque）。
双端队列具有栈和队列的特点，既可以在队尾插入和删除元素，也可以在队头插入和删除元素。
数据结构中栈的介绍1.栈的概念栈（Stack）是一种特殊的表，这种表只在表的一端进行插入和删除操作。
允许插入和删除数据元素的这一端称为栈顶；而另一固定的一端称为栈底。
不含任何元素的栈称为空栈。
栈的修改是按后进先出的原则进行的。
栈又称为后进先出(Last In First Out)表，简称为LIFO 表。
如图1所示：假设一个栈S中的元素为a,a,..,a，则称a为栈底元素，a为栈顶元nn1n-11素。
t1图 2 图12.栈的存储与操作（称为栈顶指针）由于栈是一个特殊的表，可以用一维数组来实现栈。
同时设立指针t 来指示栈顶元素的当前位置。
为最早入s[1]将栈底固定在数组的底部，我们用一个数组s[1..m]来表示一个栈时，即时，表示这个栈为一个空栈。
t=0(下标增大的方向)扩展。
当栈的元素，并让栈向数组上方时，表示这个栈已满。
当t=m 可以用下列方式定义栈：const; m=栈表目数的上限type} stack=array[1..m] of stype; {栈的数据类型vars:stack;}t:integer; {栈顶指针进栈、出栈操作的过程和函数（假设栈元素的数据类型为整型）：）(1)进栈过程（push时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢≥①若tm 出；不满则作②）；；（栈指针加１，指向进栈地址）②置t=t+1 为新进栈的元素）；xt)=x ③S(，结束（procedure push(var s:stack; x:integer;var t:integer);beginif t=m then writeln('overflow')elsebegint:=t+1;s[t]:=x;endend;(2)退栈函数（pop）空则下溢；≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈，①若t 不空则作②)； x）；②x=s(t)，（退栈后的元素赋给 t=t-1，结束（栈指针减１，指向栈顶）。
③function pop(var s:stack;var t:integer):integer;beginif t=0 then writeln('underflow')elsebeginpop:=s[t];t:=t-1;endend;读栈顶元素函数（top）(3)function top(var s:stack; t:integer):integer;beginif t=0 then writeln('underflow')elsetop:=s[t];end;3栈的应用举例依次入栈，以下出栈序列不可能出现的初始状态为空，元素a,b,c,d,e,f,g【例10-4】.设栈S ）。
的是（C.a,e,d,c,b,f,g B.b,c,a,f,e,g,d A.a,b,c,e,d,f,gE.g,e,f,d,c,b,aD.d,c,f,e,b,a,g，每个元素依次A题解：此题可以采用模拟的方法，依次判断各个选项是否能出现。
如出栈，a 进栈，然后b出栈，c进栈后出栈，进栈然后出栈，即得到此序列。
再来看B，a,b不能进栈后出栈，gd出栈，可以满足。
依此类推，发现只有E，e，f进栈，f，e出栈，d 满足，答案为E。
共五个车厢。
其中有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5.如下图,】10-5【例3也可以进入栈S让后面的车厢通过。
现已知第一个到达出口的是每个车厢可以向左行走, 号车厢，请写出所有可能的到达出口的车厢排列总数。
5 4 3 2 1 ←出口←↓S，4，出栈，此时栈中有元素进栈，然后，题解：首先必是12，3312，未进栈元素有 4我们可以讨论，如下：5的出栈顺序，之前出栈，一定在由于。
5我们可以分情况讨论，21四个数字的一个54(1)4先出栈：此时相当于，不经过栈直接到出口。
相当于42，，，514 5排在前，1排在排列，24/4=6前，共有种数（种）。
4的出栈顺序必连续，有以下三种排列：5和4先出栈：此时(2)5．5 4 2 1；2 5 4 1；2 1 5 4。
综上所述，总的排列数是9种。
【例1】计算后缀表达式题目描述数学上使用的是中缀表达式，在中缀表达式中需要使用括号来改变运算的优先级。
事实上我们可以用后缀表达式或前缀表达式，这两种表达式里就可以完全避免使用括号。
后缀表达式：运算符放在两个运算对象之后。
所有计算按运算符出现的顺序，由左而右进行。
例如：3*(5-2)+7 对应的后缀表达式为3.5.2.- *7.+@现有一后缀表达式，让你求表达式的值，已知运算符仅限于??????屜尯四种运算。
输入@表示表达式结束，'.'为操作数的结束符。
如：后缀表达式3.5.2.- *7.+@的值为16。
输入一个后缀表达式，无需判错，“/”作为整除运算。
输出后缀表达式的值，一个整数。
参考程序：program ex10_6;constn=30;typestack=array[1..n] of integer;vars:stack;a:string;t,i,j,k,q:integer;procedure push(var s:stack; x:integer;var top:integer);beginif top=n then writeln('overflow')elsebegintop:=top+1;s[top]:=x;endend;function pop(var s:stack;var top:integer):integer;beginif top=0 then writeln('underflow')elsebeginpop:=s[top];top:=top-1;endend;begini:=1; t:=0;readln(a);while a[i]<>'@' dobegincase a[i] of'0'..'9' :begink:=0;repeatk:=10*k+ord(a[i])-ord('0');i:=i+1;until a[i]='.' ;push(s,k,t); {数字进栈}end;'+' : push(s,pop(s,t)+pop(s,t),t); {取栈首的两个数值相加}'-' :beginj:=pop(s,t);push(s,pop(s,t)-j,t);end;'*' : push(s,pop(s,t)*pop(s,t),t); { 取栈首的两个数值相乘}'/' :beginj:=pop(s,t);push(s,pop(s,t) div j,t);end;end;i:=i+1;end;q:=pop(s,t); {最后栈中的元素即为答案}writeln(q);end.【例2】背包问题假设有n件质量为w，w，...，w的物品和一个最多能装载总质量为T的背包，能否n21从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即w+w+...+w=T。
若能，则背包问题有解，否则无解。
iki2i1算法思想首先将n件物品排成一列，依次选取；若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。
这时我们称背包装满。
若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈），然后在未装入的物品中挑选，重复此过程，直至装满背包（有解），或无物品可选（无解）为止。
具体实现设用数组w[1..N]，stack[1..N]分别存放物品重量和已经装入背包（栈）的物品序号，tot表示背包的剩余最大装载量。
每进栈一个物品，就从tot中减去该物品的质量,设i为待选物品序号,若tot-w[i]>=0，则该物品可选；若tot-w[i] < 0，则该物品不可选,且若I=n，则需退栈，若此时栈空，则说明无解。
参考程序：program ex10_7;var t,n,i:integer;w,stack:array[1..100]of integer;function knap(tot:integer):boolean;vari,top:integer;begintop:=0;i:=1;while (tot>0)and (i<=n)dobeginif (tot-w[i]>=0)and(i<=n) then begintop:=top+1;stack[top]:=i;tot:=tot-w[i];end;if tot=0 then exit(true){正好装满则返回true}else beginif (i=n)and(top>0)then{I=n时退栈}begini:=stack[top];dec(top);tot:=tot+w[i];if (i=n)and(top>0) thenbegin{如退栈后I=n，即退栈的元素是最后一个，则需再次退栈，因为此时已无法选择下一个物品}i:=stack[top];dec(top);tot:=tot+w[i];end;end;inc(i);end;end;exit(false);end;beginreadln(t,n);for i:=1 to n do read(w[i]); if knap(t) then writeln('Yes') else writeln('No');end.。
