java - 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 上看到具有时间复杂性证明的完整解决方案，由 Vivek Mangla 创建。

Immutable Queue Algorithm 可以更好地理解为 Linked List ，非常正确的方法。

可以使单链表充当不可变队列，这样每当执行入队时，只会修改前后的新对象，而前一个对象仍将代表前一个队列。因此不会进行不必要的复制。

也可以说，如果前一个对象多次入队，那么我们别无选择，只能复制整个队列并创建一个新对象，其前后指向前（第一个）元素，后指向最后一个元素。

使用链表的完整代码可以看成：

 * 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>>**/
}

希望这会有所帮助。