Homework Sourse1 In Java Create an array based implementation of a stack Yo
1- In Java Create an array based implementation of a stack
You will 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
Following is implementation in Java for above
package com.learning.solr;
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();
}
import java.util.Arrays;
public class ArrayStack implements StackOperations {
private int top = -1;
private static final int DEFAULT_CAPACITY = 4;
private int items[];
public ArrayStack() {
items = new int[DEFAULT_CAPACITY];
}
@Override
public void push(int item) {
if (top == items.length - 1) {
resizeArrayStackCapacity();
}
items[++top] = item;
}
@Override
public int pop() {
return items[top--];
}
@Override
public int peek() {
return items[top];
}
@Override
public boolean isEmpty() {
return (top == -1);
}
private void resizeArrayStackCapacity() {
int newSize = items.length * 2;
items = Arrays.copyOf(items, newSize);
}
@Override
public String toString() {
if (isEmpty()) {
return \"top [ ] bottom (empty stack)\";
} else {
StringBuilder itemsBuilder = new StringBuilder();
itemsBuilder.append(\"[ \");
for (int i = 0; i <= top; i++) {
itemsBuilder.append(items[i] + \" \");
}
itemsBuilder.append(\"]\");
return \" top \" + itemsBuilder + \" bottom (stack with \" + (top + 1) + \" elements)\";
}
}
public int getSize(){
return top + 1;
}
protected int[] getItems() {
return items;
}
}
package com.learning.solr;
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();
}
package com.learning.solr;
import java.util.Arrays;
public class ArrayQueue implements QueueOperations {
private static final int DEFAULT_CAPACITY = 4;
private int[] items;
private int capacity; // capacity
private int front = 0;
private int rear = 0;
private int size=0;
public ArrayQueue() {
this(DEFAULT_CAPACITY);
}
public ArrayQueue(int capacity) {
this.capacity = capacity;
this.items = new int[capacity];
}
@Override
public int dequeue() {
int item = 0;
if (isEmpty()) {
System.out.println(\"Array queue is empty\");
} else {
item = items[front];
items[front] = 0;
front = (front + 1) % capacity;
size--;
}
return item;
}
@Override
public void enqueue(int element) {
int diff = rear - front;
if (diff == -1 || diff == (capacity - 1)) {
resizeArrayQueueCapacity();
}
items[rear] = element;
rear = (rear + 1) % capacity;
size++;
}
private void resizeArrayQueueCapacity() {
int newSize = items.length * 2;
capacity=newSize;
items = Arrays.copyOf(items, newSize);
}
@Override
public boolean isEmpty() {
return (rear == front) ? true : false;
}
@Override
public int peek() {
if (isEmpty()) {
System.out.println(\"Array queue is empty\");
return 0;
} else {
return items[front];
}
}
@Override
public String toString() {
return \"front:\" + front + \" back:\" + rear
+ \"\ front \"+Arrays.toString(items)+\" back (queue with \"+size+\" elements wrapped)\";
}
}
package com.learning.solr;
/**
* 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.
*/
public class UseArrayStackImpl {
public static void main(String[] args) {
ArrayStack arrayStack=new ArrayStack();
arrayStack.push(1);
arrayStack.push(2);
arrayStack.push(3);
arrayStack.push(4);
arrayStack.push(5);
System.out.println(arrayStack);
ArrayStack arrayStack2=new ArrayStack();
arrayStack.push(1);
arrayStack.push(2);
arrayStack.push(3);
arrayStack.push(4);
arrayStack.push(5);
System.out.println(arrayStack);
System.out.println(areEqual(arrayStack, arrayStack2));
ArrayStack arrayStack3=new ArrayStack();
arrayStack.push(1);
arrayStack.push(2);
arrayStack.push(3);
arrayStack.push(4);
arrayStack.push(5);
System.out.println(areEqual(arrayStack, arrayStack3));
ArrayStack arrayStack4=duplicateStack(arrayStack2);
System.out.println(areEqual(arrayStack2, arrayStack4));
}
/**
* 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.
*/
public static boolean areEqual(ArrayStack arrayStack1, ArrayStack arrayStack2) {
// Check for nulls
if (arrayStack1 == null || arrayStack2 == null)
return false;
if (arrayStack1 == arrayStack2)
return true;
if (arrayStack1.getSize() != arrayStack2.getSize())
return false;
for (int i = 0; i < arrayStack1.getSize(); i++) {
if (arrayStack1.getItems()[i] != arrayStack2.getItems()[i]) {
return false;
}
}
return true;
}
/**
* 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.
*/
public static ArrayStack duplicateStack(ArrayStack arrayStack) {
ArrayStack duplicateStack = new ArrayStack();
for (int i = 0; i < arrayStack.getSize(); i++) {
duplicateStack.push(arrayStack.getItems()[i]);
}
return duplicateStack;
}
}
