数据结构第四章、栈.ppt

第四章 栈、队列和哈希表 一、栈 栈的类型定义 Stack类简介 栈的应用举例 栈的定义 栈可以看成一种“特殊的”线性表，是限定仅在表尾(top)进行插入或删除操作的线性表。 允许插入和删除的一端称为栈顶(top，表尾)，另一端称为栈底(bottom，表头) 特点：后进先出 (LIFO) 栈的抽象数据类型的定义 ADT Stack { 数据对象：D = {ai | ai∈ElemSet, i=1,2,3,…,n} 数据关系：R = {ai-1, ai | ai-1,ai∈D} 基本操作：Stack( ) // 初始化新栈 Push( ) // 进栈 Pop( ) // 出栈 Peek( ) // 取栈顶元素值 Clear( ) // 清空栈 Contains( ) // 确定某元素是否在栈中 　 } ADT Stack 基本操作的实现 //入栈 public void Push(T item) { if(IsFull()) { Console.WriteLine(Stack is full); return; } data[++top] = item; } //出栈 public T Pop() { T tmp = default(T); if (IsEmpty()) { Console.WriteLine(Stack is empty); return tmp; } tmp = data[top]; --top; return tmp; } Stack类 表示对象的简单的后进先出非泛型集合。 命名空间： ?System.Collections 参考文献地址： / 栈的应用举例 ——例1：数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 public void Conversion(int n) { Stack s = new Stack(); while(n 0) { s.Push(n%8); n = n/8; } while(!s.IsEmpty()) { n = s.Pop(); Console.WriteLine(“{0}”, n); } } 例2，表达式求值 在机器内部，任何一个表达式都是由操作数、运算符和界限符组成。操作数和运算符是表达式的主要部分，分界符标志了一个表达式的结束。根据表达式的类型，表达式分为三类，即算术表达式、关系表达式和逻辑表达式。为简化问题，我们仅讨论四则算术运算表达式，并且假设一个算术表达式中只包含加、减、乘、除、左圆括号和右圆括号等符号，并假设‘#’是界限符。 算术表达式的两种表示 ——中缀表达式 运算符在两个操作数中间的表达式 如：12+(2+5*4) /2 - 5 问题：既要考虑括号的作用，又要考虑运算符的优先级，还要