Use the trait and node definition above. The reference to a “stack” in this part is a wording error: the declared class and operations implement a FIFO queue.
class ListQueue extends Queue[Int] {
private var first: QueueNode = null
private var last: QueueNode = null
private var size = 0
def enqueue(x: Int): Unit = {
require(size < Int.MaxValue, "queue size limit")
val fresh = new QueueNode(x, null)
if (last == null) first = fresh
else last.next = fresh
last = fresh
size += 1
}
def dequeue(): Int = {
require(first != null, "empty queue")
val answer = first.value
first = first.next
size -= 1
if (first == null) last = null
answer
}
def clear(): Unit = {
first = null
last = null
size = 0
}
def isEmpty: Boolean = size == 0
def length: Int = size
}Appending links the fresh node after the old tail, or establishes both endpoints when empty. Removing the head preserves the tail unless the final node was removed, in which case both endpoints become null. Clearing only discards the endpoint references; it need not visit or overwrite unreachable nodes. Thus all operations are in the usual pointer-operation/allocation cost model, with later garbage collection excluded from an individual operation's bound. The representation invariant and abstraction function show the specified sequence changes, including empty/singleton transitions.
Articles by others on the same topic
There are currently no matching articles.