《栈的基本知识.pdf》由会员分享，可在线阅读，更多相关《栈的基本知识.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1 栈的基本知识 内容提要 1、栈的概念和特性；2、栈的存储结构：顺序存储和链式存储；3、双栈及操作；4、栈的几种运算（操作）实现；5、栈的简单应用举例；重点难点 1、栈的特性和应用场合；2、栈的存储结构；3、栈的操作实现；内容讲授 1 栈的概念和特性 栈（stack）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。如果我们把冼净的碗“摞上”称为进栈（压栈），把“取用碗”称为出栈（弹出），那么上例的特点是：后进栈的先出栈。然而，摞
2、起来的碗实际上是一个线性表，只不过“进栈”和“出栈”都在最顶上进行，或者说，元素的插入和删除操作都是在线性表的一端进行而已。一般而言，栈是一个线性表，其所有的插入和删除操作均是限定在线性表的一端进行，允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)。若给定一个栈 S=（a1,a2，a3，an），则称 a1为栈底元素，an为栈顶元素，元素 ai位于元素 ai-1之上。栈中元素按a1,a2，a3，an 的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为 an,an-1，a1。也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。因此栈又称为后进
3、先出(LIFOLast In First Out)表。我们常用一个图来形象地表示栈，其形式如下图：通常，对栈进行的操作主要有以下几种：2 在使用栈之前，首先需要建立一个空栈，称建栈（栈的初始化）；往栈顶加入一个新元素，称进栈（压栈、入栈）；删除栈顶元素，称出栈（退栈、弹出）；查看当前的栈顶元素，称读栈；注意与的区别 在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈。2 栈的存储结构（1）顺序栈 栈是一种线性表，在计算机中用一维数组作为栈的存储结构最为简单，操作也最为方便。例如，设一维数组 STACK1.n 表示一个栈，其中 n 为栈的容量，即可存放元素的最大个数。栈的第一个元素，或称
4、栈底元素，是存放在 STACK1处，第二个元素存放在 STACK2处，第 i 个元素存放在 STACKi处。另外，由于栈顶元素经常变动，需要设置一个指针变量 top，用来指示栈顶当前位置，栈中没有元素即栈空时，令 top=0；当 top=n时，表示栈满。如果一个栈已经为空，但用户还继续做出栈（读栈）操作，则会出现栈的“下溢”；如果一个栈已经满了，用户还继续做进栈操作，则会出现栈的“上溢”。这两种情况统称为栈的溢出。建栈的操作很简单，只要建立一个一维数组，再把栈顶指针置为零即可。栈的容量根据具体的应用要求而定，一般要定义的足够大。比如：type arraytype=array1.n of int
5、eger;var stack:arraytype;top:integer;（2）链式栈 当我们学可指针和链表后，也可以用链表来模拟栈（链式栈），这样可以提高空间利用率，但编程复杂度提高了。定义方法如下：type link=node node=record data：integer;next：link end;var hs:link;(3)记录型栈 由于栈本身和栈顶指针是密不可分的，所以有时我们把他们定义成一个记录来处理。如：type stack=record vec:array1.n of integer;n为栈可达到的最大深度 top:integer;end;var s:stack;栈的某个
6、元素为 s.veci,栈顶指针为 s.top 3 3 对栈的几种运算的实现方法 （1）建栈 只要把栈顶指针置为零。即在程序开始时，置 top:=0；（2）测试栈 测试栈顶指针的值，若 top=0，则栈空；若 top=n，则栈满。（3）读栈 若 top=0，则栈空，无栈顶元素可读，显示出错信息，中止程序；若 top0，则回送栈顶元素的值 STACKtop给某个变量。（4）进栈（push）将栈顶指针加 1 后，再把新元素送到栈顶。注意进栈操作前必须保证栈不能满，否则会溢出。假设新元素 x 为整型，栈的最大深度为 n。则，x 和 n 设置为值型参，而栈和栈顶指针要设置成变量型参。为什么？proced
7、ure push(var stack:arraytype;var top:integer;n:integer;x:integer);begin if top=n then begin writeln(Stack full!);halt end else begin top:=top+1;stacktop:=x end end;（5）出栈(pop)取得栈顶元素的值给 x后，再把栈顶指针 top的值减 1。注意出栈操作前必须保证栈非空。还要注意都用变量型参。为什么？请问：本来的栈顶元素还在不在，还好不好调用？procedure pop(var stack:arraytype;var top:int
8、eger;var x:integer);begin if top=0 then begin writeln(Stack empty!);halt end else begin x:=stacktop;top:=top-1 end end;*下面是把以上五个操作修改成链式栈的操作：(1)置空栈 setnull(hs);不回收结点 procedure setnull(hs:link);begin hs=nil;end;4 procedure setnull(hs:link);回收结点 begin while hsnil do begin p:=hs;hs:=hs.next;dispose(p)en
9、d;end;(2)进栈 push(hs,x)procedure push(var hs:link;x:integer);begin new(p);p.data:=x;不再判断栈是否满了，有无问题？除非系统无可用内存了，死机 p.next:=hs;hs:=p;如何防止以上情况的出现？注意及时释放内存空间 end;(3)出栈 pop(hs，x)procedure pop(var hs:link;var x:integer);begin if hs=nil then begin writeln(underflow);halt;end else begin x:=hs.data;p:=hs;hs:=h
10、s.next;dispose(p);如果不加,可能会怎样？end end;(4)读取栈顶元素 readtop(hs)function readtop(hs:link):inteter；begin if hs=nil then begin writeln(underflow);halt;end else readtop:=hs.data 还要不要释放空间？end；(5)判断栈空 sempty(hs)function sempty(hs:link):Boolean;begin sempty:=(hs=nil);end；5 *下面再把以上五个操作修改成记录型栈的操作：（1）建栈 s.top:=0；（
11、2）测试栈 s.top=0，则栈空；若 s.top=n，则栈满。（3）读栈 若 s.top=0，则栈空，无栈顶元素可读，显示出错信息，中止程序；若 s.top0，则回送栈顶元素的值 s.vecs.top。(4)进栈 procedure push(var s:stack;x:integer);begin if s.top=n then begin writeln(Stack full!);halt end else begin s.top:=s.top+1;s.vecs.top:=x end end;（5）出栈 procedure pop(var s:stack;var x:integer);b
12、egin if s.top=0 then begin writeln(Stack empty!);halt end else begin x:=s.vecs.top;s.top:=s.top-1 end end;出栈有时也可用函数实现，如：function pop(var s:stack):integer;begin if s.top=0 then begin writeln(Stack empty!);halt end else begin pop:=s.vecs.top;s.top:=s.top-1 end end;4.双栈及操作 在有些应用中需要设置两个容量都很大的栈时(元素类型要一致)
13、，为了节省空间，可以使它们共享一维数组空间 s1.t，两个栈的栈底分别设在数组两端，让两个栈彼此迎面“增长”，两个栈顶指针分别为 top1,top2。仅当两个栈的栈顶指针在中间相遇时（top1=top2）才发生“上溢”。如下图：6 type bothstack=record data：array1.maxn of integer；top1，top2：0.maxn+1；end；var bs:stack；k:1.2；k=1表示栈 1，k=2表示栈 2 栈的应用举例 1、若已知一个栈的入栈顺序是 1，2，3，n，其输出序列为 P1，P2，P3，Pn，若 P1是 n，则 Pi 是(C )。A)i B)
14、n-1 C)n-i+1 D)不确定 2、以下哪一个不是栈的基本运算(B )。A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空 D)将栈置为空栈 3、设栈 S 和队列 Q 初始状态为空，元素 e 1，e 2，e 3，e 4，e 5，e 6依次通过栈 S，一个元素出栈后即进入队列 Q，若出队的顺序为 e 2，e 4，e 3，e 6，e 5，e 1，则栈 S 的容量至少应该为（B ）。A）2 B）3 C）4 D）5 4、设栈 S 的初始状态为空,现有 5 个元素组成的序列1,2,3,4,5,对该序列在 S 栈上依次进行如下操作(从序列中的 1开始,出栈后不在进栈):进栈,进栈,进栈,出栈,进
15、栈,出栈,进栈,问出栈的元素序列是:_,栈顶指针的值为_，栈顶元素为:_。解答：出栈序列为3，4，栈顶指针值为 3，栈顶元素为 5。5、设栈 S 和队列 Q 初始状态为空，元素 e 1，e 2，e 3，e 4，e 5，e 6依次通过栈 S，一个元素出栈后即进入队列 Q，若出队顺序为 e 2，e 4，e 3，e 6，e 5，e 1，则栈 S 的容量至少应该为_。解答：为 3。6、如下图,有一个无穷大的的栈 S,在栈的右边排列着 1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈 S 让后面的车厢通过。现已知第一个到达出口的是 3 号车厢，请写出所有 7 1 2 3 可能的到达出
16、口的车厢排列总数(不必给出每种排列)。出口 1 2 3 4 5 S 解答：9 分别为：32145、32154、32415、32451、32541、34215、34251、34521、35421；是否类似于用生成法求 n的全排列的问题？思考：题目意思同上，现在有 n个车厢，第 1个到达出口的是 i号车厢，问有多少种可能？7、讨论 NOIP2003初中组第三那题：栈（Stack.pas）【问题背景】栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。栈的重要性不言自明，任何一门数据结构
17、的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。【问题描述】输出序列 尾端 头端 操作数序列 头端 栈 A 宁宁考虑的是这样一个问题：一个操作数序列，从 1，2，一直到 n（图示为 1 到 3 的情况），栈 A 的深度大于 n。现在可以进行两种操作，1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push操作）2.将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop操作）使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3生成序列 2 3 1的过程。（原始状态如上图
18、所示）1 2 3 1 2 3 1 3 2 1 1 3 2 2 3 2 3 1 8 你的程序将对给定的 n，计算并输出由操作数序列 1，2，n经过操作可能得到的输出序列的总数。【输入格式】输入文件只含一个整数 n（1 n 18）【输出格式】输出文件只有一行，即可能输出序列的总数目 【输入样例】3【输出样例】5 【算法分析】因为这道题中的 N 最大有 18，如果用穷举法，时间复杂度约为 N！，是显然不行的。而且本题只要求“可能输出序列的总数目”。所以，我认为其中一定存在着某种关系。于是，我就开始着手推出一个公式。我觉得，这个式子一定是一个递归公式，因为 N 的情况中包含了 N 前面的情况。即对于每
19、个数字，它在某个时刻可能出栈也可能不出栈，而且他会把整个问题一分为二，成为 2个相同的子问题。现在试想：1 可以什么时候出栈？可以是第 1 个出栈，也可以是第 2 个出栈，也可以是最后一个（第 n 个）出栈。设输入 n 时，问题的解为 f(n)，假设 1 是第 i 个出栈的，则在他之前有 i-1个数，解为 f(i-1)；后面还有 n-i个数，解为 f(n-i)。再根据乘法原理，方案数为：f(i-1)*f(n-i)，其中 i 从 1 到 n。即递归公式为：F（n）=niinFiF1*1）（）（n0）=101*niinFiF）（）（n0）注意，这个递归公式的边界条件为：F（0）=1。利用这个公式，我们就可以非常快得算出结果。【参考程序】const maxn=18;var i,j,n:longint;s:array 0.maxn of int64;注意范围 begin assign(input,stack.in);reset(input);assign(output,stack.out);9 rewrite(output);read(n);close(input);s0:=1;for i:=1 to maxn do begin si:=0;for j:=0 to i-1 do si:=si+sj*si-j-1 end;writeln(sn);close(output)end.