数据结构名师课件.ppt

1、第三章 栈和队列,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,3.1 栈的类型定义,3.2 栈类型的实现,3.3 栈的应用举例,3.4 队列的类型定义,3.5 队列类型的实现,栈（stack）,定义 栈是只能在一端插入和删除的线性表 特性：后进先出（LIFO）或 先进后出（FILO） 设栈s=（a1，a2，. . . ,ai，

2、. . . ，an）， 其中a1是栈底元素， an是栈顶元素。 栈顶（top)：允许插入和删除的一端； 约定top始终指向新数据元素将存放的位置。 栈底（bottom):不允许插入和删除的一端。,3.1 栈的类型定义,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：, ADT Stack,InitStack( / 存储空间的初始分配量 #define STACKINCREMENT 10; / 存储空间的分配增量 typedef struc

3、t SElemType *base; / 栈底指针 SElemType *top; / 栈顶指针(栈顶元素的下一个位置) int stacksize; / 当前分配的存储容量 SqStack;,类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。,1）和顺序表一样采用增量式的空间分配； 2）操作和栈顶相关：插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置；删除操作（出栈）：删除栈顶元素；取元素操作：取栈顶元素的值。各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在O(1)时间内能获取操作位置，故可设置专门的栈顶指针top。,3）约定：top指向栈顶元素的下一个位置（便于表

4、示空栈）。 4）栈顶的初始化：S.top = S.base(在上述3)约定下的空栈形式)， 5）栈空：S.base = S.top， 栈满：S.top - S.base = S.stacksize 6）入栈：*S.top + = e， 出栈：e = *-S.top 注意：4), 5), 6)步受3)制约。约定不同，相应的判定和处理也不一样。 如假设top就指向栈顶元素，此时4),5),6)如何？,基本操作的实现,base,空栈,a 进栈,b 进栈,a,top,base,top,base,top,a,b,约定：top指向栈顶元素的下一个位置,base,e 进栈,f 进栈溢出,e出栈,edcba,

5、top,base,top,base,top,edcba,dcba,Status InitStack (SqStack ,取栈顶元素GetTop_Sq算法设计,参数：顺序栈S、取得的栈顶元素 ,入栈操作Push_Sq算法设计,参数：顺序栈,Status Push (SqStack ,出栈操作Pop_Sq算法设计,参数：顺序栈 scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion,例二、 括号匹配的检验 假设在表达式中 （）或（

6、） 等为正确的格式， （ ）或（ ）或 （）) 均为不正确的格式。,则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。,从左至右扫描表达式，遇左括号入栈，遇右括号与栈顶元素比较：若左右括号匹配，则继续扫描；否则说明不匹配，结束。在上述操作中，若栈为空，或扫描结束后栈不为空，均说明不匹配。,分析可能出现的不匹配的情况:,到来的右括弧并非是所“期待”的；,例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8,到来的是“不速之客”；,直到结束，也没有到来所“期待”的括弧。,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“

7、右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。,Status matching(string .,例三、行编辑程序问题,如何实现？,“每接受一个字符即存入存储器” ?,并不恰当！,处理规则：遇#退一格；遇退一行 算法思想：引入栈，保存终端输入的一行字符（逐行处理）；遇#退一格出栈一次遇退一行清栈 步骤：1）初始化栈S2）读入字符ch3）ch!=EOF 3.1) ch!=EOF ,则实际有效的是下列两行： while (*s) putchar(*s+);,while (ch

8、 != EOF / 从终端接收下一个字符 ,ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = get char();,while (ch != EOF) /EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的 数据区；,例四、 迷宫求解,通常用的是“穷举求解”的方法,求迷宫路径算法的基本思想是：,若当前位置“可通”，则纳入路径，继续前进;,若当前位置“不可通”，则后退，换方向继续探索;,若四周“均无通路”，则将当前位置从路径中删除出去。,问题：找从“入口”到“出口”的路径（所经过的通道方块） 分析： 方块的表示坐标，当前的状态（障碍、未走的通路、已走的

9、通路）； 已走的路径： 路径中各方块的位置及在路径中的序号; 从各方块出发已探索的方向，注意不能重复（可约定按东、南、西、北的方向顺次探索）； 从当前方块无路可走时，将已走路径回退一个方块，继续探索其他未走的方向 栈存储已走的通道块,设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当前位置； 否则 while (栈不空）；,求迷宫中一条从入口到出口的路径的算法：, ,若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块；,若栈不空但栈顶位

10、置的四周均不可通， 则删去栈顶位置；/ 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； ,若栈空，则表明迷宫没有通路。,限于二元运算符的表达式定义: 表达式 := (操作数) + (运算符) + (操作数) 操作数 := 简单变量 | 表达式 简单变量 : = 标识符 | 无符号整数,例五、 表达式求值,只包含+, -, *, / 四个双目运算符，且算符本身不具有二义性； 三个运算规则运算符优先关系（考虑算符本身的优先级和结合性）； 只有 (=)，#=#； 假设输入的是一个合法的表达式。,问题描述,引入OPTR和OPND两个栈 初始：OPTR有

11、一个元素#，OPND为空 读入一字符c c=#：return(GetTop(OPND) c非运算符：Push(OPND,c) c运算符：t=GetTop(OPTR)，比较t和c的优先关系 tc：Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); x=Operate(a, theta, b); Push(OPND, x); 继续读入字符处理。,算法思想,表达式的三种标识方法：,设 Exp = S1 + OP + S2,则称 OP + S1 + S2 为前缀表示法(波兰式),S1 + OP + S2 为中缀表示法,S1 + S2 + OP 为后缀表示法(逆波

12、兰式),例如: Exp = a b + (c d / e) f 前缀式: + a b c / d e f 中缀式: a b + c d / e f 后缀式: a b c d e / f +,结论:,1）操作数之间的相对次序不变;,2）运算符的相对次序不同;,3）中缀式丢失了括弧信息， 致使运算的次序不确定;,4)前缀式的运算规则为: 连续出现的两个操作数和在它们 之前且紧靠它们的运算符构成一 个最小表达式;,5)后缀式的运算规则为: 运算符在式中出现的顺序恰为 表达式的运算顺序; 每个运算符和在它之前出现 且 紧靠它的两个操作数构成一个最小 表达式。,运算符： * / * + - （ ） 界限

13、符： ；,以表达式 A*B + CD 为例说明利用栈的求值过程。,优先级： 4 3 3 2 2 1 1 0,操作数变量：A B C D,A*B + C/D;,top2,思想：从左到右扫描表达式，若当前读入的是操作数，则进操作数（NS）栈，若读入的符号是运算符，应进行判断： 若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”，则弹出栈顶元素，继续扫描下一符号。否则当前读入符号暂不处理，从操作数栈弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，结果送入操作数栈，继续处理当前读入符号。 2.若读入的运算符的优先级大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹

14、出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。 3. 若读入的是“；”，且运算符栈顶的符号也是“；”时，则表达式处理结束。从操作数栈弹出表达式结果。,例 计算 2+4-3*6,表达式的不同表示之间的相互转换 逆波兰式波兰式 如：abcd+*e*+ +a*b+cde 共同点 运算对象的次序一致 不需要括号区分优先级和结合性 某算符在所有算符中的次序决定了它的计算次序 转换的思想 参照逆波兰式的计算过程，将计算转换为待计算的算符和运算对象的串的拼接 逆波兰式中缀表达式 如： abcd+*e*+ a+b*(c+d)*e,输入：表达式符号序列,表达式

15、求值算法：,输出：表达式值 y,初始化栈 NS、OS,Push (OS, “;” , top2)； t=0; /表示扫描下一个符号 while (t 2) IF t=0 THEN read W;,IF W 为操作数 THEN Push( NS, W, top1),ELSE p=OStop2; /读运算符栈栈顶元素，存入p .,IF (Wp)or(W=“(“) THEN,Push (OS, W, top2); t=0;,ELSE IF (p=“;” ）and (W=“ ;”) THEN, Pop (NS, y,top1); t=2; /处理过程结束,ELSE IF (p=“(“ )and (w=

16、“）”）THEN,ELSE Pop(NS,x,top1);,Pop(NS,z,top1);,Pop(OS,p,top2）；,x=z x;,Push(NS ,x ,top1);,t=1; /t=1,当前的符号下次重新考虑,输出 y; return;, Pop(OS ,p,top2); t=0; ,练习1：A+B*C-D/E；,练习：A-B/C+D*E；,优先级相同时，应先处理栈中数据,错在哪？,练习2：若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的一个出栈次序是（ ）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3,d,练习3：用一维

17、数组设计栈，初态是栈空，top=0。现有输入序列是 a、b、c、d，经过 push、push、pop、push、pop、push操作后，输出序列是（ ），栈顶指针是（ ）,b、c,2,如何从后缀式求值？,先找运算符， 再找操作数,例如： a b c d e / f +,ab,d/e,c-d/e,(c-d/e)f,如何从原表达式求得后缀式？,每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。,分析 “原表达式” 和 “后缀式”中的运算符: 原表达式: a + b c d / e f 后缀式: a b c + d e / f ,从原表达式求得后缀式

18、的规律为：,1) 设立操作数栈；,2) 设表达式的结束符为“#”， 予设运算符栈的栈底为“#”；,3) 若当前字符是操作数， 则直接发送给后缀式。,4) 若当前运算符的优先数高于栈顶运算符，则进栈；,5) 否则，退出栈顶运算符发送给后缀式；,6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。,从原表达式求得后缀式的规律为：,void transform(char suffix , char exp ) InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch,

19、 OP) Pass( Suffix, ch); else if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while / CrtExptree, ,switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c) break; defult : while(Gettop(S, c) / switch,1、栈（stack）,定义 栈是只能在一端插入和删除的线性表 特性：后进先出

20、（LIFO）或 先进后出（FILO） 设栈s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是栈底元素， an是栈顶元素。 栈顶（top)：允许插入和删除的一端； 约定top始终指向新数据元素将存放的位置。 栈底（bottom):不允许插入和删除的一端。,内容回顾,2、栈的类型定义,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：, ADT Stack,内容回顾,InitStack( . z=f(x); return

21、(2*z); ,f 函数,调用 f函数,int f1(int x) int y,z; . z=f2( y); return (2*z); ,int f2(int t) int a,c; . c=f1(a); return (3+c); ,间接调用,递归应用的特点 对于一个问题，当问题规模很大时，往往难于直接求解，此时： 将大问题分解成若干小问题 考虑如何利用这些小问题的解构成大问题的解 这种分解、合成的方法就是递归求解中的递归方法； 另外，递归应用要注意避免陷入死循环，递归必须有出口，即要确立递归的结束条件，给出此时的直接求解方法。,以求4的阶乘为例：,4！=4*3！,3! =3* 2!,2!

22、 =2* 1!,1! =1,4! =4*6,2! =2*1,3! =3*2,下 推,回 代,例如：写一函数求n!,1 (n=0,1) n! = n * (n-1)！ (n1),int fac ( int n) int f; if(n0) printf(“n0,data error!n”); return; else if(n=0 |n= =1) f=1; else f= n*fac(n-1) ; return f; ,例如：写一函数求n!,1 (n=0,1) n! = n(n-1)！ (n 1),以求4的阶乘为例：,fac(4)=4*fac(3),fac(3)=3*fac( 2),fac(2)

23、=2*fac( 1),fac(1)=1,fac(4)=4*6,fac(2)=2*1,fac(3)=3*2,下 推,回 代,利用栈实现递归调用,将所有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。,调用前当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,递归的实现,保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。,调用后从被调用函数返回调用函数之前，应该完成下列三项任务：,多个函数嵌套调用的规则是：,此时的内存管理实行“栈式管理”,后调用先返回

24、 ！,例如： void main( ) void a( ) void b( ) a( ); b( ); /main / a / b,main的数据区,函数a的数据区,函数b的数据区,递归工作栈：递归执行过程中占用的 数据区。 递归工作记录：每一层的递归参数合成 一个记录。 当前活动记录：栈顶记录指示当前层的 执行情况。 当前环境指针：递归工作栈的栈顶指针。,递归函数执行的过程可视为同一函数进行嵌套调用：,例： 递归的执行情况分析,void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i=w;+i) printf(“%3d,”,w); p

25、rintf(“n”); ,运行结果： 1， 2，2， 3，3，3，,递归调用执行情况如下：,特点 是无终止的递归调用，因此，应该给定一个限制递归次数的条件。,问题求解是递归的Hanoi塔 问题描述： 有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则： 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻，每个塔座上不能将大盘压到小盘上,void hanoi(int n, char a, char b, char c)n-圆盘数a-源塔座b-中介塔座 c-目标塔座 搬动方法 n=1

26、, a-c n1:hanoi(n-1, a, c, b)a-chanoi(n-1, b, a, c) 注意用递归调用的结果，不关注该结果如何获得的细节,执行情况： 递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示,解决方法： n=1时，直接把圆盘从A移到C n1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题,void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由

27、小到大且至上而下编号为1至n / 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 1 if (n=1) 2 move(x, 1, z); / 将编号为的圆盘从x移到z 3 else 4 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔 5 move(x, n, z); / 将编号为n的圆盘从x移到z 6 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔 7 8 ,递归与回溯N皇后问题 在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列或同一对角线上，则称它们为互相攻击。n皇后问题是指： 找到

28、这 n 个皇后的互不攻击的布局,0 1 2 3,0 1 2 3,k = i+j,k = n+i-j-1,基本思路依次为每一行确定该行皇后的合法位置 安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探 ( j = 0, , n-1 ) 在第 j 列安放一个皇后 如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后： 如果没有出现攻击，在第 j 列安放的皇后不动递归安放第 i+1行皇后 如果第 i 行不能安放皇后，则回溯到第 i-1 行，从下一个列(j+1)继续试探,数据结构设计 标识每一列是否已经安放了皇后线性表，表长为N 标识各条主对角线是否已经安放了皇

29、后 线性表，表长为2N-1 标识各条次对角线是否已经安放了皇后 线性表，表长为2N-1 记录当前各行的皇后在第几列布局状况 线性表，表长为N 存储结构的选择表长固定，有随机存取的要求顺序表,存储结构 标识每一列是否已经安放了皇后数组col，表长为N 标识各条主对角线是否已经安放了皇后 数组md，表长为2N-1 标识各条次对角线是否已经安放了皇后 数组sd，表长为2N-1 记录当前各行的皇后在第几列布局状况 数组q，表长为N,算法void Queen( int i, int n ) for ( int j = 0; j n; j+ ) if ( 第 i 行第 j 列没有攻击 ) 在第 i 行第

30、j 列安放皇后; if ( i = n-1 ) 输出一个布局; else Queen ( i+1, n ); 撤消第 i 行第 j 列的皇后; ,!colj mdn+i-j-1=1; sdi+j=1; qi = j;,输出q,colj= 0; mdn+i-j-1=0; sdi+j=0; qi = 0;,回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串 2.去掉空格（原串） 3.压入栈 4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文,字符串：“madam im adam”,雾锁山头山锁雾，天连水尾水连天,蜜蜂酿蜂蜜,黄山落叶松叶落山黄,练习题： 1、请写出下面程

31、序的运行结果。 #include “stdlib.h” void p(int w) int i; if (w!=0) 1 printf(“%3d”,w) 2 p(w-1); 3 p(w-1); main p(3); ,1 2 3 运行结果：3211211,2 1 3 运行结果：1213121,2、编写一个程序计算2阶Fibonacci数列： 0 n=0 Fib(n)= 1 n=1 Fib(n-1)+Fib(n-2) 其它,定义：队列是限定只能在表的一端进行插入， 在表的另一端进行删除的线性表。 队尾(rear)允许插入的一端 队头(front)允许删除的一端 队列特点：先进先出(FIFO),3

32、.4 队列的类型定义,ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾,基本操作：, ADT Queue,队列的基本操作：,InitQueue( 出队列：x=sq+front;,存在问题 设数组维数为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出真溢出 当front-1,rear=M-1时，再有元素入队发生溢出假溢出 解决方案 队首固定，每次出队剩余元素向下移动浪费时间 循环队列,3.5 队列类型的实现,链队列链式映象,

33、循环队列顺序映象,typedef struct QNode / 结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;,链队列链式映象,typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;,a1,an,Q.front Q.rear,Q.front Q.rear,空队列,入队算法 JD *ldcr(JD *rear,int x) JD *p; p=(JD *)malloc(sizeof(JD); p-data=x; p-next=N

34、ULL; rear-next=p; return(p); ,出队算法 int ldsc(JD *front,JD *rear) JD *s; int x; if(front=rear) return(-1); s=front-next; front-next=s-next; if(s-next=NULL) rear=front; x=s-data; free(s); return(x); ,Status InitQueue (LinkQueue ,Status EnQueue (LinkQueue ,Status DeQueue (LinkQueue ,循环队列 基本思想：把队列设想成环形，让

35、sq0接在sqM-1之后，若rear+1=M,则令rear=0;,实现：利用“模”运算 入队： rear=(rear+1)%M; sqrear=x; 出队： front=(front+1)%M; x=sqfront; 队满、队空判定条件,#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;,循环队列顺序映象,队空：front=rear 队满：

36、front=rear,如何区分队空和队满？,区分队空和队满的方法 设标志位(上次的更新动作)：0-创建/删除，1-插入 引入队列长度 少用一个元素空间：插入前判断 Q.front=(Q.rear+1)%MAXQSIZE,0,1,7,2,3,4,5,6,Q.front,Q.rear,0,1,7,2,3,4,5,6,Q.front,Q.rear,a1,a2,a3,a4,a5,a6,a7,有维护的代价,难点连续的存储单元的上下界：d1,d2 初始化空队：Q.front = Q.rear = d1; 队空： Q.front=Q.rear 队满： Q.front=(Q.rear-d1+1)%(d2-d1

37、+1)+d1 入队： 前提：队列不满 Q.baseQ.rear = e; Q.rear = (Q.rear-d1+1)%(d2-d1+1)+d1; 出队：前提：队列不空 e = Q.baseQ.front; Q.front = (Q. front-d1+1)%(d2-d1+1)+d1,入队算法： void en_cycque(int sq, int front, int rear, int x) if(rear+1)%M)=front) printf(overflow); else rear=(rear+1)%M; sqrear=x; ,出队算法： int dl_cycque(int sq,

38、int front, int rear, int *q) if(front=rear) return(0); else front=(front+1)%M; *q=sqfront; return(1); ,Status InitQueue (SqQueue ,Status EnQueue (SqQueue ,Status DeQueue (SqQueue ,1. 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。,2. 熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。,3. 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。,4. 理解递归算法执行过程中栈的状态变化过程。,本章学习要点,本章小结,本章主要介绍了如下一些基本概念： 栈：是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出