CSC 220 Data Structures Program #4 (follows: L5 Stacks, Queues and Generics, requires: P3) Description: Your objective is to implement a stack and a queue using the list implementation you did in program #3. You must use the linked list implementation of a list. You are to use your list operations to accomplish the operations of a stack and queue. Getting started: Grab your ListAsLinkedList class and your Node class from program #3 In the List.java file given to you, where it says "public class List", put your ListAsLinkedList class's fields and methods. To be clear, this creates a new class called List (that does NOT implement IList) that is the exact same as your ListAsLinkedList class. DON'T FORGET to rename the constructor to "List". Where it says "class Node", put your Node class's fields and methods. You will not need the IList interface nor the ListAsArray class, so do NOT include them. The Stack.java and Queue.java files given to you are where you will implement your stack and queue. They have been "stubbed out" meaning method "stubs", or blank methods, have been created for you. These need to be given an implementation that will carry out the operations. To be clear, you are NOT recreating a linked list in your Stack and Queue classes. I should NOT see any reference to the Node datatype nor the head field in your Stack and Queue files. Instead, use the given list field on line 5 and perform List operations (i.e. append, prepend, deleteAt, size, getValueAt, and positionOf) on that list field. Use 1 or more of these operations on your list field to mimic the operations of a Stack (push, pop, peek, and isEmpty) and Queue(enqueue, dequeue, front, and isEmpty). Not following these directions will result in failing this assignment as it defeats the purpose of teaching you how to use a fully implemented abstract data type to create another abstract data type (i.e. using a fully implemented List to create a Stack and Queue). Running the code: The Main.java file contains the entry point, so compiling and running that class will run the application. The undo command in the game relies on a correct stack implementation and the replay command relies on a correct queue implementation. Testing these two commands will test your stack and queue implementations and ensure they are functioning correctly.

code template for stack:

/** Stack abstract data type */ public class Stack { /** List objects to hold our stack items. Use List operations to implement the methods below */ private List list;

public Stack() { // instantiate list here

}

public void push(char value) {

}

public char pop() {

}

public char peek() {

}

public boolean isEmpty() {

} }

code template for queue

/** Queue abstract data type */ public class Queue { /** List objects to hold our queue items. Use List operations to implement the methods below */ private List list; public Queue() { // instantiate list here

} public void enqueue(char value) {

} public char dequeue() {

}

public char front() {

}

public boolean isEmpty() {

} }

my list class:

class ListAsArray implements IList {

// initialize array to a size of 30 elements // this will prevent the need to resize our array

//character array to store elements

char arr[];

//count of current number of elements in this list

int count;

public ListAsArray() {

// size of 30 elements

arr = new char[30];

count = 0;

}

@Override

public void append(char value) {

//checking if there is space for new element

if (count < arr.length) {

//adding to list at index count

arr[count] = value;

//updating count

count++;

}

}

@Override

public void prepend(char value) {

//checking if there is space

if (count < arr.length) {

//shifting current elements to one place to right

for (int i = count; i > 0; i--) {

arr[i] = arr[i - 1];

}

//new value at index 0 and updating count

arr[0] = value;

count++;

}

}

@Override

public void deleteAt(int position) {

//checking if position is valid

if (position >= 0 && position < count) {

for (int i = position; i < count - 1; i++) {

arr[i] = arr[i + 1];

}

//updating count

count--;

}

}

@Override

public int size() {

return count;

}

@Override

public char getValueAt(int position) {

//if position is valid, returning element at position

if (position >= 0 && position < count) {

return arr[position];

}

throw new IndexOutOfBoundsException("Invalid position: " + position);

}

@Override

public int positionOf(char value) {

//looping and finding the index of value

for (int i = 0; i < count; i++) {

if (arr[i] == value) {

//if found

return i;

}

}

//if not found

return -1;

}

}

/** Singly Linked List implementation of our List */ class ListAsLinkedList implements IList {

//references to head and tail nodes of this list

private Node head, tail;

//count of current number of elements in this list

private int count;

//constructor initializing empty list

public ListAsLinkedList() {

head=null;

tail=null;

count=0;

}

@Override

public void append(char value) {

//new node with given value

Node newNode=new Node(value);

//if head is null, adding as both head and tail

if(head==null){

head=newNode;

tail=newNode;

} else{

//appending to tail and updating tail

tail.next=newNode;

tail=newNode;

}

//updating count

count++;

}

@Override

public void prepend(char value) {

//creating a new node with given value

Node newNode=new Node(value);

//if head is null, adding as both head and tail

if(head==null){

head=newNode;

tail=newNode;

}else{

newNode.next=head;

head=newNode;

}

//updating count

count++;

}

@Override

public void deleteAt(int position) {

if(position>=0 && position

//if position is 0, removing head node

if(position==0){

head=head.next;

//if list just become empty, setting tail to null

if(head==null){

tail=null;

}

//updating count

count--;

return;

}

Node curr=head;

for(int i=0;i

curr=curr.next;

}

//removing curr.next

curr.next=curr.next.next;

//if new curr.next is null, setting curr as tail

if(curr.next==null){

tail=curr;

}

//updating count

count--;

}

}

@Override

public int size() {

return count;

}

@Override

public char getValueAt(int position) {

//exception if position is invalid

if(position<0 || position>=count){

throw new IndexOutOfBoundsException("Invalid position: " + position);

}

Node temp=head;

for(int i=0;i

temp=temp.next;

}

//returning data of temp

return temp.data;

}

@Override

public int positionOf(char value) {

int pos=0;

//looping through nodes and finding node with target value

for(Node temp=head;temp!=null;temp=temp.next){

if(temp.data==value){

//found

return pos;

}

pos++;

}

//not found

return -1;

}

}

/** A singly linked list node for our singly linked list */ class Node { char data; //data value

Node next; //pointer to next node

public Node(char data) {

this.data = data;

next=null;

}

}