常用的数据结构和算法4.ppt

专业教程 理论讲解部分 Ver3.1 第021课 算法及数据结构 概述： 栈的概念 栈的实现 重点： 难点： 栈的实现 栈的实现 4 栈 栈只允许访问一个数据项：即最后插入的数据项。移除这个数据项后才能访问倒数第二个插入的数据项，依此类推。这种机制在不少编程环境中都很有用。 栈提供了一种“后入先出”的一种数据结构 栈是一块连续的(物理的或者逻辑的)存储区域.有两个标识标志出栈的两个端点 –栈底和栈顶. 栈需要提供2个最基本的操作压入(push)和弹出(pop) 第021课 算法及数据结构 下面我们用一个数组来实现一个最简单的栈. private int[] stack; 但是,只有一个数组还无法实现栈得功能,我们还需要一些标识. private final int SIZE; private final int BOTTOM = 0; private int top; 其中,SIZE是数组得大小,栈得大小要比数组得小1个,随后我们会解释原因.当这个栈被创建后其大小不会改变,所以我们定义它为final(不会改变得变量).BOTTOM标识着这个栈得栈底,它始终为数组得第一个元素,所以为final得0.top标识着这个栈得栈顶,它会随着栈得使用变化. 4.1 栈的初始化 第021课 算法及数据结构 4 栈 初始化栈 BOTTOM top 0 SIZE 当这个栈被初始化之后,如图 SIZE = size; stack = new int[SIZE]; top = BOTTOM; 初始化代码如下: 其中,size为初始化参数.可以当作已知量. 第021课 算法及数据结构 4.1 栈的初始化 4 栈 栈被初始化时有一下几点: 2.栈底通常定义于存储空间得一段,而且通常是固定得. 1.存储空间得初始化.如果是动态的仅仅需要得到其大小及初始空间得创建. 3.令栈顶指向栈底.这里我们只需令top = BOTTOM; 此时,一个空栈被创建. 第021课 算法及数据结构 4.1 栈的初始化 4 栈 4.2 空栈的判断 一个栈被建立,我们需要在任意时刻需要了解到它得情况,比如是否为空. 下面我们来看看如何判断一个栈是否为空. public boolean isEmpty(){ if(top != BOTTOM){ return false; }else{ return true; } } 判断得依据是依靠判断top与BOTTOM的关系. 当top ==BOTTOM时,此时栈为空,否则栈非空. 第021课 算法及数据结构 4 栈 空栈 BOTTOM top 0 SIZE 1 2 BOTTOM top SIZE 0 非空栈 第021课 算法及数据结构 4.2 空栈的判断 4 栈 4.3 满栈的判断 同样,我们还需要在任何时刻需要判断栈是否为满栈. public boolean isFull(){ if(top != SIZE){ return false; }else{ return true; } } 判断得依据是依靠判断top与SIZE的关系. 当top ==SIZE时,此时栈为满,否则栈不满. 第021课 算法及数据结构 4 栈 空栈 1 2 3 4 5 6 7 BOTTOM 0 SIZE 1 2 BOTTOM top SIZE 0 非空栈 top 注意:这里需要声明一点,top指向的是下一个将要使用的空间. 为了数组的安全,不至越界.通常top == SIZE定义为满栈.这就是为什么栈的空间比数组的小的原因. 第021课 算法及数据结构 4.3 满栈的判断 4 栈 4.4 入栈(压栈 push) 栈是要用来存储数据的,数据被存储到栈中,这个动作叫入栈或者压栈. 下面我们来看看压栈的实现. public synchronized void push(int data) throws IllegalStateException{ if(!isFull()){ stack[top++] = data; }else{ throw new IllegalStateException(Stack is overload.); } } 第021课 算法及数据结构 4 栈 这里我们要注意入栈的步骤: 1.需要判断栈是否是满栈,如果栈满,那么返回一个异常说明栈已经满了.无法在使其它元素入栈.如果栈非满,那么继续. 2.将数据存储到top指向的空间.由于top始终指向第一个未使用的空间.所以可以将数据存储进去. 3.将top向栈底反向移动一个单位. 注意,第2步与第3步千万不能颠倒.否则会引起栈的存储异常. 第021课 算法及数据结构 4