文档介绍：第1页
2. 逻辑结构 与同线性表相同(xiānɡ tónɡ)，仍为一对一关系。
3. 运算规则 只能在栈顶运算，且访问结点时依照(yīzhào)后进先出
（LIFO）或先进后出（FILO）的原则。
：
定义 限定只能在表的一端进行插入(chā rù)和删除运算的
线性表（只能在栈顶操作）
上次课内容回顾
第1页/共34页
第一页，共34页。
第2页
讨论：有无通用的判别原则？
有。在可能的输出(shūchū)序列中，不存在这样的输入序列i，j，k，能同时满足入栈顺序i，j，k 和 出栈顺序k ，i， j。
例4 一个(yī ɡè)栈的输入序列为12345，若在入栈的过程中允许出栈，则可能得到的出栈序列有多少种，分别是什么？
第2页/共34页
第二页，共34页。
第3页
例1：回文游戏
设计思路(sīlù)：用栈暂存回文
例2：数制转换（十转N）
设计思路(sīlù)：用栈暂存低位值
例3 ：括号匹配的检验
设计思路(sīlù)：用栈暂存左括号
例4：表达式求值
设计思路(sīlù)：用栈暂存运算符
简化(jiǎnhuà)程序设计问题
第3页/共34页
第三页，共34页。
第4页
回文游戏(yóuxì)：顺读与逆读字符串一样（不含空格）
d
a
d
top
若不等，非回文
若直到(zhídào)栈空都相等，则是回文
有没有更简洁的办法呢？
(读入字符串，压入n/2个字符,n为字符个数)
多进制输出(shūchū)：
字符串：“madam I madam”
“上海自来水来自海上”
例 把十进制数159转换成八进制数
(159)10=(237)8
159
8
19
8
2
8
0
2 3 7
余 7
余 3
余 2
top
top
7
top
7
3
top
7
3
2
第4页/共34页
第四页，共34页。
第5页
多进制输出(shūchū)：
例 把十进制数159转换成八进制数
(159)10=(237)8
159
8
19
8
2
8
0
2 3 7
余 7
余 3
余 2
top
top
7
top
7
3
top
7
3
2
public class Test
{
public static void main(String args[])
{
int i=159;
String binStr=(i);
String otcStr=(i);
String hexStr=(i);
(binStr);
}
}
第5页/共34页
第五页，共34页。
第6页
多进制输出(shūchū)：
import .*;
class T
{
public static void main(String[] args)
{
(toOctal(159));
}
public static String toOctal(int a)
{
String str = ""; Stack s = new Stack();
while(a!=0) { (a%8); a=a/8; }
while(!()) {str