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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2010, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala.collection
package mutable
import generic._
import collection.immutable.{List, Nil}
import collection.Iterator
import annotation.migration
/** A stack implements a data structure which allows to store and retrieve
* objects in a last-in-first-out (LIFO) fashion.
*
* @tparam A type of the elements contained in this stack.
*
* @author Matthias Zenger
* @author Martin Odersky
* @version 2.8
* @since 1
* @define Coll Stack
* @define coll stack
* @define orderDependent
* @define orderDependentFold
* @define mayNotTerminateInf
* @define willNotTerminateInf
*/
@serializable @cloneable
class Stack[A] private (var elems: List[A]) extends scala.collection.Seq[A] with Cloneable[Stack[A]] {
def this() = this(Nil)
/** Checks if the stack is empty.
*
* @return true, iff there is no element on the stack
*/
override def isEmpty: Boolean = elems.isEmpty
/** The number of elements in the stack */
override def length = elems.length
/** Retrieve n'th element from stack, where top of stack has index 0 */
override def apply(index: Int) = elems(index)
/** Push an element on the stack.
*
* @param elem the element to push on the stack.
* @return the stack with the new element on top.
*/
def push(elem: A): this.type = { elems = elem :: elems; this }
/** Push two or more elements onto the stack. The last element
* of the sequence will be on top of the new stack.
*
* @param elems the element sequence.
* @return the stack with the new elements on top.
*/
def push(elem1: A, elem2: A, elems: A*): this.type = this.push(elem1).push(elem2).pushAll(elems)
/** Push all elements in the given traversable object onto
* the stack. The last element in the traversable object
* will be on top of the new stack.
*
* @param xs the traversable object.
* @return the stack with the new elements on top.
*/
def pushAll(xs: TraversableOnce[A]): this.type = { xs foreach push ; this }
@deprecated("use pushAll")
@migration(2, 8, "Stack ++= now pushes arguments on the stack from left to right.")
def ++=(xs: TraversableOnce[A]): this.type = pushAll(xs)
/** Returns the top element of the stack. This method will not remove
* the element from the stack. An error is signaled if there is no
* element on the stack.
*
* @throws Predef.NoSuchElementException
* @return the top element
*/
def top: A =
elems.head
/** Removes the top element from the stack.
*
* @throws Predef.NoSuchElementException
* @return the top element
*/
def pop(): A = {
val res = elems.head
elems = elems.tail
res
}
/**
* Removes all elements from the stack. After this operation completed,
* the stack will be empty.
*/
def clear(): Unit = elems = Nil
/** Returns an iterator over all elements on the stack. This iterator
* is stable with respect to state changes in the stack object; i.e.
* such changes will not be reflected in the iterator. The iterator
* issues elements in the reversed order they were inserted into the stack
* (LIFO order).
*
* @return an iterator over all stack elements.
*/
@migration(2, 8, "Stack iterator and foreach now traverse in FIFO order.")
override def iterator: Iterator[A] = elems.iterator
/** Creates a list of all stack elements in LIFO order.
*
* @return the created list.
*/
@migration(2, 8, "Stack iterator and foreach now traverse in FIFO order.")
override def toList: List[A] = elems
@migration(2, 8, "Stack iterator and foreach now traverse in FIFO order.")
override def foreach[U](f: A => U): Unit = super.foreach(f)
/** This method clones the stack.
*
* @return a stack with the same elements.
*/
override def clone(): Stack[A] = new Stack[A](elems)
}
// !!! TODO - integrate
object Stack {
def apply[A](xs: A*): Stack[A] = new Stack[A] ++= xs
}
|
