Java contiguous queue
In the code below, I have two linked lists liperm and litemp. I want to initialize litemp with liperm values first and then add other values. But it doesn't work as it doesn't initialize them. Could you help me:
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());
}
}
Basic method:
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);
Interface:
public interface ExamImmutableQueue<E> {
public ExamImmutableQueue<E> enqueue(E e);}
0
source to share
3 answers
I'll start by giving you advice: put this code aside and start fresh. Something is wrong at the design level:
- You don't quite understand what is an immutable object. Read it again. Immutable means that the state of the object never changes after construction.
- You have several public methods in which the interface contract is only "enqueue".
- You tend to do methods of doing things that they shouldn't. a constructor that only prints
setQueue
, that doesn't set up any queue. At the very least, choose your names carefully.
Directions:
-
litemp
should not be a class field. Perhaps it shouldn't be. - you need trailing margins inside your object. Especially the collection
liperm
- Build objects in constructors. A constructor that does nothing may have no place.
- Did you know that an element
E
is considered mutable or immutable? This can affect what you can do. - Focus on implementation
enqueue
. You can also use Queue as an interface to create the things you want .
Note. An optional queue seems pointless to me (given that it exists in theory ). Ask again what is the use of this collection before going into the implementation.
+9
source to share
This is the ImmutableQueue tool from Github.
Visit 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 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;
}
}
+1
source to share
The following solution was taken from GitHub and is a complete solution with time complexity. Proof can be seen on GitHub and created by Vivek Mangla.
The immutable queue algorithm can be better understood in terms of Linked List, very correct approach.
A single linked list can be made to act like an immutable queue, so that whenever a queue is executed, only the new front and back object needs to be changed, whereas the previous object will still represent the previous queue. And therefore, an unnecessary copy is not made.
It can also be stated that if the previous object is enqueued more than once than we have no other option, but copy that whole queue and create a new object with a front and back pointer to the front (first) element and a back pointing to the last one.
The complete code using linked list can be seen as:
* 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
* but with certain RESTRICTIONS so that....<<<<.....It is NOT going to CONTRADICT ABOVE CONCEPTS...>>>>>
* And Those <Restrictions> are::
* <1>..<Current Queue Object front and rear are not to be modified >
* <2>..<Current Queue Object SIZE is not to be Modified>
* And Hence <Modifications> will be done only on::
* <1>..<Previous Linked List node next value ..(If necessary)>
* <2>..<new Linked List node data value>
* <3>..<new Queue Object 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 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 front is null)OR
* (it front is just one step ahead of it 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 front is equal to new List Node formed ;
* new Object rear is equal to new List Node Formed ;
* }
*
* else if(this object rear is referring to last element){
* new Object front is equal to current Object front ;
* new Object rear is equal to new List Node Formed ;
* }
* else{
* << Create a Duplicate Queue of Current Object and adjust new Object rear and front references>>
* }
*
* new Object SIZE is 1 More than current Object 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 Bounds MUST NOT BE CHANGED
* SO,
*
* if(current front is null i.e. EMPTY OR..... if it rear.next is referring to it 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 front will refer to current front.next;
* it rear will refer to current rear;
* it SIZE will be 1 LESS than current 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 front is null i.e. EMPTY OR..... if it rear is refering to it 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 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>>**/
}
Hope this helps.
0
source to share