 Solution

class ArrayDoubleEndedQueue(val MAX: Int) extends DoubleEndedQueue {
  require(MAX > 0)
  private val a = new Array[Int](MAX)
  private var head = 0
  private var size = 0

  private def slot(offset: Int): Int =
    ((head.toLong + offset.toLong) % MAX.toLong).toInt

  private def before(i: Int): Int = if (i == 0) MAX - 1 else i - 1
  private def after(i: Int): Int = if (i == MAX - 1) 0 else i + 1

  def isEmpty: Boolean = size == 0

  def addLeft(x: Int): Unit = {
    require(size < MAX)
    head = before(head)
    a(head) = x
    size += 1
  }

  def addRight(x: Int): Unit = {
    require(size < MAX)
    a(slot(size)) = x
    size += 1
  }

  def getLeft(): Int = {
    require(size > 0)
    val x = a(head)
    head = after(head)
    size -= 1
    x
  }

  def getRight(): Int = {
    require(size > 0)
    val x = a(slot(size - 1))
    size -= 1
    x
  }
}