queue_clean.c++

class Stack {
  private:
    int value;
    const Stack *next;
    Stack( int _value, const Stack *_next = 0 ) : value(_value), next(_next) { }
  public:
    const Stack* push( int _value ) const {
      return new Stack(_value, this);
    }
    bool empty() const {
      return !this;
    }
    int top() const {
      assert(this);
      return value;
    }
    const Stack* pop() const {
      assert(this);
      return next;
    }
    static const Stack *null;
};
const Stack *Stack::null = 0;

class Queue {
  private:
    int size, help2_size;
    const Stack *main, *help, *main2, *help2;
    Queue( int _size, int _help2_size, const Stack *_main, const Stack *_help,
       const Stack *_main2, const Stack *_help2 )
      : size(_size), help2_size(_help2_size), main(_main), help(_help),
        main2(_main2), help2(_help2) {}
    Queue* morph() {
      if (help2_size == -1) {
        help2_size = size;
        help2 = Stack::null;
        main2 = main;
      }
      if (help2_size > 0) {
        help2_size--;
        help2 = help2->push(main2->top());
        main2 = main2->pop();
      }
      if (help2_size == 0) {
        help = help2;
        help2_size = -1;
        help2 = main2 = Stack::null;
      }
      return new Queue(size, help2_size, main, help, main2, help2);
    }
  public:
    Queue() : size(0), help2_size(-1) {
      main = help = main2 = help2 = Stack::null;
    }
    const Queue* push( int value ) const {
      return Queue(size + 1, help2_size, main->push(value), help, main2, help2).morph();
    }
    bool empty() const {
      return size == 0;
    }
    int top() const {
      return help->top();
    }
    const Queue* pop() const {
      assert(size);
      return Queue(size - 1, help2_size == -1 ? -1 : help2_size - 1,
           main, help->pop(), main2, help2).morph();
    }
};