創建不可變隊列的問題

Question

我正在使用下面的代碼來創建一個不可變隊列。

import java.util.NoSuchElementException; 
import java.util.Queue; 

public class ImmutableQueue<E> { 

    //Two stacks are used. One is to add items to the queue(enqueue) and 
    //other is to remove them(dequeue) 


    private ImmutableQueue(ReversableStack<E> order, ReversableStack<E> reverse) { 
     this.order = order; 
     this.reverse = reverse; 
    } 

    //initially both stacks are empty 
    public ImmutableQueue() { 
     this.order = ReversableStack.emptyStack(); 
     this.reverse = ReversableStack.emptyStack(); 
    } 

    public ImmutableQueue<E> enqueue(E e) { 
     if (null == e) 
      throw new IllegalArgumentException(); 
     return new ImmutableQueue<E>(this.order.push(e), this.reverse); 
    } 

    public ImmutableQueue<E> dequeue() { 
     if (this.isEmpty()) 
      throw new NoSuchElementException(); 
     if (!this.reverse.isEmpty()) { 
      return new ImmutableQueue<E>(this.order, this.reverse.tail); 
     } else { 

      return new ImmutableQueue<E>(ReversableStack.emptyStack(), 
        this.order.getReverseStack().tail); 
     } 
    } 




    private static class ReversableStack<E> { 
     private E head; //top of original stack 
     private ReversableStack<E> tail; //top of reversed stack 
     private int size; 

     //initializing stack parameters 
     private ReversableStack(E obj, ReversableStack<E> tail) { 
      this.head = obj; 
      this.tail = tail; 
      this.size = tail.size + 1; 
     } 

     //returns a new empty stack 
     public static ReversableStack emptyStack() { 
      return new ReversableStack(); 
     } 

     private ReversableStack() { 
      this.head = null; 
      this.tail = null; 
      this.size = 0; 
     } 

     //Reverses the original stack 
     public ReversableStack<E> getReverseStack() { 
      ReversableStack<E> stack = new ReversableStack<E>(); 
      ReversableStack<E> tail = this; 
      while (!tail.isEmpty()) { 
       stack = stack.push(tail.head); 
       tail = tail.tail; 
      } 
      return stack; 
     } 

     public boolean isEmpty() { 
      return this.size == 0; 
     } 

     public ReversableStack<E> push(E obj) { 
      return new ReversableStack<E>(obj, this); 
     } 
    } 

    private ReversableStack<E> order; 

    private ReversableStack<E> reverse; 



    private void normaliseQueue() { 
     this.reverse = this.order.getReverseStack(); 
     this.order = ReversableStack.emptyStack(); 
    } 

    public E peek() { 
     if (this.isEmpty()) 
      throw new NoSuchElementException(); 
     if (this.reverse.isEmpty()) 
      normaliseQueue(); 
     return this.reverse.head; 
    } 

    public boolean isEmpty() { 
     return size() == 0; 
    } 

    //returns the number of items currently in the queue 
    public int size() { 
     return this.order.size + this.reverse.size; 
    } 

    public static void main(String[] args) 
    { 
     ImmutableQueue<Integer> newQueue = new ImmutableQueue<Integer>(); 
     newQueue.enqueue(5); 
     newQueue.enqueue(10); 
     newQueue.enqueue(15); 
     int x = newQueue.size(); 
     //ImmutableQueue<Integer> x = newQueue.dequeue(); 
     System.out.println(x); 

    } 

} 

但是，每當我試圖做一個出列，我得到一個NoSuchElementException。此外，newQueue.size函數也返回0. 我做錯了什麼？ 感謝

Answer 1

你缺少新ImmutableQueue參考..

因爲enqueue()方法返回的ImmutableQueue

public ImmutableQueue<E> enqueue(E e) { 
    if (null == e) 
     throw new IllegalArgumentException(); 
    return new ImmutableQueue<E>(this.order.push(e), this.reverse); 
} 

但一個新的實例在您的主要方法，則需要丟棄對象

public static void main(String[] args) 
{ 
    ImmutableQueue<Integer> newQueue = new ImmutableQueue<Integer>(); 
    newQueue.enqueue(5); 
    newQueue.enqueue(10); 
    newQueue.enqueue(15); 
    int x = newQueue.size(); 
    //ImmutableQueue<Integer> x = newQueue.dequeue(); 
    System.out.println(x); 

} 

將您的電話改爲：

newQueue = newQueue.enqueue(5); 
int x = newQueue.size(); 
System.out.println(x); 

，你會看到的尺寸將會改變