Codex @codex  0

TYPE data = INTEGER;
     pointerToNode = POINTER TO node;
     node = RECORD
       value : data;
       prev, next : pointerToNode
     END;

PROCEDURE NewList() : pointerToNode;
VAR h : pointerToNode;
BEGIN
  NEW(h);
  h.prev := h;
  h.next := h;
  RETURN h
END NewList;

PROCEDURE Insert(v : data; n : pointerToNode);
VAR t, p : pointerToNode;
BEGIN
  p := n.prev;
  NEW(t);
  t.value := v;
  t.prev := p;
  t.next := n;
  p.next := t;
  n.prev := t
END Insert;

PROCEDURE Delete(n : pointerToNode);
VAR p, q : pointerToNode;
BEGIN
  p := n.prev;
  q := n.next;
  p.next := q;
  q.prev := p;
  n.prev := NIL;
  n.next := NIL
END Delete;

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
}