Question

You are provided with a StackInterface to implement your stack, make sure to implement the data structure using java.util.ArrayList and naming your implementation ArrayListStack (make sure to use generics like you have been for the data structures so far). The provided StackTester assumes you name your implementation that way. Note that you have also been provided a PalindromeTester with the specific isPalindrome() method you are required to implement, following the approach above. The method should take whitespace, case-sensitivity, digits, and symbols into account (see documentation above method).

Additionally, provide your implementation for a CircularArrayQueue<E> based on the java.util.Queue interface, passing the JUnit tests provided for the following six methods.

Queue interface methods to implement:

return type	method + description
boolean	add(E e)
	Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E	element()
	Retrieves, but does not remove, the head of this queue.
boolean	offer(E e)
	Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
E	peek()
	Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E	poll()
	Retrieves and removes the head of this queue, or returns null if this queue is empty.
E	remove()
	Retrieves and removes the head of this queue.

StackInterface.java

public interface StackInterface<E> {

    /**
     * Returns true if the stack is empty; otherwise, returns false
     *
     * @return true if empty, false otherwise
     */
    public boolean empty();

    /**
     * Returns the object at the top of the stack without removing it
     *
     * @return reference (shallow copy) of object at top of stack
     */
    public E peek();

    /**
     * Returns the object at the top of the stack and removes it
     *
     * @return reference of removed object from top of stack
     */
    public E pop();

    /**
     * Pushes an item onto the top of the stack and returns the item pushed.
     *
     * @param obj object to push onto top of stack
     * @return item that was pushed
     */
    public E push(E obj);
}

Answer 1

Hi,

I have Implemented the stack using the arraylist, following is the code for it. It should be straightforward to understand. Let me know if you need more help to understand this. To check for palindrome, you need to pass each character as an object to the following stack.

import java.util.ArrayList;

public class ArrayListStack implements StackInterface<Object> {

    ArrayList<Object> stack = new ArrayList<>();

    /**
     * Returns true if the stack is empty; otherwise, returns false
     *
     * @return true if empty, false otherwise
     */
    @Override
    public boolean empty() {
        return stack.isEmpty();
    }

    /**
     * Returns the object at the top of the stack without removing it
     *
     * @return reference (shallow copy) of object at top of stack
     */
    @Override
    public Object peek() {
        if (empty())
            return null;
        else
            return stack.get(stack.size() - 1);
    }

    /**
     * Returns the object at the top of the stack and removes it
     *
     * @return reference of removed object from top of stack
     */
    @Override
    public Object pop() {
        if (empty())
            return null;
        else {
            Object obj = stack.get(stack.size() - 1);
            stack.remove(stack.size() - 1);
            return obj;
        }
    }

    /**
     * Pushes an item onto the top of the stack and returns the item pushed.
     *
     * @param obj object to push onto top of stack
     * @return item that was pushed
     */
    @Override
    public Object push(Object obj) {
        stack.add(obj);
        return null;
    }

}

For the queue, the implementation is as following

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.Queue;

public class QueueArrayList implements Queue<Object> {

    private int currentSize; // Current Circular Queue Size
    private int maxSize; // Circular Queue maximum size

    private int rear;// rear position of Circular queue(new element enqueued at rear).
    private int front; // front position of Circular queue(element will be dequeued from front).

    private ArrayList<Object> queue;

    // initialize the class with size of circular queue
    QueueArrayList(int size) {
        maxSize = size;
        queue = new ArrayList<>(maxSize);
        this.front = -1;
        this.rear = -1;
        currentSize = 0;
    }

    // Inserts the specified element into this queue if it is possible to do so
    // immediately without violating capacity restrictions, returning true upon
    // success and throwing an IllegalStateException if no space is currently
    // available.
    @Override
    public boolean add(Object e) {
        // check if queue size if full
        if (currentSize != maxSize) {
            front = (front + 1) % maxSize;
            queue.add(front, e);
            currentSize++;
            return true;
        } else {
            throw new IllegalStateException();
        }
    }

    // Retrieves, but does not remove, the head of this queue.
    @Override
    public Object element() {
        return queue.get(front);
    }

    // Inserts the specified element into this queue if it is possible to do so
    // immediately without violating capacity restrictions.
    @Override
    public boolean offer(Object e) {
        //check if queue size is full
        if (currentSize != maxSize) {
            queue.add(front, e);
            front = (front + 1) % maxSize;
            currentSize++;
            return true;
        }
        return false;
    }

    // Retrieves, but does not remove, the head of this queue, or returns null if
    // this queue is empty.
    @Override
    public Object peek() {
        if (front == -1 && rear == -1)
            return null;
        else
            return queue.get(front);
    }

    // Retrieves and removes the head of this queue, or returns null if this queue
    // is empty.
    @Override
    public Object poll() {
        if (front == -1 && rear == -1)
            return null;
        else {
            return remove();
        }
    }

    // Retrieves and removes the head of this queue.
    @Override
    public Object remove() {
        Object o = null;
        //check if queue is empty
        if (currentSize == 0)
            return null;
        else {
            rear = (rear + 1) % maxSize;
            o = queue.get(rear);
            queue.remove(rear);
            currentSize--;
        }
        return o;
    }

    @Override
    public boolean remove(Object o) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public int size() {
        // TODO Auto-generated method stub
        return 0;
    }

    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean contains(Object o) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public Iterator<Object> iterator() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public Object[] toArray() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public Object[] toArray(Object[] a) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public boolean containsAll(Collection c) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean addAll(Collection c) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean removeAll(Collection c) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean retainAll(Collection c) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public void clear() {
        // TODO Auto-generated method stub

    }

}