美文网首页JAVA基础(未看)
疯狂java笔记之栈和队列

疯狂java笔记之栈和队列

作者: Jack921 | 来源:发表于2017-08-24 17:00 被阅读266次

    栈的英文单词是Stack,它代表一种特殊的线性表,这种线性表只能在固定一端(通常认为是线性表的尾端)进行插入,删除操作。

    栈的基本定义

    栈是一种数据结构,它代表只能在某一端进行插入,删除操作的特殊线性表,通常就是在线性表的尾端进行插入,删除操作。

    对于栈而言,允许进行插入,删除操作的一端被称为栈顶(top),另一端咋被称为栈底(bottom)。

    对于一个栈不包含任何元素,那么这个栈就被称为空栈。
    从栈顶插入一个元素被称为进栈,将一个元素从栈顶删除被称为“弹出栈”,对应的英文说法为pop,如下图:

    stack.PNG

    对于元素为a0,a1,a2,...,an-1的栈,假设栈中元素被a0,a1,a2,...,an-1的次序进栈,那么a0未栈底元素,an-1为栈顶元素。出栈时第一个弹出的元素应为栈顶元素,也就是an-1.也就是说,栈中元素的修改是按后进先出(LIFO)的原则进行的。

    归纳起来,可以再对栈下一个定义:栈就是一种后进先出(LIFO)的线性表。

    栈的常用操作

    栈是一种被限制过的线性表,通常不应该提供线性表中的如下方法:

    • 获取指定索引处的元素
    • 按值查找数据元素的位置
    • 向指定索引处插入数据元素
    • 删除指定元素索引处的数据元素
      从上面这个方法可以看出,栈不应该提供从中间任意位置
      访问元素的方法。也就是说,栈只允许在栈顶插入,删除元素。
      栈的常用操作如下:
    • 初始化:通常是一个构造器,用于创建一个空栈
    • 返回栈的长度:该方法用于返回栈中数据元素的个数
    • 入栈:向栈的栈顶插入一个数据元素,栈的长度+1
    • 出栈:从栈的栈顶删除一个数据元素,栈的长度-1,该方法通常饭后被删除的元素
    • 访问栈顶元素:返回栈顶的数据元素,但不删除栈顶元素
    • 判断栈是否为空:改方法判断栈是否为空,如果栈为空则返回true,否则返回false.
    • 清空栈:将栈清空

    类似于线性表即采用顺序存储的方式来实现,也可以用链式结构来实现,也可使用链式结构来实现,栈同样即可采用顺序结构来存储栈内的元素,也可采用链式结构来存储栈内元素。

    栈的顺序存储结构及实现

    顺序存储结构的栈简称为顺序栈,它利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。栈底位置固定不变,它的栈顶可以直接通过顺序栈底层数组的数组元素arr[size-1]来访问。顺序栈的存储示意图如下图:

    stack_sort.PNG

    顺序栈中数据元素的物理关系和逻辑关系是一致的,先进栈的元素位于栈底,栈底元素的存储位置相对也比较小。

    1.进栈

    对于顺序栈的进栈操作而言,只需将新的数据元素存入栈内,然后让记录栈内元素个数的变量加1,程序即可再次通过arr[size-1]重新访问新的栈顶元素。进栈操作示意图如下:


    inti_stack.PNG

    由于顺序栈底层通常会采用数组来保存数据元素,因此可能出现的情况是:当程序试图让一个数据元素进栈时,底层数据已满,那么就必须扩充底层数组的长度来容纳新进栈的数据元素。

    1.出栈

    对于顺序栈的出栈操作而言,需要将栈顶元素弹出栈,程序要做两件事。

    • 让记录栈内元素个数的变量减1.
    • 释放数组对栈顶元素的引用。

    出栈操作示意图如下图:


    out_stack.PNG

    对于删除操作来说,只要让记录栈内元素个数的size减1,程序即可通过arr[size-1]访问到新的栈顶元素。但不要忘记释放原来栈顶的数组引用,否则会引起内存泄漏。

    栈比普通线性表的功能更弱,栈时一种被限制过的线性表,只能从栈顶插入,删除数据元素。

    栈的链式存储结构及实现

    程序可以采用单链表来保存栈中所有元素,这种链式结构的栈也被称为栈链。对于栈链而言,栈顶元素不断地改变,程序只要使用一个top引用来记录当前的栈顶元素即可。top引用变量永远引用栈顶元素,再使用一个size变量记录当前栈中包含多少个元素即可。如下图:

    linked_stack.PNG

    1.进栈

    对于栈链的进栈操作,程序只需要做如下两件事:
    -让top引用指向新元素添加的元素,新元素的next引用指向原来的栈顶元素。

    • 让记录栈内元素个数的size变量加1.
      进栈操作示意图如下:
    into_linked_stack.PNG

    2.出栈

    对于链栈的出栈操作,需要将栈顶元素弹出栈,程序需要做两件事情:

    • 让top引用指向原栈顶元素的下一个元素,并释放原来的栈顶元素
    • 让记录栈内元素个数的size变量减1.

    出栈操作示意图如下:

    out_linked_stack.PNG

    对于顺序栈来说,程序开始就需要在底层为他开辟一块连续的内存(数组),这个空间浪费其实很大.从空间利用率的角度说,链栈的空间利用率比顺序栈的空间利用率要高一些。

    java集合中的栈

    Java集合实际上提供两种栈供开发者使用:

    • java.util.Stack:它就是一个最普通的顺序栈,底层数据实现。这个Stick类是线程安全的,在多线程环境下也可以放心使用
    • java.util.LinkedList:LinkedList是一个双端链表:除此之外。LinkedList还可作为栈使用,查看该类api将会发现,他同样提供了push(),pop(),peek()等方法,这表明LinkedList其实还可以当成栈使用。LinkedList代表栈的链式实现,但它是线程不安全的,如果需要在多线程环境下使用,则应该使用Collections类的工具发将其“改造”成线程安全的类。

    队列

    队列的基本定义

    队列是一种特殊的线性表,他只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作,进行插入操作的端称为队尾,进行删除的端称为对头。

    如果队列中不包含任何元素,该队列就被称为空队列。

    对于一个队列来说,每个元素总是从队列的rear端进入队列,然后等待该与元素之前的所有元素出对之后,当前元素才能出对。因此,把队列简称为先进先出(FIFO)的线性表。如下图:


    queue.PNG

    队列的常用操作

    队列同时是一种被限制过的线性表,通常不应该提供线性表中的如下方法:

    • 获取指定索引处的元素
    • 按值查找数据元素的位置
    • 向指定索引处插入数据元素
    • 删除指定索引处的数据元素
      从上面这些方法可以看出,队列不应该提供从中间任意位置访问元素的方法,也就是说,队列只允许在队列的前端(front)删除元素,只允许在队列的后端(rear)插入元素。
      队列的常用操作如下:
    • 初始化:通常是一个构造器,用于创建一个空队列
    • 返回队列的长度:该方法用十返回队列中数据元素的个数。
    • 加入元索:向队列的rear端插入一个数据元素,队列的长度+1
    • 删除元素:从队列的front端删除一个数据元素,队列的长度-1,该方法通常返回被删除的元素。
    • 访问队列的前端元素:返回队列的front端的数据元素,但不删除该元素。
    • 判断队列是否为空:该方法判断队列是否为空,如果队列为空则返回true否则返回false
    • 清空队列:将队列清空

    类似于线性表既可采用顺序存储的方式来实现,也可采用链式结构来卖现,队列同样既可采用顺序结构来存储队列元素,也可采用链式结构来存储队列元素。

    队列的顺序存储结构及实现

    系统采用一组地址连续的存储单元依次存放队列从rear端到front端的所有数据元素,程序只需(front和rear两个整型变量来记录队列front端的元素索引、rear端的元素索引。示意图如下:


    queue_sort.PNG

    顺序队列可能会造成假满的问题,程序有如下解决方:

    • 每次将元素移除队列时将队列中的所有元素向front端移动一位,这种方式front值永远为0,有元素插入队列时rear值+1,有元素移除队列时rear值-1,。但这种方式非常浪费时间,因为每次将元素从队列移除都需要进行“整体搬家”。
    • 将数组存储区看成一个首尾相接的环形区域,当存放数组的最大地址之后,rear值再次变为0。采用这种技巧存储的队列称为循环队列。

    循环队列

    为了重新利用循环顺序队列底层数组中已删除元素所占用的空间,消除可能出现的“假满”现象,可以将顺序队列改进为循环队列。

    循环队列是首尾相连的队列:当front,rear变量值达到底层数组的capacity-1之后,再前进一位就自定变成0,。示意图如下:

    circulation.PNG

    不管队列是空还是满,都会出现一个情况:front==rear.如果底层数据中elementData[front]==null,则表明此时队列为空,否则表明该队列已满。

    队列的链式存储结构及实现

    使用链式结构保存线性表,也可以采用链式结构来存储队列的各元素,采用链式存储结构的队列也被称为链队列。

    对于链队列而言,由于程序需要从rear端添加元素,然后从front端移除元素,因此考虑对链队列增加front,rear两个引用变量,使他们分别执行链队列的头,尾两个节点。链队列示意图如下:


    queue_llinked.PNG

    由于链队列采用链式结构类保存队列中所有元素,该队列允许添加无限多个数据元素,因此链队列无队列满的问题。

    1.插入队列

    对于链队列而言,插入操作的实现非常简单,只要创建一个新节点,让原rear节点的next引用指向新的节点,再让rear引用指向该新节点即可。

    queue_linked_insert.PNG

    2.移除队列

    对于链队列而言,移除操作的实现也非常简单,只要让front引用指向原front所引用节点的下一个节点即可。当然,不要忘记释放原front节点的引用。示意图如下:


    queue_linked_delete.PNG

    Java集合中的队列

    从JDK1.5开始,java的集合框架中提供了一个queue接口,该接口代表了一个队列,实现该接口的类可以当成队列使用。Queue里包含了6个方法,用于代表队列包含的3个标志性的方法,如下所示:

    • 插入:在队列的rear端插入元素
    • 移除:在队列的front端删除元素
    • 访问:访问队列的front端元素

    Java为上面的每个方法方法提供了两个版本:具有特殊返回值的版本和抛出异常的版本,这样就产生了6个方法。

    版本 抛出异常的版本 具有特殊返回值的版本
    插入 add(e) offer(e)
    移除 remove() poll()
    访问 element() peek()

    双端队列

    双端队列代表一种特殊的队列,它可以在两端同时进行插入,删除操作,如下图所示:

    double_queue.PNG

    对于双端队列,由于它可以从两端分别进入插入,删除操作,如果程序将所有的插入,删除操作固定在一端进行,这个双端队列就变成前面介绍的栈,由此可见,Deque和Queue,Stack之间的关系如图:

    double_queue_relation.PNG

    双端队列(Deque)既可说是Queue的子接口,也可说Stack(JDK并未提供这个接口)的子接口。因此。Deque即可当成队列使用,也可当成栈使用。

    由此可见,Deque其实就是Queue和Stack混合而成的一种特殊的线性表,完全可以参考起前面的Queue,Stack的实现类实现Deque。

    JDK为Deque提供了ArrayDeque和LinkedList两个常见的实现类。其中,ArrayDeque代表顺序存储结构的双端队列,LinkedList则代表链式存储结构的双端队列。

    LinkedList代表一种双向,链式存储结构的循环线性表,这里有提到LinkedList代表线程安全的,链式结构的双端队列,由此可见,LinkedList实在是一个功能非常强大的集合类。事实上,LinkedList几乎是Java集合框架中方法最多的类。


    LinkedList_relation.PNG

    虽然LinkedList工具类的功能非常强大,它既可当成线性表使用,也可当成栈使用,还可当成队列使用,但对大部分程序而言,使用ArrayList,ArrayDeque的性能比LinkedList更好。

    相关文章

      网友评论

        本文标题:疯狂java笔记之栈和队列

        本文链接:https://www.haomeiwen.com/subject/mehddxtx.html