疯狂java笔记之栈和队列栈队列双端队列

栈的英文单词是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更好。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习和数学

[数据结构与算法] 线性表总结

线性表也是基本的数据结构之一,Python里面的list和tuple,就是线性表的一种实现。 首先什么是表呢,其实很简单,比如【元素1,元素2,。。。,元素n】...

47311
来自专栏SpringBoot

String、StringBuffer与StringBuilder之间区别

最近学习到StringBuffer,心中有好些疑问,搜索了一些关于String,StringBuffer,StringBuilder的东西,现在整理一下。

1012
来自专栏偏前端工程师的驿站

Java魔法堂:深入正则表达式API

目录                               一、前言 二、正则表达式的使用诉求 三、java.util.regex包 四、java.lan...

2035
来自专栏个人分享

Scala第四章学习笔记(面向对象编程)

DelayedInit特质是为编译器提供的标记性的特质。整个构造器被包装成一个函数并传递给delayedInit方法。

811
来自专栏java一日一条

Java面试题:栈和队列的实现

(5)设计含最小函数min()的栈,要求min、push、pop、的时间复杂度都是O(1)

1141
来自专栏小灰灰

JDK容器学习之Queue: ArrayDeque

数组双端队列 ArrayDeque 双端队列,表示可以添加元素到(或删除,获取)队列头也可以添加元素到(或删除,获取)队列尾 ? 1. 底层数据结构 类中定义成...

1966
来自专栏chenjx85的技术专栏

leetcode-28-Implement strStr()

2796
来自专栏程序员互动联盟

【高级编程】C++中vector使用详解

1. 在C++中的详细说明 vector是C++标准模板库中的部分内容,它是一个多功能的,能够操作多种数据结构和算法的模板类和函数库。 vector之所以被认为...

38911
来自专栏一个会写诗的程序员的博客

Kotlin 中 有趣 好玩的高阶函数《Kotlin极简教程》正式上架:

912
来自专栏博岩Java大讲堂

Java集合--非阻塞队列(ConcurrentLinkedQueue实现原理)

6887

扫码关注云+社区

领取腾讯云代金券