Java不可变队列

Question

在下面的代码中，我有两个链表liperm和litemp。我想先使用liperm的值初始化litemp，然后添加其他值。但它不起作用，因为它没有初始化它们。你能帮帮：

public class ExamImmutableQueueImpl<E> implements ExamImmutableQueue<E> { 

    LinkedList<E> liperm = new LinkedList<E>(); 
    LinkedList<E> litemp = new LinkedList<E>(liperm); 

    public ExamImmutableQueueImpl(LinkedList li){ 
     System.out.println(li.toString()); 
    } 

    public ExamImmutableQueueImpl(){} 

@Override 
    public ExamImmutableQueue<E> enqueue(E e) { 
     System.out.println(litemp.toString()); 
     litemp.add(e); 

     return new ExamImmutableQueueImpl<>(litemp); 
    } 

    public final void setQueue(E e){ 
     liperm.add(e); 


    } 

    public void getQueue(){ 
     System.out.println(litemp.toString()); 
    } 





} 

的主要方法是：

public static void main(String args[]){ 
    ExamImmutableQueueImpl<Integer> o1 = new ExamImmutableQueueImpl<Integer>(); 
    ExamImmutableQueue<Integer> obj; 
    o1.setQueue(2); 
    o1.setQueue(1); 
    o1.setQueue(2); 
    o1.setQueue(3); 
    obj = o1.enqueue(6); 

接口是：

public interface ExamImmutableQueue<E> { 
public ExamImmutableQueue<E> enqueue(E e);} 

Answer 1

我给你一个建议启动：把这段代码放在一边，开始新鲜。 在设计层面上看起来有什么问题：

• 你不太明白什么是不可变对象。再次阅读。不可变意味着对象状态在施工后永远不会改变。
• 您有几种公共方法，其中来自界面的合同只是“入队”。
• 你倾向于使方法做他们不希望做的事情。只打印的构造函数，setQueue哪些没有设置任何队列。至少仔细选择你的名字。

路线：

• litemp不应该是一个类字段。也许不应该存在。
• 你需要在你的对象内的最后一个字段。尤其是集合liperm
• 在构造函数中构造对象。不做任何事的构造函数可能没有它的位置
• 你知道元素E是否被假定为可变或不可变？这对你可以做的事情有所影响。
• 专注于实施enqueue。为了使事情成为现实，你也可以有Queue作为界面。

注意：一个不可变的队列，似乎就没有任何意义，我（给什么队列理论上是）。在执行之前再次询问这个集合的用法。

Answer 2

这是来自Github的ImmutableQueue的一个实现。
访问https://github.com/guptaAbhishek/ImmutableQueue

package com.liuhao.DataStructures; 

import java.util.NoSuchElementException; 

public class ImmutableQueue<E> { 
    private static class ImmutableStack<E> { 

     private E head; // head is an object of generic type E 
     private ImmutableStack<E> tail; // tail is an ImmutableStack object 
     private int size; // size of the stack 

     /** 
     * Default constructor head to null, tail to null, size to 0 
     * */ 
     private ImmutableStack() { 
      this.head = null; 
      this.tail = null; 
      this.size = 0; 
     } 

     /** 
     * Constructor Overloading (E Object, ImmutableStack object tail) head 
     * is object tail is tail (ImmutableStack object) size = size of the 
     * tail+1 
     * */ 
     private ImmutableStack(E obj, ImmutableStack<E> tail) { 
      this.head = obj; 
      this.tail = tail; 
      this.size = tail.size + 1; 
     } 

     /** 
     * Emptying the stack returning the ImmutableStack 
     * */ 
     public static ImmutableStack emptyStack() { 
      return new ImmutableStack(); 
     } 

     /** 
     * Checking if stack is empty with their size 
     * 
     * @return true of false if Stack is empty or not 
     * */ 
     public boolean isEmpty() { 
      return this.size == 0; 
     } 

     /** 
     * Push into the stack 
     * 
     * @param E 
     *   object 
     * @return ImmutableStack with object 
     * */ 
     public ImmutableStack<E> push(E obj) { 
      return new ImmutableStack<E>(obj, this); 
     } 

     /** 
     * Take stack object and push the head of the tail stack to the stack do 
     * this until the stack is empty 
     * 
     * @return reverse stack 
     * */ 
     public ImmutableStack<E> toReverseStack() { 
      ImmutableStack<E> stack = new ImmutableStack<E>(); 
      ImmutableStack<E> tail = this; 
      while (!tail.isEmpty()) { 
       stack = stack.push(tail.head); 
       tail = tail.tail; 
      } 
      return stack; 
     } 
    } 

    /** 
    * Two stack for enqueue and dequeue the element from the queue order for 
    * enqueue reverse for dequeue 
    * 
    * */ 
    private ImmutableStack<E> order; 
    private ImmutableStack<E> reverse; 

    /** 
    * Default constructor ImmutableQueue two empty stacks 
    * 
    * */ 
    public ImmutableQueue() { 
     this.order = ImmutableStack.emptyStack(); 
     this.reverse = ImmutableStack.emptyStack(); 
    } 

    /** 
    * Constructor overloading Using two immutable stack order and reverse 
    * 
    * */ 
    public ImmutableQueue(ImmutableStack<E> order, ImmutableStack<E> reverse) { 
     this.order = order; 
     this.reverse = reverse; 
    } 

    /** 
    * Balancing the Queue reverse the order stack and assign it to reverse 
    * stack and make order stack empty 
    * */ 
    private void balanceQueue() { 
     this.reverse = this.order.toReverseStack(); 
     this.order = ImmutableStack.emptyStack(); 
    } 

    /** 
    * Enqueue Object if object is null throw IllegalArgumentException 
    * 
    * @return ImmutableQueue with object 
    * */ 
    public ImmutableQueue<E> enqueue(E object) { 
     if (object == null) 
      throw new IllegalArgumentException(); 
     return new ImmutableQueue<E>(this.order.push(object), this.reverse); 
    } 

    /** 
    * Dequeue from the queue if Queue is empty then throw 
    * NoSuchElementException 
    * 
    * if Reverse Stack is not empty then return Immutable queue with reverse 
    * stack's tail object 
    * 
    * else reverse the Order ImmutableStack and take the tail of this and clean 
    * the order ImmutableStack 
    * 
    * @return ImmutableQueue 
    * */ 
    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>(ImmutableStack.emptyStack(), this.order.toReverseStack().tail); 
     } 
    } 

    /** 
    * Getting the peek of the queue if Object is empty throw and Exception 
    * NoSuchElementException. if reverse stack is Empty balanceQueue. 
    * 
    * @return head of the reverse stack 
    * */ 
    public E peek() { 
     if (this.isEmpty()) 
      throw new NoSuchElementException(); 
     if (this.reverse.isEmpty()) 
      balanceQueue(); 
     return this.reverse.head; 
    } 

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

    public int size() { 
     return this.order.size + this.reverse.size; 
    } 

    public double percentage(double x) { 
     double value = 0; 
     if (!this.isEmpty()) { 
      value = size() * x/100; 
     } 
     return value; 
    } 
} 

Answer 3

以下解决方案已经从GitHub和完整的解决方案其随时间复杂度证明可以在 GitHub看到和维韦克忙拉创建。

不可变队列算法可以更好地理解链表，非常正确的方法。

一个单独的链接列表可以像一个不可变的队列一样工作，这样每当只执行一个排队时，只有新的前后对象将被修改，而前一个对象仍然会代表前一个队列。因此不需要的副本是没做。

也可以这样说，如果先前的对象已排队不止一次，我们就没有其他选择了，但要复制整个队列并创建一个前后指向前的新对象（第一个）元素和后指向最后一个。

使用链表的完整代码可以被看作是::

* This has been released under GPL v3 Licence by Vivek Mangla 2014. 
* For More Information go to::  http://www.gnu.org/licenses/ 
* AlgoRithM:::::: 
* 
* According to the Immutable Queue Concept****** 
* 
* If suppose there is an object q representing an Immutable Queue 
*    Now if we perform an enQueue() operation then, 
*        this object will STILL Represent The Previous Queue 
*        and a new Object q1 of Immutable Queue will be representing 
*         new Queue with 1 extra element then previous one. 
*      *************similar argument for dequeue()operation ************* 
* 
*  *******It MEANS THAT THERE IS NO BOUNDATION ON MEMORY FOR an OBJECT.. 
* 
*    i.e. it is NOT NECESSARY that a new Object MUST HAVE A 
*      WHOLE NEW MEMORY SPACE Of New Queue it is representing.******** 
* 
*BUT If we are EnQueing a value in previous persistent Object MORE_THAN_ONCE than we have to allocate a Whole new Memory Space 
* 
* 
* Using the Above CONCEPT ... 
* 
* I have created an algorithm to make a Linked List to work like an Immutablequeue. 
* 
* In this Algorithm, 
*  A new Object may be using Same Memory Space as Previous One's 
*   but with certain RESTRICTIONS so that....<<<<.....It is NOT going to CONTRADICT ABOVE CONCEPTS...>>>>> 
*  And Those <Restrictions> are:: 
*          <1>..<Current Queue Object's front and rear are not to be modified > 
*          <2>..<Current Queue Object's SIZE is not to be Modified> 
*  And Hence <Modifications> will be done only on:: 
*          <1>..<Previous Linked List node's next value ..(If necessary)> 
*          <2>..<new Linked List node's data value> 
*          <3>..<new Queue Object's rear,front and SIZE value> 
*          <4>..<In worst case copy whole Queue of Current Object for new Object > 
* 
* <<WHERE rear is a reference to last element of Linked_List and front is First element of Linked_List>> 
* 
* <<...NOTE::!!!!THE CURRENT QUEUE OBJECT'S Variable Values Are Not Modified At ALL...!!!!>> 
* 
**************************<********************************************************************************>************* 
*/ 








import java.util.NoSuchElementException; 

public class IQ1<E>{ 


    /*************************<***********************************************************************>*********************** 
    * The Object of this class is having 3 Variables... 
    * 
    * 1.> front :: for keeping track of head of this Object.. 
    * 2.> rear :: for keeping track of end of this Object.. 
    * 3.> SIZE :: for keeping track of number of elements of this Object.. 
    *********************<*******************************************************************************>******************* 
    */ 


    List front=null,rear=null; 
    int SIZE=0; 
    IQ1<E> IQ1=null; 
    static List list=null,node=null,p=null,p1=null; 

    public IQ1(){} 

    /************************************ 
    ******************************************************************** 
    * enqueue(E e) operation 
    ******************************************************************** 
    * 
    * if(parameter passed is null){ 
    *        THROW ILLEGAL_ARGUMENT_EXCEPTION ; 
    *        } 
    * 
    * else if(it is not null){ 
    * 
    *       Create a new List Node.. List list=new List(); 
    *       Now data part of this list contains value passed in parameter ; 
    *       Create a new Immutable Queue Object..IQ1<E> IQ1=new IQ1<E> ; 
    *       Now , 
    *       if((current Object's front is null)OR 
    *         (it's front is just one step ahead of it's rear i.e. 
    *  <this object has been created by removing last element from another object whose rear was in somewhere middle of list>)){ 
    *           new Object's front is equal to new List Node formed ; 
    *           new Object's rear is equal to new List Node Formed ; 
    *                } 
    * 
    *       else if(this object's rear is referring to last element){ 
    *          new Object's front is equal to current Object's front ; 
    *          new Object's rear is equal to new List Node Formed ; 
    *        } 
    *       else{ 
    *       << Create a Duplicate Queue of Current Object and adjust new Object's rear and front references>> 
    *       } 
    *       
    *       new Object's SIZE is 1 More than current Object's SIZE ; 
    *       
    *       } 
    * 
    * return null; 
    *****************************************<******************************************>************************************      
    */ 


    /************************<****************************************************************>************ 
    * <<TIME_COMPLEXITY>> 
    *    <1.>..<Best Case::> O(1) 
    *    <2.>..<Worst Case::> Less Than |_O(n/2)_|<< WHERE, n IS no. of elements enqueued>> 
    * <<****FOR CALCULATION OF TIME COMPLEXITY SEE END OF THIS PROGRAMM****>> 
    ***************************<***********************************************************>**************** 
    */ 



    @SuppressWarnings("unchecked") 
    public IQ1<E> enqueue(E e){ 

     if(e==null)throw new IllegalArgumentException();/** <<YOU_MAY_HANDLE_THIS_EXCEPTION_ON_YOUR_OWN>> **/ 

      list=new List(); 
      list.object=e; 
      IQ1=new IQ1<E>(); 
      if((front==null)||(rear.next==front)){IQ1.rear=IQ1.front=list;} 
      else if (rear.next==null){ 
       IQ1.front=front; 
       IQ1.rear=list; 
       rear.next=list; 
      } 
      else{ 
       p=front;p1=null; 
       node=new List(); 
       node.object=p.object;IQ1.front=node; 
       p1=node;p=p.next; 
       while(p!=rear.next){ 
        List node1=new List(); 
        node1.object=p.object; 
        p1.next=node;p1=node;p=p.next; 
       } 
       p1.next=list; 
       IQ1.rear=list; 
      } 

      IQ1.SIZE=SIZE+1; 

      return IQ1; 

    } 


    /**************************<*************************************************************************************>******** 
    * ********************************* 
    * dequeue() Operation 
    * ********************************* 
    * 
    * Now Dequeue operation is little bit TRICKY.. 
    * Because We have to remove first element BUT CURRENT OBJECT's Bounds MUST NOT BE CHANGED 
    * SO, 
    * 
    * if(current's front is null i.e. EMPTY OR..... if it's rear.next is referring to it's front i.e. 
    *         previous object was containing single item and then a dequeue operation was performed 
    *         on it and allocated to current object){ 
    *                   THROW EXCEPTION ; 
    *                  } 
    * 
    *          Create a new Immutable Queue Object; 
    *          it's front will refer to current's front.next; 
    *          it's rear will refer to current's rear; 
    *          it's SIZE will be 1 LESS than current's SIZE; 
    *          return this new Object; 
    * 
    * *****************************<******************************************************************************>*********** 
    */ 

    /***********************<*************************************************************************************> 
    * <<Time_Complexity>>.. 
    *     <O(1)...in ALL CASES> 
    ************************<************************************************************************************>* 
    */ 


    @SuppressWarnings("unchecked") 
    public IQ1<E> dequeue(){ 

     if((front==null)||(rear.next==front)){ 
      rear=null;front=null; 
      throw new NoSuchElementException(); 
      /** <<YOU_MAY_HANDLE_THIS_EXCEPTION_ON_YOUR_OWN>> **/ 
     } 

     IQ1=new IQ1<E>(); 
     IQ1.front=front.next; 
     IQ1.rear=rear; 
     IQ1.SIZE=SIZE-1; 

     return IQ1; 

    } 


    /******************************<********************************************************************************>********** 
    *********************** 
    * peek() Operation 
    *********************** 
    * 
    * if(current's front is null i.e. EMPTY OR..... if it's rear is refering to it's front i.e. 
    *         previous object was containing single item and then a dequeue operation was performed 
    *         on it and allocated to current object){ 
    *                   THROW EXCEPTION ; 
    *                  } 
    * 
    *          return current Object's front.object ; 
    * 
    *****************************<**********************************************************************************>******** 
    */ 

    /** 
    * <<Time_Complexity>>.. 
    *     <O(1)...in ALL CASES> 
    ****************************<*************************************************************************************> 
    */ 


    @SuppressWarnings("unchecked") 
    public E peek(){ 
     if((front==null)||(rear.next==front))throw new NoSuchElementException();/** <<YOU_MAY_HANDLE_THIS_EXCEPTION_ON_YOUR_OWN>> **/ 

     return (E)front.object; 


    } 


    /**************************<**********************************************************************************>*********** 
     *<************************ 
     * size() Operation 
     *************************> 
     *             return SIZE ; 
     * 
     *************************<**********************************************************************************>************ 
     * 
     */ 

    /*******************************************<****************************************>************************************* 
    * 
    * <<Time_Complexity>>.. 
    *     <O(1)...in ALL CASES> 
    *******************************************<******************************************>*********************************** 
    */ 

    public int size(){ 

      return SIZE; 


    } 


} 

/*****************************<**************************************************************************************>**** 
**************************************************** 
* Linked List Has Been Used To Store Pushed Element. 
* class List is used to declare Linked list Node. 
* This class is also a Generic Class to support Generic data Types. 
**************************************************** 
* 
* It has 2 variables:: 
*  1.> A Generic Reference variable E object; 
*  2.> A next reference which refers to next node List next=null; 
****************************<**************************************************************************************>***** 
*/ 


class List<E>{ 


    E object;/**<<Node Data Part Can Contain Any Object>>**/ 
    List next=null;/***<<Reference to next Node>>**/ 
} 

希望这会有所帮助。