Program Speci cation: A Stack is a simple container that is initially empty and
ID: 3606115 • Letter: P
Question
Program Speci cation:
A Stack is a simple container that is initially empty and need only support three simple operations:
isEmpty - reports true if the stack contains no values, otherwise reports false.
push value - adds value onto the stack.
pop - removes the most currently pushed value on the stack { FILO.
You are to extend your DynArray class to implement a stack which can hold double values and adheres
to the following:
Mandatory Instance methods:
public int size()
// returns the number of values which are currently on the stack
public boolean isEmpty()
// returns true only if there are no values on the stack
public void push(double value)
// add the specified value onto the stack
public double pop()
// if the stack is not empty,
// remove and returns the most currently push'd value on the stack
// otherwise,
// returns Double.NaN
public void stackDump()
// print all of the values currenty on the stack, in the order that
// they would be pop'd off of the stack
A Queue is a simple container that is initially empty and need only support three simple operations:
isEmpty - reports true if the queue contains no values, otherwise reports false.
que value - adds value into the queue.
deQue - removes the least currently queed value in the queue { FIFO.
You are to extend your DynArray class to implement a queue which can hold double values and adheres
to the following:
Mandatory Instance methods:
public int size()
// returns the number of values which are currently in the queue
public boolean isEmpty()
// returns true only if there are no values in the queue
public void que(double value)
// add the specified value into the queue
public double deQue()
// if the queue is not empty,
// remove and returns the least currently que'd value in the queue
// otherwise,
/ returns Double.NaN
public void queueDump()
// print all of the values currenty in the queue, in the order that
// they would be deQue'd from the queue
Your Class must also work with the following Driver Class StackQueueDriver:
public class StackQueueDriver
{
public static void main(String[] args)
{
Stack myStack = new Stack();
Queue myQueue = new Queue();
System.out.println("Filling Stack:");
double value;
for (int s = 1; s < 11; ++s)
{
value = s + s/10.0;
System.out.println(" pushing " + value);
myStack.push(value);
}
System.out.println(" Stack Dump:");
myStack.stackDump();
System.out.println(" Emptying Stack:");
while(!myStack.isEmpty())
{
value = myStack.pop();
System.out.println(" pop = " + value);
}
System.out.println(" Stack Dump:");
myStack.stackDump();
System.out.println(" A pop too far = " + myStack.pop());
System.out.println(" ");
System.out.println("Filling Queue:");
for (int q = 1; q < 11; ++q)
{
value = 2*q + q/10.0;
System.out.println(" queing " + value);
myQueue.que(value);
}
System.out.println(" Queue Dump:");
myQueue.queueDump();
System.out.println(" Emptying Queue:");
while(!myQueue.isEmpty())
{
value = myQueue.deQue();
System.out.println(" deQue = " + value);
}
System.out.println(" Queue Dump:");
myQueue.queueDump();
System.out.println(" A deQue too far = " + myQueue.deQue());
}
}
And produce the following output (or something equivalent):
Filling Stack:
pushing 1.1
pushing 2.2
pushing 3.3
pushing 4.4
pushing 5.5
pushing 6.6
pushing 7.7
pushing 8.8
pushing 9.9
pushing 11.0
Stack Dump:
11.0
9.9
8.8
7.7
6.6
5.5
4.4
3.3
2.2
1.1
Emptying Stack:
pop = 11.0
pop = 9.9
pop = 8.8
pop = 7.7
pop = 6.6
pop = 5.5
pop = 4.4
pop = 3.3
pop = 2.2
pop = 1.1
Stack Dump:
A pop too far = NaN
Filling Queue:
queing 2.1
queing 4.2
queing 6.3
queing 8.4
queing 10.5
queing 12.6
queing 14.7
queing 16.8
queing 18.9
queing 21.0
Queue Dump:
array.at(0) = 2.1
array.at(1) = 4.2
array.at(2) = 6.3
array.at(3) = 8.4
array.at(4) = 10.5
array.at(5) = 12.6
array.at(6) = 14.7
array.at(7) = 16.8
array.at(8) = 18.9
array.at(9) = 21.0
Emptying Queue:
deQue = 2.1
deQue = 4.2
deQue = 6.3
deQue = 8.4
deQue = 10.5
deQue = 12.6
deQue = 14.7
deQue = 16.8
deQue = 18.9
deQue = 21.0
Queue Dump:
A deQue too far = NaN
DynArray:
class DynArray
{
private double[] array;
private int size;
private int nextIndex;
public DynArray() // constructor
{
// set array to a new array of double, of size one set size to one, and set nextIndex to zero.
array = new double[1];
size = 1;
nextIndex = 0;
}
public int arraySize() // Accessor
{
// return the value of size.
return size;
}
public int elements() // accessor
{
// return the value of nextIndex.
return nextIndex;
}
public double at(int index) // accessor
{
// if 0 <= index < nextIndex
if(index >=0 && index < nextIndex)
// return the value of array[index].
return array[index];
// Otherwise
else
// return Double.NaN.
return Double.NaN;
}
private void grow()
{
// make array a reference to an array that is twice as large
// and contains the same values for indicies 0 through
// nextIndex - 1, and adjust size appropriately.
if(nextIndex == size)
{
array = Arrays.copyOf(array, size*2);
size = size *2;
}
}
private void shrink()
{
// make array a reference to an array that is half as large
// and contains the same values for indicies 0 through
// nextIndex - 1, and adjust size appropriately.
if(nextIndex == (size/2))
{
array = Arrays.copyOf(array, size/2);
size = size / 2;
}
}
//public void insertAt(int index, double value) // mutator
//{
// if 0 <= index <= nextIndex
//if(index >= 0 && index <= nextIndex)
// move the nessecary values over one so that value can be incerted at the location index in the array,
// inserts incerts value at the location index, and adjust nextIndex appropriately.
// Note a grow() may be neccessary before or after.
// Otherwise
//else
//return; // do nothing.
//}
public void insert(double value) // mutator
{
grow();
// insert value at location nextIndex.
array[nextIndex] = value;
nextIndex++;
}
//public double removeAt(int index) // mutator
// if 0 <= index < nextIndex
// move the nessecary values over one as to eliminate
// the value at the location index in the array, adjust
// nextIndex appropriately, and return the value that was
// at the location index .
// Note: a shrink() may be neccessary before or after.
// else
// return Double.NaN.
public double remove() // mutator
{
// return the removal of the value at location nextIndex-1.
double value = at(nextIndex-1);
shrink();
--nextIndex;
return value;
}
public void printArray() //accessor
{
// prints the values of all occupied locations of the array to the screen
for(int x = 0; x < size; x++)
System.out.printf("array[%d] = %f", x, array[x]);
}
}
Explanation / Answer
/*----------- Make a package with name stack_queue and add the following file in it ------------------------*/
/*----------- Make a class file with name Stack and paste this code ------------------------*/
package stack_queue;
public class Stack extends DynArray {
public int size(){
return arraySize();
}
// returns the number of values which are currently on the stack
public boolean isEmpty(){
if(arraySize()<=0){
return true;
}
else return false;
}
// returns true only if there are no values on the stack
public void push(double value){
insert(value);
}
// add the specified value onto the stack
public double pop(){
return remove();
}
// if the stack is not empty,
// remove and returns the most currently push'd value on the stack
// otherwise,
// returns Double.NaN
public void stackDump(){
int nextIndex=arraySize();
while(nextIndex>=0){
double value = at(nextIndex-1);
--nextIndex;
if(at(nextIndex)>=0){
System.out.println("Dumping = "+value);
}
}
}
}
// print all of the values currenty on the stack, in the order that
// they would be pop'd off of the stack
/*----------- Make a class file with name Queue and paste this code ------------------------*/
package stack_queue;
public class Queue extends DynArray {
public int size(){
return arraySize();
}
// returns the number of values which are currently in the queue
public boolean isEmpty(){
if(arraySize()<=0){
return true;
}
else return false;
}
// returns true only if there are no values in the queue
public void que(double value){
insert(value);
}
// add the specified value into the queue
public void deQue(){
int i=0;
while(at(i)>=0){
System.out.println("deQue = "+at(i));
i++;
}
}
// if the queue is not empty,
// remove and returns the least currently que'd value in the queue
// otherwise,
// returns Double.NaN
public void queueDump(){
int i=0;
while(at(i)>=0){
System.out.println("deQue = "+at(i));
i++;
}
}
// print all of the values currenty in the queue, in the order that
// they would be deQue'd from the queue
}
/*----------- Make a class file with name DynArray and paste this code ------------------------*/
package stack_queue;
import java.util.Arrays;
public class DynArray {
private double[] array;
private int size;
private int nextIndex;
private int startIndex;
public DynArray() // constructor
{
// set array to a new array of double, of size one set size to one, and set nextIndex to zero.
array = new double[1];
size = 1;
nextIndex = 0;
startIndex=0;
}
public int arraySize() // Accessor
{
// return the value of size.
return size;
}
public int elements() // accessor
{
// return the value of nextIndex.
return nextIndex;
}
public double at(int index) // accessor
{
// if 0 <= index < nextIndex
if(index >=0 && index < nextIndex)
// return the value of array[index].
return array[index];
// Otherwise
else
// return Double.NaN.
return Double.NaN;
}
private void grow()
{
// make array a reference to an array that is twice as large
// and contains the same values for indicies 0 through
// nextIndex - 1, and adjust size appropriately.
if(nextIndex == size)
{
array = Arrays.copyOf(array, size*2);
size = size *2;
}
}
private void shrink()
{
// make array a reference to an array that is half as large
// and contains the same values for indicies 0 through
// nextIndex - 1, and adjust size appropriately.
if(nextIndex == (size/2))
{
array = Arrays.copyOf(array, size/2);
size = size / 2;
}
}
public double deq(){
double value = at(startIndex);
//qshrink();
++startIndex;
return value;
}
//public void insertAt(int index, double value) // mutator
//{
// if 0 <= index <= nextIndex
//if(index >= 0 && index <= nextIndex)
// move the nessecary values over one so that value can be incerted at the location index in the array,
// inserts incerts value at the location index, and adjust nextIndex appropriately.
// Note a grow() may be neccessary before or after.
// Otherwise
//else
//return; // do nothing.
//}
public void insert(double value) // mutator
{
grow();
// insert value at location nextIndex.
array[nextIndex] = value;
nextIndex++;
}
//public double removeAt(int index) // mutator
// if 0 <= index < nextIndex
// move the nessecary values over one as to eliminate
// the value at the location index in the array, adjust
// nextIndex appropriately, and return the value that was
// at the location index .
// Note: a shrink() may be necessary before or after.
// else
// return Double.NaN.
public double remove() // mutator
{
// return the removal of the value at location nextIndex-1.
double value = at(nextIndex-1);
shrink();
--nextIndex;
return value;
}
public void printArray() //accessor
{
// prints the values of all occupied locations of the array to the screen
//for(int x = 0; x < size; x++){}
//System.out.printf("array[%d] = %f", x, array[x]);
}
}
/*----------- Make a class file with name StackQueueDriver and paste this code ------------------------*/
package stack_queue;
public class StackQueueDriver
{
public static void main(String[] args)
{
Stack myStack = new Stack();
Queue myQueue = new Queue();
System.out.println("Filling Stack:");
double value;
for (int s = 1; s < 11; ++s)
{
value = s + s/10.0;
System.out.println(" pushing " + value);
myStack.push(value);
}
System.out.println(" Stack Dump:");
myStack.stackDump();
System.out.println(" Emptying Stack:");
System.out.println(" Stack Dump:");
myStack.stackDump();
while(!myStack.isEmpty())
{
value = myStack.pop();
System.out.println(" pop = " + value);
}
System.out.println(" A pop too far = " + myStack.pop());
System.out.println(" ");
System.out.println("Filling Queue:");
for (int q = 1; q < 11; ++q)
{
value = 2*q + q/10.0;
System.out.println(" queing " + value);
myQueue.que(value);
}
System.out.println(" Queue Dump:");
myQueue.queueDump();
System.out.println(" Emptying Queue:");
//while(!myQueue.isEmpty())
//{
myQueue.deQue();
//System.out.println(" deQue = " + value);
//}
System.out.println(" Queue Dump:");
myQueue.queueDump();
System.out.println(" A deQue too far = NaN");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.