You were asked to use generics and any of the data structures covered in chapter
ID: 665499 • Letter: Y
Question
You were asked to use generics and any of the data structures covered in chapters 20 and 21 to implement your own generic stack and queue. Use the UML diagrams below as a guidance.
MyStack <E>
-data structure
Select your own data structure to implement stack
+MyStack()
+MyStack (c :E[])
+isEmpty():Boolean
+push(item:E):void
+pop():E
+clear():void
Creates an empty stack
Creates a stack with items in an array
Returns true if empty, otherwise, returns false
Pushes an item on top of stack
Returns and removes an item from the top of stack
Reset Stack to empty
MyQueue <E>
-data structure
Select your own data structure to implement queue
+MyQueue()
+MyQueue (c :E[])
+isEmpty():Boolean
+enqueue(item:E):void
+dequeue():E
+clear():void
Creates an empty queue
Creates a queue with items in an array
Returns true if empty, otherwise, returns false
Inserts an item at end of queue
Returns and removes an item from the front of queue
Reset queue to empty
Create a driver to test the stack and queue.
Test your stack and queue with the attached drivers.
import java.util.*;
public class MyQueueTest {
public static void main (String [] args) {
MyQueue <Integer> myQueue = new MyQueue<Integer>();
myQueue.enqueue(10);
myQueue.enqueue(5);
myQueue.enqueue(15);
myQueue.enqueue(50);
System.out.println (" original integer queue ");
while (!myQueue.isEmpty())
System.out.print (myQueue.dequeue() + " ");
MyQueue <String> myQ = new MyQueue<String>();
myQ.enqueue ("Kim");
myQ.enqueue ("Jasmin");
myQ.enqueue ("Noma");
myQ.dequeue();
System.out.println (" original String queue ");
while (!myQ.isEmpty())
System.out.print (myQ.dequeue() + " ");
String [] names = {"Kemper", "Carlton", "Caleb"};
MyQueue<String> myQ2 = new MyQueue<String> (names);
System.out.println (" original second String queue ");
while (!myQ2.isEmpty()){
System.out.print(myQ2.dequeue()+ " ");
}
}
}
public class MyStackTester {
public static void main (String [] args) {
MyStack myStack = new MyStack();
myStack.push("Chris");
myStack.push("Kim");
myStack.push("Jasmin");
System.out.println ("Original Stack: ");
while (!myStack.isEmpty()){
System.out.print(myStack.pop()+ " ");
}
System.out.println (" Is it empty? " + myStack.isEmpty());
Integer [] numbers = {10, 20, 30};
myStack = new MyStack (numbers);
System.out.println ("Second Stack: ");
while (!myStack.isEmpty()){
System.out.print(myStack.pop()+ " ");
}
}
}
MyStack <E>
-data structure
Select your own data structure to implement stack
+MyStack()
+MyStack (c :E[])
+isEmpty():Boolean
+push(item:E):void
+pop():E
+clear():void
Creates an empty stack
Creates a stack with items in an array
Returns true if empty, otherwise, returns false
Pushes an item on top of stack
Returns and removes an item from the top of stack
Reset Stack to empty
Explanation / Answer
My stack implementation
-------------------------------------------------
As a datastructure, dynamic array is being used. In Java, the same can be done using generic ArrayList. And, stack behaves in LIFO (Last In First Out) manner.So, here the same is being achieved using the ArrayList. items are pushed one by one into the list, but while popping the last item is being returned and removed from the list.
The implementation is as below,
public class MyStack<E>
{
private List<E> dataStructure
public MyStack()
{
this.dataStructure = new ArrayList<E>();
}
public MyStack(E[] items):this()
{
for(E item: items)
{
this.dataStructure.add(item);
}
}
public boolean isEmpty()
{
return this.dataStructure.size() == 0;
}
public void push(E item)
{
this.dataStructure.add(item);
}
public E pop()
{
int size = this.dataStructure.size();
if(size > 0)
{
E item = this.dataStructure.get(size-1);
this.dataStructure.remove(size-1);
return item;
}
return -1;
}
public void clear()
{
this.dataStructure.clear();
}
}
My queue implementation
-------------------------------------------------
And, queue behaves in FIFO (First In First Out) manner.So, here the same is being achieved using the ArrayList. items are enqued one by one into the list, but while dequing the first item is being returned and removed from the list.
The implementation is as below,
public class MyQueue<E>
{
private List<E> dataStructure
public MyQueue()
{
this.dataStructure = new ArrayList<E>();
}
public MyQueue(E[] items):this()
{
for(E item: items)
{
this.dataStructure.add(item);
}
}
public boolean isEmpty()
{
return this.dataStructure.size() == 0;
}
public void enqueue(E item)
{
this.dataStructure.add(item);
}
public E dequeue()
{
int size = this.dataStructure.size();
if(size > 0)
{
E item = this.dataStructure.get(0);
this.dataStructure.remove(0);
return item;
}
return -1;
}
public void clear()
{
this.dataStructure.clear();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.