Immutable Queue in Java using an Immutable Stack

Question

I am new to this Immutability concept and I have some coding experience in JAVA. Recently as a part of internship program, they gave me a 5-day task, which was to implement Immutable Queue. After some research I came with a solution which was given below. Can some review the code.

[Technically your are not helping me in my internship process as it was over a while ago and I didn't got selected for the next round. So as per the rules of it there is no restriction on publishing the code after the process completion.]

ImmutableQueue.java

import java.util.NoSuchElementException;
public class ImmutableQueue<E> {
 private final class ImmutableEmptyQueue extends ImmutableQueue<E>{ //sub class for Empty queue
 public ImmutableEmptyQueue(){ //Constructor for the ImmutableEmptyQueue
 super(null, null);
 }
 public ImmutableQueue<E> enqueue(E e){ //Enqueue operation on EmptyQueue
 if(e==null){
 throw new IllegalArgumentException(); //if no argument passed throws exception
 }
 return new ImmutableQueue<E>(forward , backward.push(e));
 }
 public ImmutableQueue<E> dequeue(){ //Dequeue operation on EmptyQueue
 throw new NoSuchElementException(); //throws exception
 }
 public E peek(){ //returns the first object
 if(this.IsEmpty()){ //if empty throws exception
 throw new IllegalArgumentException();
 }
 return null;
 }
 public int size(){ //return size zero
 return 0;
 }
 public boolean IsEmpty(){ //Check if empty or not
 return true;
 }
 }
 private final ImmutableStack<E> forward; //forward queue
 private final ImmutableStack<E> backward; //backward queue
 private final ImmutableEmptyQueue empty = new ImmutableEmptyQueue();//ImmutableEmptyQueue object
 public final ImmutableQueue<E> Empty = empty; //ImmutableQueue object which is empty
 public ImmutableQueue(ImmutableStack<E> forward, ImmutableStack<E> backward){//Constructor of the ImmutableQueue<E> class
 this.forward = forward;
 this.backward = backward;
 }
 public ImmutableQueue<E> enqueue(E e){ //Enqueue operation of the Immutable Queue
 if(e==null){ //if no valid argumnet passed throws error
 throw new IllegalArgumentException();
 }
 return new ImmutableQueue<E>(forward , backward.push(e)); //return new Queue
 }
 public ImmutableQueue<E> dequeue(){ //Dequeue Operation of the Immutable Queue
 if(this.IsEmpty()){
 throw new NoSuchElementException(); //if queue is empty throw error
 }
 ImmutableStack<E> f = forward.pop(); //top object removed from the forward stack
 if(!f.IsEmpty()){
 return new ImmutableQueue<E>(f , backward); //new ImmutableQueue formed
 }
 else if(backward.IsEmpty()){
 return new ImmutableEmptyQueue(); //new ImmutableEmptyQueue
 }
 else{
 return new ImmutableQueue<E>(backward.Reverse(),(new ImmutableStack<E>(null,null)).Empty);//new ImmutableQueue with backward stack empty
 }
 }
 private boolean IsEmpty() {
 return (forward.IsEmpty() && backward.IsEmpty()); //Checks Whether the queue is empty or not
 }
 public E peek(){ 
 return forward.peek(); //removes the first object from the ImmutableQueue
 }
 public int size(){
 return (forward.Size()+backward.Size()); //return the size of the ImmutableQueue
 }
}
class ImmutableStack<E>{
 private final class ImmutableEmptyStack extends ImmutableStack<E> { //Immutable Empty Stack class 
 public ImmutableEmptyStack() { //Constructor for Immutable Empty Stack
 super(null, null); 
 }
 public ImmutableStack<E> pop(){ //Pop Operation
 if(this.IsEmpty()){
 throw new NoSuchElementException();
 }
 return null;
 }
 public ImmutableStack<E> push(E e){ //Push Operation
 if(e==null){
 throw new IllegalArgumentException();
 }
 return new ImmutableStack<E>(e,this);
 }
 public E peek(){ //Peek Operation
 if(this.IsEmpty()){
 throw new NoSuchElementException();
 }
 return null;
 }
 public boolean IsEmpty(){ //Checks whether any element present in the EmptyStack
 return true;
 }
 public int Size(){ //Size of the EmptyStack
 return 0;
 }
 }
 private final E head; //head of the stack
 private final ImmutableStack<E> tail; //tail or the body of the stack is implemented as a stack
 private final ImmutableEmptyStack empty = new ImmutableEmptyStack();//Creating object of the ImmutableEmptyStack
 public final ImmutableStack<E> Empty = empty; //Creating an EmptyImmutableStack
 public ImmutableStack(E head, ImmutableStack<E> tail){ //Constructor to build the ImmutableStack with two arguments 
 this.head = head;
 this.tail = tail != null ? tail : new ImmutableEmptyStack(); //if no tail is present add the ImmutableEmptyStack as the Tail
 }
 public ImmutableStack<E> pop(){ //return the tail of the stack
 if(this.IsEmpty()){
 throw new NoSuchElementException(); //if no element exists throw exception
 }
 return this.tail;
 }
 public ImmutableStack<E> push(E e){ //Push Operation of the Stack 
 if(e==null){
 throw new IllegalArgumentException(); 
 }
 return new ImmutableStack<E>(e , this);
 }
 public E peek(){ //return the head of the stack
 if(this.IsEmpty()){ //if no element exists throw exception
 throw new NoSuchElementException();
 }
 return this.head;
 }
 public boolean IsEmpty(){ //Check if any element exists or not in the Stack
 return (head==null && tail==null);
 }
 public int Size(){ //Return the Size of the Stack
 if(IsEmpty())
 return 0;
 else
 return (1+tail.Size());
 }
 public ImmutableStack<E> Reverse(){ //reverse the stack and point it to the same
 ImmutableStack<E> reversedstack = new ImmutableEmptyStack(); //resultant reverse Immutable Stack initialization
 ImmutableStack<E> temp = this; //temporary Immutable Stack
 while(!(temp instanceof ImmutableStack.ImmutableEmptyStack)){ //Adding the non empty instances of temp into reversedstack
 reversedstack = reversedstack.push(temp.peek());
 temp = temp.pop();
 }
 return reversedstack;
 }
}

Answer 1

1. This code assumes that all empty stacks are instances of ImmutableEmptyStack, but the public constructor allows code to create a new ImmutableStack that happens to be empty, so it would be better to use temp.IsEmpty()

   while(!(temp instanceof ImmutableStack.ImmutableEmptyStack)){
   

2. It would be better to make the empty values static members, so you'd need to make the nested classes static too. This will save memory and also prevent code changes from accessing the surrounding ImmutableQueue / ImmutableStack fields. It would be even better to put the empty classes each in their own file, i.e. not a nested class.

   private static final class ImmutableEmptyQueue extends ImmutableQueue<E>{
   private static final ImmutableEmptyQueue empty = new ImmutableEmptyQueue();
   private final class ImmutableEmptyStack extends ImmutableStack<E> {
   private static final ImmutableEmptyStack empty = new ImmutableEmptyStack();
   

3. Java coding conventions say to start method names with a lower case letter, so isEmpty() instead of IsEmpty().

4. If you've made the empty values static, then you can even make the constructors private: then to use this class you always start with e.g. ImmutableQueue.empty and build it up using calls to enqueue(value).

Answer 2

First, let's get some general remarks out of the way:

• Stop writing useless comments. Every single one of your comments was superfluous clutter that added no insight to the code.
• Respect Java naming conventions.

I'll review ImmutableStack first. There are two cases: the empty stack and non-empty stacks. I see that you have made an attempt to implement the special case for the empty stack. However, you will have a better time if you reverse the inheritance. Think of it this way: the public should be able to make an empty stack, but all non-empty stacks should only be create using .push(). Furthermore, the empty stack is simpler: it has no "next" pointer.

import java.util.NoSuchElementException;
class ImmutableStack<E> {
 private class NonEmpty extends ImmutableStack<E> {
 private final E head;
 private final ImmutableStack<E> tail;
 private final int size;
 private NonEmpty(E head, ImmutableStack<E> tail) {
 this.head = head;
 this.tail = tail;
 this.size = 1 + tail.size();
 }
 @Override
 public ImmutableStack<E> pop() {
 return this.tail;
 }
 @Override
 public E peek() {
 return this.head;
 }
 @Override
 public boolean isEmpty() {
 return false;
 }
 @Override
 public int size() {
 return this.size;
 }
 }
 public ImmutableStack<E> pop() {
 throw new NoSuchElementException();
 }
 public ImmutableStack<E> push(E e) {
 if (e == null) {
 throw new IllegalArgumentException(); 
 }
 return new NonEmpty(e, this);
 }
 public E peek() {
 throw new NoSuchElementException();
 }
 public boolean isEmpty() {
 return true;
 }
 public int size() {
 return 0;
 }
}

A stack does not traditionally offer a reverse() operation, because the data structure is not designed to do it efficiently. If you need to reverse a stack, you can do so using its public methods, so I recommend that you leave this code outside of the stack class.

public static <E> ImmutableStack<E> reverse(ImmutableStack<E> stack) {
 ImmutableStack<E> rev = new ImmutableStack<E>();
 for (ImmutableStack<E> fwd = stack; !fwd.isEmpty(); fwd = fwd.pop()) {
 rev = rev.push(fwd.peek());
 }
 return rev;
}

Implementing the queue in terms of two stacks does not make much sense. You would be much better off with an independent implementation.

• Harold L: Inverting the inheritance is really elegant. This is a really traditional way to implement an immutable queue. The benefit is that you get O(1) enqueue and O(1) amortized dequeue operations.