class Test {
  function : Main(args : String[]) ~ Nil {
    queue := Queue->New();

    queue->Push(3); queue->Push(6); queue->Push(9);
    queue->Pop();
    queue->Push(12);
    queue->Push(15);

    while(<>queue->Empty()) {
      queue->Top()->GetValue()->PrintLine();
      queue->Pop()->PrintLine();
    };
    queue->Pop()->PrintLine();
  }
}

class Queue {
  @head, @tail : Node;

  New() {
  }

  method : public : Push(value : Int) ~ Nil {
    if(@head = Nil) {
      @head := @tail := Node->New(value);
    }
    else {
      tail := Node->New(@tail, value);
      @tail->SetNext(tail);
      @tail := tail;
    };
  }

  method : public : Pop() ~ Bool {
    if(@head <> Nil) {
      if(@head = @tail) {
        @head := @tail := Nil;
      }
      else {
        prev := @tail->GetPrev();
        prev->SetNext(Nil);
        @tail := prev;
      };

      return true;
    };

    return false;
  }

  method : public : Top() ~ Node {
    return @tail;
  }

  method : public : Empty() ~ Bool {
    return @head = Nil;
  }
}

class Node {
  @value : Int;
  @next : Node;
  @prev : Node;

  New(value : Int) {
    @value := value;
  }

  New(prev : Node, value : Int) {
    @prev := prev;
    @value := value;
  }

  method : public : GetValue() ~ Int {
    return @value;
  }

  method : public : SetNext(next : Node) ~ Nil {
    @next := next;
  }

  method : public : GetPrev() ~ Node {
    return @prev;
  }

  method : public : ToString() ~ String {
    return @value->ToString();
  }
}