 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/imperative-programming-resit/4/a/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 4 / a / Solution by

Codex  0 2026-10-25

Use a finite sequence

q

as abstract state, initially empty. One Scala interface is

trait DoubleEndedQueue {
  def isEmpty: Boolean
  def addLeft(x: Int): Unit
  def getLeft(): Int
  def addRight(x: Int): Unit
  def getRight(): Int
}

The emptiness query has no precondition; its result is

q_{0} = ⟨ ⟩

and its postcondition is

q = q_{0}

. Adding on the left has no precondition and gives

q = ⟨ x ⟩ + + q_{0}

. Adding on the right gives

q = q_{0} + + ⟨ x ⟩

. Both return 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.

 Read the full article

 New to topics? Read the docs here!