Homework Sourse1 In Java Create an array based implementation of a stack Re
1- In Java Create an array based implementation of a stack
Requirments:
a- Use packages to organize your code. The classes/abstractions of your collections should exist in some logical package, i.e., kent.edu.ood.hw.collections. Your collection classes should not contain the main program.
b- Create a separate package that will contain your \"driver\" class. This class can be the class that contains your implementation for the isEqual method (and the other method specified in the assignment).
c- Use \"src/main/java\" as your source directory. Most likely most of are just using \"src\"
create a class called ArrayStack that implements StackOperations. You are to implement the appropriate behavior and state required for this abstraction. For simplicity, assume our stack abstraction only contains integer values.
public interface StackOperations {
// Push an item onto the stack
public void push(int item);
// Pop an item off the stack
public int pop();
// Return the top item from the stack
public int peek();
// Return true if empty, otherwise false
public boolean isEmpty();
}
For this portion of the assignment you will implement a stack using an array. Your array should be unbounded meaning that your implementation should detect when your array is full, create a new, bigger array and then copy the old array to the new one. The user of the push method should not be aware that this is happening in the background. Conversely, your pop method should throw a NoSuchElementException when the method is called and the stack is empty.
In addition, in ArrayStack, implement/override the toString method so that it returns a string in exactly the following format (three examples shown with integers):
top [ ] bottom (empty stack)
top [ 1 ] bottom (stack with one element)
top [ 5 2 8 ] bottom (stack with 3 elements)
2.In Java Create an array based implementation of a queue
You will create a class called ArrayQueue that implements QueueOperations. You are to implement the appropriate behavior and state required for this abstraction. For simplicity, assume our queue abstraction only contains integer values.
public interface QueueOperations {
// Remove an element from the queue
public int dequeue();
// Place an element on the queue
public void enqueue(int element);
// Check if the queue is empty
public boolean isEmpty();
// Return element at head of queue but don’t remove it.
public int peek();
}
You will implement a queue using an array. The problem is that, as you enqueue and dequeue elements, the data in the queue is stored towards the end of the array and space frees up at the beginning of the array.
To reuse any unused space, your array implementation should be circular. That is, whenever we reach the end of the array we “wrap around” to the beginning of the array. You may find that using the modulus (%) operator is handy for keeping the front and back indices within the index bounds of the array.
As with your array implementation using stacks, when your queue array is full, you’ll need to expand the array by copying the queue data to a new, bigger array. Your new front of the queue should be the zeroth element of the array. You’ll need to figure out how to detect that your array is full (hint: keep a counter of the number of elements in the queue/array).
Finally, implement the methods of the ArrayQueue including the toString method, which should return a string in exactly the following format (two examples shown with integers):
front: 4 back: 4
front [ 1 ] back (queue with one element)
front: 6 back: 0
front [ 5 2 8 ] back (queue with 3 elements wrapped)
Use your implementations
1. The task here is write a method that will create (2) stacks based on the implementation you created and use their APIs to determine if the stacks are the same. In other words, write a method areEqual that returns true if the two stacks specified in the parameters have the same elements in the same order, and false otherwise. Two elements are the same if they refer to the same object. The method may remove elements from the stacks, but it must return the elements to the stacks in the same order to restore the stacks to their original state.
2. Write a method duplicateStack that returns a new stack containing the same elements and in the same order as the stack specified in the parameter. The method should create a new stack and fill it with the same data elements as the given stack. Note, your method, when completed should not alter the contents of the original stack passed into your method.
Solution
interface QueueOperations {
// return the size of the queue
public int size();
public boolean isEmpty();
public boolean isFull();
// insert an element into the queue
public void enqueue(int obj) throws Exception;
// removes an element from the queue
public int dequeue() throws Exception;
public int peek() throws Exception;
}
class ArrayQueue implements QueueOperations{
private static final int capacity = 5;
private int[] Q;
private final int N; // capacity
private int f = 0;
private int r = 0;
private int s = 0;
public ArrayQueue(){
this(capacity);
}
public ArrayQueue(int capacity){
N = capacity;
Q = new int[N];
}
public int size() {
return s;
}
public boolean isEmpty() {
return (r == f) ? true : false;
}
public boolean isFull() {
int diff = r - f;
if(diff == -1 || diff == (N -1))
return true;
return false;
}
public void enqueue(int obj) throws Exception{
if(isFull()){
throw new Exception();
}else{
Q[r] = obj;
r = (r + 1) % N;
s++;
}
}
public int dequeue() throws Exception{
int item;
if(isEmpty()){
throw new Exception();
}else{
item = Q[f];
Q[f] = 0;
f = (f + 1) % N;
s--;
}
return item;
}
@Override
public String toString() {
String s;
s = \"front [\";
if (size() > 0)
s += Q[0];
if (size() > 1)
for (int i = 1; i <= size() - 1; i++) {
s += \", \" + Q[i];
}
String str = \"front :\"+f+\" back :\"+r+\" \ \";
s = str +s;
return s + \"] back\";
}
@Override
public int peek() throws Exception {
if (isEmpty())
throw new Exception(\"Stack is empty.\");
return Q[f];
}
}
interface StackOperations {
// Push an item onto the stack
public void push(int item);
// Pop an item off the stack
public int pop() throws Exception;
// Return the top item from the stack
public int peek() throws Exception;
// Return true if empty, otherwise false
public boolean isEmpty();
}
class ArrayStack implements StackOperations{
protected int capacity;
public static final int CAPACITY = 16; // power of 2
public static int MINCAPACITY=1<<15; // power of 2
protected int[] stackRep;
protected int top = -1;
public ArrayStack() {
this(CAPACITY); // default capacity
}
public ArrayStack(int cap) {
capacity = cap;
stackRep = new int[capacity]; // compiler may give warning, but this
}
public int size() {
return (top + 1);
}
public boolean isEmpty() {
return (top < 0);
}
public void push(int data) {
if (size() == capacity)
expand();
stackRep[++top] = data;
}
private void expand() {
int length = size();
int[] newstack=new int[length<<1]; // or 2* length
System.arraycopy(stackRep,0,newstack,0,length);
stackRep=newstack;
}
@SuppressWarnings(\"unused\")
private void shrink() {
int length = top + 1;
if(length<=MINCAPACITY || top<<2 >= length)
return;
length=length + (top<<1); // still means shrink to at 1/2 or less of the heap
if(top<MINCAPACITY) length = MINCAPACITY;
int[] newStack=new int[length];
System.arraycopy(stackRep,0,newStack,0,top+1);
stackRep=newStack;
}
@Override
public int peek() throws Exception {
if (isEmpty())
throw new Exception(\"Stack is empty.\");
return stackRep[top];
}
@Override
public int pop() throws Exception {
int data;
if (isEmpty())
throw new Exception(\"Stack is empty.\");
data = stackRep[top];
stackRep[top--] = Integer.MIN_VALUE; // dereference S[top] for garbage collection.
return data;
}
@Override
public String toString() {
String s;
s = \"top [\";
if (size() > 0)
s += stackRep[0];
if (size() > 1)
for (int i = 1; i <= size() - 1; i++) {
s += \", \" + stackRep[i];
}
return s + \"] bottom\";
}
}
class Driver{
public static boolean areEqual(ArrayStack stk1,ArrayStack stk2){
if(stk1==null&&stk2==null)
return true;
else if(stk1==null&&stk2!=null)
return false;
else if(stk2==null&&stk1!=null)
return false;
else if(stk1.size() != stk2.size()){
return false;
}
else{
boolean isSame =true;
try{
ArrayStack tempStk1 = new ArrayStack(stk1.size());
ArrayStack tempStk2 = new ArrayStack(stk2.size());
while(!stk1.isEmpty()){
int item1 = stk1.pop();
int item2 = stk2.pop();
tempStk1.push(item1);
tempStk2.push(item2);
if(item1 != item2)
isSame = false;
break;
}
while(!tempStk1.isEmpty()){
stk1.push(tempStk1.pop());
stk2.push(tempStk2.pop());
}
}
catch(Exception e){
}
return isSame;
}
}
public static ArrayStack duplicateStack(ArrayStack stk){
if(stk==null)return null;
ArrayStack newStakc = new ArrayStack(stk.size());
ArrayStack tempStakc = new ArrayStack(stk.size());
try{
while(!stk.isEmpty()){
tempStakc.push(stk.pop());
}
while(!tempStakc.isEmpty()){
int item = tempStakc.pop();
stk.push(item);
newStakc.push(item);
}
}
catch(Exception e){
}
return newStakc;
}
}
