Question

In Java: Initiate empty queue of strings and recreate .isempty, .size, .dequeue, .enqueue methods.

//You may not use the original methods of the stack api to answer. You may not add any more fields to the class.

import java.util.NoSuchElementException;

import edu.princeton.cs.algs4.Stack;

public class StringQueue {
   //You may NOT add any more fields to this class.
   private Stack stack1;
   private Stack stack2;

   /**
   * Initialize an empty queue.
   */
   public StringQueue() {

//TODO
   }

   /**
   * Returns true if this queue is empty.
   *
   * @return {@code true} if this queue is empty; {@code false} otherwise
   */
   public boolean isEmpty() {
       //TODO
   }

   /**
   * Returns the number of items in this queue.
   *
   * @return the number of items in this queue
   */
   public int size() {
       // TODO
   }

   /**
   * Adds the item to this queue.
   *
   * @param item the item to add
   */
   public void enqueue(String item) {
       // TODO
   }

   /**
   * Removes and returns the item on this queue that was least recently added.
   *
   * @return the item on this queue that was least recently added
   * @throws NoSuchElementException if the queue is empty
   */
   public String dequeue() throws NoSuchElementException {
       // TODO
   }
}

Hints:
You will need to store enqueued items on one of the stacks. However, when it comes time to dequeue, those items will be in the wrong order, so use the second stack to reverse the order. Note that once the items are in the second stack, they will come out of the second stack in the correct order and you can still use the first stack to store new items that are enqueued. You should not keep moving the strings back and forth between the two stacks as this will make your solution extremely inefficient. Each string should be inserted into stack1 and most once and into stack2 at most once.
I suggest you start with the very simple sequence: enqueue(“one”), enqueuer(“two”), dequeue(), dequeue(). Of course, the String “one” should come out first followed by the String “two”. Once you have that working, start testing your code with more complex sequences and fixing any use cases you missed in your original attempt at a solution. For example, make sure to at least try the seuquence enqueue(“one”), enqueuer(“two”), dequeue(), enqueue(“three”), dequeue(), dequeue().

Answer 1

//Code for StringQueue using Stacks

//Note: As the Stack is not give, i have implemented it

import java.util.NoSuchElementException;

class Stack
{
String item[] = new String[1000];
int sp;

Stack(){
sp = -1;
}

void push(String itm){
if( isFull() ){
System.out.println("\nStack is Full");
System.exit(0);
}
sp++;
item[sp] = itm;

}

String pop(){
if( isEmpty() ){
System.out.println("\nStack is Empty..");
System.exit(0);
}
String itm = item[sp];
sp--;
return itm;   

}

boolean isEmpty(){
if( sp== -1 )
return true;
return false;
}

boolean isFull(){
if( sp==999)
return true;
return false;

}

int size(){
return( sp+1 );
}

}

public class StringQueue {
//You may NOT add any more fields to this class.
private Stack stack1;
private Stack stack2;

/**
* Initialize an empty queue.
*/
public StringQueue() {
stack1 = new Stack();
stack2 = new Stack();

//TODO
}

/**
* Returns true if this queue is empty.
*
* @return {@code true} if this queue is empty; {@code false} otherwise
*/
public boolean isEmpty() {
//TODO
if( stack1.isEmpty() && stack2.isEmpty() )
return true;

return false;

}

/**
* Returns the number of items in this queue.
*
* @return the number of items in this queue
*/
public int size() {
// TODO
int s1 = stack1.size();
int s2 = stack2.size();

int qsize = s1+2;

return (qsize);
}

/**
* Adds the item to this queue.
*
* @param item the item to add
*/
public void enqueue(String item) {
// TODO
stack1.push(item);
}

/**
* Removes and returns the item on this queue that was least recently added.
*
* @return the item on this queue that was least recently added
* @throws NoSuchElementException if the queue is empty
*/
public String dequeue() throws NoSuchElementException {
// TODO
String itm="";
if( isEmpty() )
{
System.out.println("\nQueue is Empty...");
System.exit(0);
}
if( !stack2.isEmpty() ){
itm = stack2.pop();
return itm;
}

if( !stack1.isEmpty() )
{
while(!stack1.isEmpty()){
itm = stack1.pop();
stack2.push(itm);
}
itm = stack2.pop();
return itm;
  
}
return itm;   
}

public static void main( String args[] ){

StringQueue sq = new StringQueue();
  
sq.enqueue("one");
sq.enqueue("two");

System.out.println(sq.dequeue());
System.out.println(sq.dequeue());

sq.enqueue("one");
sq.enqueue("two");

System.out.println(sq.dequeue());

sq.enqueue("three");
System.out.println(sq.dequeue());
System.out.println(sq.dequeue());

}
}