Use a finite sequence as abstract state, initially empty. One Scala interface isThe emptiness query has no precondition; its result is and its postcondition is . Adding on the left has no precondition and gives . Adding on the right gives . Both return
trait DoubleEndedQueue {
def isEmpty: Boolean
def addLeft(x: Int): Unit
def getLeft(): Int
def addRight(x: Int): Unit
def getRight(): Int
}Unit.Each removal requires a nonempty incoming sequence.
getLeft() returns its first entry and leaves the remaining final sequence; getRight() returns its last entry and leaves the remaining initial sequence. These contracts remove exactly one occurrence, so duplicate values are permitted and do not collapse the sequence into a set.Keep private references
first and last, both initially null. A nonempty representation is a finite acyclic chain from first through next to last. Its representation invariant requires first.prev == null, last.next == null, and reciprocal links between every adjacent pair. The nodes reached by following prev from last are exactly the same nodes in reverse order. No internal node reference is exposed to clients.The abstraction function reads the
datum values along the forward chain, giving the abstract sequence from left to right. The empty representation has both endpoint references null; the invariant requires that either both are null or both are nonnull. A single node has both links null. Updating both endpoint references when removing that last node is therefore essential.The following class uses the node type supplied in the paper:An insertion connects a fresh endpoint to the old chain and updates its reciprocal link. A removal reconnects the exposed endpoint to null; the singleton case also clears the opposite endpoint. The remaining chain therefore satisfies the same representation invariant and has exactly the abstract sequence required by the specification. Every operation performs pointer work, excluding allocation costs for a newly added node.
class DoublyLinkedDoubleEndedQueue extends DoubleEndedQueue {
private var first: Node = null
private var last: Node = null
def isEmpty: Boolean = first == null
def addLeft(x: Int): Unit = {
val node = new Node(x, null, first)
if (first == null) last = node
else first.prev = node
first = node
}
def addRight(x: Int): Unit = {
val node = new Node(x, last, null)
if (last == null) first = node
else last.next = node
last = node
}
def getLeft(): Int = {
require(!isEmpty)
val old = first
first = old.next
if (first == null) last = null
else first.prev = null
old.next = null
old.datum
}
def getRight(): Int = {
require(!isEmpty)
val old = last
last = old.prev
if (last == null) first = null
else last.next = null
old.prev = null
old.datum
}
}Add this method inside the concrete class:Its precondition is a valid receiver, including an empty one. Its postcondition leaves and prints the entries of from left to right in the displayed bracket format, followed by a newline. The loop invariant says that the printed entries are precisely the chain before
def display: Unit = {
print("[")
var current = first
var separator = ""
while (current != null) {
print(separator)
print(current.datum)
separator = ", "
current = current.next
}
println("]")
}current; the not-yet-printed entries are the chain starting there. Advancing along the acyclic chain terminates after its length. Printing changes the output stream, but it changes neither links nor payloads.With that display format the output isThe first removal takes the newly prepended left value . The right removal later takes the most recently appended . The next left removal takes the earlier , leaving the ordered sequence . The two equal values are different occurrences, and the displayed order follows the links rather than numerical sorting.
20
10
10
Queue status: [30, 40, 15] Articles by others on the same topic
There are currently no matching articles.