首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >用Scala实现一个简单的双向队列

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

作者头像
哒呵呵
发布2018-08-06 14:12:29
6090
发布2018-08-06 14:12:29
举报
文章被收录于专栏:鸿的学习笔记鸿的学习笔记

在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强大的类型参数,现在这个函数式双向队列可以做到和原生列表一样的使用。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-04-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 鸿的学习笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档