1. The array-based implementation of the ADT queue on page 422 assumes a maximum

Question

1. The array-based implementation of the ADT queue on page 422 assumes a maximum queue size of 50 items. At first, create a NetBeans project which implements all of the code given by the textbook as is. Meaning that your project should include the QueueArrayBased class (page 422), QueueInterface (page 415) and QueueException class (page 415). Once you have implemented these classes and the interface, write a main class to test this QueueArrayBased class. After you are positive that the QueueArrayBased class works as intended, modify this implementation so that when the queue becomes full, the size of the array is doubled. You will need to add additional tests to your main class to verify that your modified QueueArrayBased class operates correctly with 50 or more items. 2. Create a NetBeans project which implements the palindrome-recognition algorithm described in the section “Simple Applications of the ADT Queue” (page 414). You do not have to reinvent the wheel with this exercise! Your solution should use the Stack and Queue ADT’s you have already written for Projects 3 and 4.

Explanation / Answer

isPalindrome.java
import java.util.Scanner;

public class isPalindrome {

    public static void main(String[] args){
       Scanner scan = new Scanner(System.in);
       System.out.println("Word to check: ");

       String userInput = scan.nextLine();
       userInput = userInput.toUpperCase();
       System.out.print(isPal(userInput)+" ");

   }

   public static boolean isPal(String str){
       QueueArrayBased aQueue = new QueueArrayBased();
       StackArrayBased aStack = new StackArrayBased();

       for (int i = 0; i < str.length(); i++){
           aQueue.enqueue(str.charAt(i));
           aStack.push(str.charAt(i));
       }

       //start to compare

       while(!aQueue.isEmpty()){
           if(aQueue.dequeue() != aStack.pop()){
               return false;
           }
       }

       //finished w/ empty queue (and empty stack)

       return true;
   }

}

QueueArrayBased.java
public class QueueArrayBased implements QueueInterface
{
final int MAX_QUEUE = 50; // maximum size of queue
private Object items[];
private int front, back, numItems;

public QueueArrayBased()
{
   items = new Object[MAX_QUEUE];
   front = 0;
   back = MAX_QUEUE -1;
   numItems = 0;
} // end default constructor

// queue operations:
public boolean isEmpty()
{
    return numItems == 0;
} // end isEmpty

public boolean isFull()
{
    return numItems == MAX_QUEUE;
} // end isFull

public void enqueue(Object newItem) throws QueueException
{
    if (!isFull()) {
      back = (back+1)%MAX_QUEUE;
      items[back] = newItem;
      ++numItems;
    } else {
      throw new QueueException("QueueException on enqueue: Queue full");
    } // end if
} // end enqueue

public Object dequeue() throws QueueException
{
    if (!isEmpty()) {
      // queue is not empty; remove front
      Object queueFront = items[front];
      front = (front+1)%MAX_QUEUE;
      --numItems;
      return queueFront;
    } else {
      throw new QueueException("QueueException on dequeue: Queue empty");
    }   // end if
} // end dequeue

public void dequeueAll()
{
    items = new Object[MAX_QUEUE];
    front = 0;
    back = MAX_QUEUE -1;
    numItems = 0;
} // end dequeueAll

public Object peek() throws QueueException
{
    if (!isEmpty()) {
      // queue is not empty; retrieve front
      return items[front];
    } else {
      throw new QueueException("Queue exception on peek: Queue empty");
    } // end if
} // end peek

public String toString()
{

   StringBuilder s = new StringBuilder();
   for(int i = 0; i < numItems; i++){
       s.append(items[front+i]+" ");
   }
   return s.toString();
} // end of toString

} // end QueueArrayBased

QueueInterface.java
public interface QueueInterface
{
public boolean isEmpty();
// Determines whether a queue is empty.
// Precondition: None.
// Postcondition: Returns true if the queue is empty;
// otherwise returns false.

public void enqueue(Object newItem) throws QueueException;
// Adds an item at the back of a queue.
// Precondition: newItem is the item to be inserted.
// Postcondition: If the operation was successful, newItem
// is at the back of the queue. Some implementations may
// throw QueueException if newItem cannot be added to the
// queue.

public Object dequeue() throws QueueException;
// Retrieves and removes the front of a queue.
// Precondition: None.
// Postcondition: If the queue is not empty, the item
// that was added to the queue earliest is returned and
// the item is removed. If the queue is empty, the
// operation is impossible and QueueException is thrown.

public void dequeueAll();
// Removes all items of a queue.
// Precondition: None.
// Postcondition: The queue is empty.

public Object peek() throws QueueException;
// Retrieves the item at the front of a queue.
// Precondition: None.
// Postcondition: If the queue is not empty, the item
// that was added to the queue earliest is returned.
// If the queue is empty, the operation is impossible
// and QueueException is thrown.

public String toString();
// Returns the string representation of the object

} // end QueueInterface

QueueException.java
public class QueueException extends RuntimeException
{
public QueueException(String s) {
    super(s);
} // end constructor

private final static long serialVersionUID = 2006L;
} // end QueueException

StackArrayBased.java
import ListReferenceBased.*;

public class StackArrayBased implements StackInterface {

   final int MAX_STACK = 50;
   private Object items[];
   private int top, numItems; //index for stack top

   public StackArrayBased(){
       items = new Object[MAX_STACK];
       top = -1;
       numItems = 0;
   }

   public boolean isEmpty(){
       return (top <0);
   }

   public boolean isFull(){
       return (top == MAX_STACK-1);
   }

   public void push(Object newItem) throws QueueException{
       if(!isFull()){ items[++top] = newItem; numItems++;}
       else{
           throw new QueueException("StackException on push: Stack full");
       }
   }

   public Object pop() throws QueueException{
       if(!isEmpty()){
           numItems--;
           return items[top--];
       }
       else {
           throw new QueueException("StackException on pop: Stack empty");
       }
   }

   public void popAll(){
       items = new Object[MAX_STACK];
       top = -1;
       numItems--;
   }

   public Object peek() throws QueueException{
       if(!isEmpty()) return items[top];
       else{
           throw new QueueException("StackException on peek: Stack Empty");
       }
   }

   public String toString()
   {

   StringBuilder s = new StringBuilder();
   for(int i = 0; i < numItems; i++){
       s.append(items[top+i]+" ");
   }
   return s.toString();
    } // end of toString

}

StackInterface.java
public interface StackInterface{

   public boolean isEmpty();
   public void push(Object newItem);
   public Object pop();
   public void popAll();
   public Object peek();

}

sample output
Word to check
madam
true

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.