在下面的代码中,我有两个链表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);}
我将首先给您一个建议:把这些代码放在一边,重新开始。在设计层面上似乎有什么问题:
- 你不太明白什么是不可变的对象。再读一遍。不可变意味着对象状态在构造后永远不会改变
- 您有几个公共方法,其中接口中的约定仅为"入队"
- 你倾向于让方法做他们不应该做的事情。只打印的构造函数,不设置任何队列的
setQueue
。至少要仔细选择你的名字
方向:
litemp
不应是类字段。也许不应该存在- 您需要在对象中设置最终字段。尤其是
liperm
系列 - 在构造函数中构造对象。什么都不做的构造函数可能没有它的位置
- 你知道元素
E
是可变的还是不可变的吗?这会影响你的能力 - 重点落实
enqueue
。为了使事情变得更好,您还可以将Queue作为接口
注意:一个不可变的队列对我来说似乎没有意义(考虑到队列理论上是什么)。在转入实现之前,再次询问此集合的用途。
这是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;
}
}
以下解决方案取自GitHub,具有时间复杂性证明的完整解决方案可以在GitHub,由Vivek Mangla创建。
不可变队列算法可以更好地理解链表,这是一种非常正确的方法。
单链表可以像一个不可变的队列一样工作,这样每当执行队列时,只有前面和后面的新对象才会被修改,而前面的对象仍然代表前面的队列。因此不会进行不必要的复制。
也可以说,如果前一个对象被排队不止一次,我们就别无选择了,只能复制整个队列并创建一个新对象,前后都指向front(First)元素,后都指向最后一个元素。
使用链表的完整代码可以看作::
* 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>>**/
}
希望这会有所帮助。