Question
Linkedqueue: interface QueueInterface { public void enqueue(Object item); // Effect: Adds item to the rear of this queue. // Precondition: This queue is not full.
Linkedqueue:
interface QueueInterface
{
public void enqueue(Object item);
// Effect: Adds item to the rear of this queue.
// Precondition: This queue is not full.
// Postcondition: item is at the rear of this queue.
public Object dequeue();
// Effect: Removes front element from this queue and returns it.
// Precondition: This queue is not empty.
// Postconditions: Front element has been removed from this queue.
// Return value = (the removed element)
public boolean isEmpty();
// Effect: Determines whether this queue is empty.
// Postcondition: Return value = (this queue is empty)
public boolean isFull();
// Effect: Determines whether this queue is full.
// Postcondition: Return value = (queue is full)
}
class LinkedQueue implements QueueInterface
{
private class QueueNode
// Used to hold references to queue nodes for the linked queue implementation
{
private Object info;
private QueueNode link;
}
private QueueNode front; // reference to the front of this queue
private QueueNode rear; // reference to the rear of this queue
public LinkedQueue()
// Constructor
{
front = null;
rear = null;
}
public void enqueue(Object item)
// Adds item to the rear of this queue.
{
QueueNode newNode = new QueueNode();
newNode.info = item;
newNode.link = null;
if (rear == null)
front = newNode;
else
rear.link = newNode;
rear = newNode;
}
public Object dequeue()
// Removes front element from this queue and returns it.
{
Object item;
item = front.info;
front = front.link;
if (front == null)
rear = null;
return item;
}
public boolean isEmpty()
// Determines whether this queue is empty.
{
if (front == null)
return true;
else
return false;
}
public boolean isFull()
// Determines whether this queue is full.
{
return false;
}
}
ArrayStack:
interface StackInterface
{
public void push(Object item) throws StackOverflowException;
// Effect: Adds item to the top of this stack.
// Postcondition: If (this stack is full)
// an unchecked exception that communicates
// 'push on stack full' is thrown
// else
// item is at the top of this stack.
public void pop() throws StackUnderflowException;
// Effect: Removes top item from this stack
// Postconditions: If (this stack is empty)
// an unchecked exception that communicates
// 'pop on stack empty' is thrown
// else
// top element has been removed from this stack.
public Object top() throws StackUnderflowException;
// Effect: Returns a reference to the element on top of this stack
// Postconditions: If (this stack is empty)
// an unchecked exception that communicates
// 'top on stack empty' is thrown
// else
// return value = (top element of this stack).
public boolean isEmpty();
// Effect: Determines whether this stack is empty.
// Postcondition: Return value = (this stack is empty)
public boolean isFull();
// Effect: Determines whether this stack is full.
// Postcondition: Return value = (stack is full)
}
class StackOverflowException extends RuntimeException
{
public StackOverflowException()
{
}
public StackOverflowException(String message)
{
super(message);
}
}
class StackUnderflowException extends RuntimeException
{
public StackUnderflowException()
{
}
public StackUnderflowException(String message)
{
super(message);
}
}
class ArrayStack implements StackInterface
{
private Object[] stack; // Array that holds stack elements
private int topIndex = -1; // index of top element in stack
// Constructors
public ArrayStack()
{
stack = new Object[100];
}
public ArrayStack(int maxSize)
{
stack = new Object[maxSize];
}
public void push(Object item)
// Adds an element to the top of this stack
{
if (!isFull())
{
topIndex++;
stack[topIndex] = item;
}
else
throw new StackOverflowException("Push attempted on a full stack.");
}
public void pop()
// Removes an element from the top of this stack
{
if (!isEmpty())
{
stack[topIndex] = null;
topIndex--;
}
else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}
public Object top()
// Returns the element on top of this stack
{
Object topOfStack = null;
if (!isEmpty())
topOfStack = stack[topIndex];
else
throw new StackUnderflowException("Top attempted on an empty stack.");
return topOfStack;
}
public boolean isEmpty()
// Checks if this stack is empty
{
if (topIndex == -1)
return true;
else
return false;
}
public boolean isFull()
// Checks if this stack is full
{
if (topIndex == (stack.length - 1))
return true;
else
return false;
}
}
1. (10 points) In the lectures we use the data structures ArrayStack write a " and "ArrayQueue" together to Java program to decide if an input string is a palindrome. You are asked to use the ata structures "LinkedStack" and ArrayQueue" together to write a Java program testing if an input string is a palindromeStep by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started