-
Notifications
You must be signed in to change notification settings - Fork 316
/
Queue.scala
86 lines (74 loc) · 1.81 KB
/
Queue.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
* This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
* and written by Vladimir Kostyukov, http://vkostyukov.ru
*
* Queue http://en.wikipedia.org/wiki/Queue_(abstract_data_type)
*
* -Notes-
*
* This queue also known as Banker's Queue. There is also Physics Queue. Interested in the topic -
* read the Okasaki`s book.
*
* Enqueue - O(1)
* Dequeue - O(1)
* Front - O(1)
* Rear - O(1)
*/
class Queue[+A](in: List[A] = Nil, out: List[A] = Nil) {
/**
* Check whether this queue is empty or not.
*/
def isEmpty: Boolean = in.isEmpty && out.isEmpty
/**
* Dequeues the first element from this queue.
*
* Time - O(1)
* Space - O(1)
*/
def dequeue: (A, Queue[A]) = out match {
case hd :: tl => (hd, new Queue(in, tl))
case Nil => in.reverse match {
case hd :: tl => (hd, new Queue(Nil, tl))
case Nil => throw new NoSuchElementException("Empty queue.")
}
}
/**
* Enqueues given element 'x' into the end of this queue.
*
* Time - O(1)
* Space - O(1)
*/
def enqueue[B >: A](x: B): Queue[B] = new Queue(x :: in, out)
/**
* Returns the first element of this queue.
*
* Time - O(1)
* Space - O(1)
*/
def front: A = dequeue match { case (a, _) => a }
/**
* Returns the rear of this queue.
*
* Time - O(1)
* Space - O(1)
*/
def rear: Queue[A] = dequeue match { case (_, q) => q }
override def toString = (out ::: in.reverse).mkString("Queue(",",",")")
}
object Queue {
/**
* Creates a new empty queue.
*
* Time - O(1)
* Space - O(1)
*/
def empty[A]: Queue[A] = new Queue()
/**
* Creates a new queue fromm given 'xs' sequence.
*
* Time - O(n)
* Space - O(1)
*/
def apply[A](xs: A*) =
xs.foldLeft(Queue.empty[A]) { case (acc, x) => acc.enqueue(x) }
}