用Scala实现一个简单的双向队列

在Scala里,最常用的数据结构是列表,它是一种函数式的数据结构。

scala> val list = List(1,2,3,4)
list: List[Int] = List(1, 2, 3, 4)

scala> list.head
res1: Int = 1

scala> list.tail
res2: List[Int] = List(2, 3, 4)

对列表的任何操作不会影响本身的列表,列表一旦创建便不会发生改变,这会使得我们更好的推导数据的变化。作为一门Scalable的语言,Scala允许使用者也可以开发一个类似内置列表的数据结构。在这篇文章会简单的实现一个函数式双向队列,也以此来展示类型参数和如何做简单的信息隐藏。 Begin: 类型参数可以让我们编写泛型类和特质,例如列表就是泛型的,定义为List[T],它的实例可以为List[Int],List[String]等。作为双向队列的第一段代码输入:

class Deque[T]{

}

其中T可以是任何字母。现在Deque类还没有构造参数,再补充上:

class Deque[T](elems:List[T]){

}

为了简便实现,函数式双向队列采用了内置的列表,现在Deque类可以传入一个参数elems。加上第一个方法:

override def toString = elems match {
      case List() => "Deque()"
      case List(_*) => { val y = elems mkString ","
                     s"Deque($y)"}
    }

这里使用了模式匹配,如果是空列表返回空,否则返回类似Deque(1,2,3)的文字。双向队列有四个基础方法popLeft,popRight,pushLeft,pushRight。(在这里暂时不考虑运行效率)

def popLeft: T = elems.head

def popRight: T = elems.last

def pushRight(x:T) = elems match {
  case List() => new Deque(List(x))
  case _ => new Deque(elems ::: List(x))
}
def pushLeft(x:T) = elems match {
  case List() => new Deque(List(x))
  case _ => new Deque(List(x) ::: elems)
}

将完整的Deque类输入到REPL:

scala>   class Deque[T](elems:List[T]){
     |     override def toString = elems match {
     |       case List() => "Deque()"
     |       case List(_*) => { val y = elems mkString ","
     |                      s"Deque($y)"}
     |     }
     |     def popLeft: T = elems.head
     |
     |     def popRight: T = elems.last
     |
     |     def pushRight(x:T) = elems match {
     |       case List() => new Deque(List(x))
     |       case _ => new Deque(elems ::: List(x))
     |     }
     |     def pushLeft(x:T) = elems match {
     |       case List() => new Deque(List(x))
     |       case _ => new Deque(List(x) ::: elems)
     |     }
     |   }
defined class Deque

现在的Deque长这样:

scala> val deque = new Deque(List(1,2,3,4))
deque: Deque[Int] = Deque(1,2,3,4)

scala> val deque2 = new Deque(List('a','b','c'))
deque: Deque[Char] = Deque(a,b,c)

原生的Scala数据结构是没有丑陋的new方法和指定List实例的,为了避免这个,还记得伴生对象吗?

object Deque {
  def apply[T](xs:T*) = new Deque[T](xs.toList)
}

将这个对象和Deque类放在同一个源文件,而Deque()实际上Deque.apply()的语法糖,当使用Deque(1,2,3)构造双向队列时,调用的Deque对象的apply方法。现在再将这个输入REPL:(因为REPL每一行都是一个新的object,所以会warning)

scala>   object Deque {
     |     def apply[T](xs:T*) = new Deque[T](xs.toList)
     |   }
defined module Deque
warning: previously defined class Deque is not a companion to object Deque.
Companions must be defined together; you may wish to use :paste mode for this.

scala> val deque = Deque(1,2,3,4)
deque: Deque[Int] = Deque(1,2,3,4)

scala> deque.popLeft
res0: Int = 1

scala> deque.popRight
res1: Int = 4

scala> deque.pushRight(5)
res2: Deque[Int] = Deque(1,2,3,4,5)

scala> deque.pushLeft(0)
res3: Deque[Int] = Deque(0,1,2,3,4)

看,借助了Scala强大的类型参数,现在这个函数式双向队列可以做到和原生列表一样的使用。

原文发布于微信公众号 - 鸿的学习笔记(shujuxuexizhilu)

原文发表时间:2018-04-18

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吾爱乐享

java之学习LinkedList的特有功能及案例分析

13220
来自专栏拭心的安卓进阶之路

Java 集合深入理解(11):LinkedList

今天心情鱼肚白,来学学 LinkedList 吧! 日常开发中,保存一组数据使用的最多的就是 ArrayList, 其次就是 LinkedList 了。 我们...

29370
来自专栏公众号_薛勤的博客

Java过滤掉字符串中的html标签、style标签、script标签

11620
来自专栏java闲聊

JDK1.8 LinkedList 源码解析

23240
来自专栏desperate633

LeetCode 20. Valid Parentheses题目分析代码

给定一个字符串所表示的括号序列,包含以下字符: '(', ')', '{', '}', '[' and ']', 判定是否是有效的括号序列。

9020
来自专栏架构之路

判断栈的出栈顺序合法性

栈的出栈顺序合法性是指给定一系列元素,如1 - N,按照从小到大的方式入栈,每个元素的出栈时机不定。题目给定一个出栈顺序,我们来判断这个出栈顺序有没有可能发生。...

34430
来自专栏编程

详解栈及其实现

转自:melonstreet http://www.cnblogs.com/QG-whz/p/5170418.html 栈的特点 栈(Stack)是一种线性存储...

23860
来自专栏我的技术专栏

数据结构图文解析之:栈的简介及C++模板实现

16850
来自专栏Java 源码分析

LinkedList 源码分析

LinkedList 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,...

28340
来自专栏博岩Java大讲堂

Java集合--Queue(Java中实现2)

54350

扫码关注云+社区

领取腾讯云代金券