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).

Next steps (adding generics):

Make sure everything is working correctly before moving on to this step. After things are working, you need to turn the Stack and Queue classes into generic classes. This requires several changes including a change to the List and Node classes to turn them into generic classes as well. Refer to the notes for help. After making these changes, you must modify the Main class to use your generic Stack and Queue classes. This means giving both Stack and Queue a value for the generic type parameter both at declaration and at instantiation. You only need to specify the datatype during declaration and instantiation, not every time you use the object.

ListAsLInkedList Class from program 3:

class ListAsLinkedList implements IList { private Node head; private int size; ListAsLinkedList() { } public void append(char var1) { if (this.head == null) { this.head = new Node(var1); ++this.size; } else { Node var2; for(var2 = this.head; var2.next != null; var2 = var2.next) { } var2.next = new Node(var1); ++this.size; } } public void prepend(char var1) { Node var2 = new Node(var1); var2.next = this.head; this.head = var2; ++this.size; } public void deleteAt(int var1) { if (var1 >= 0 && var1 < this.size) { if (var1 == 0) { this.head = this.head.next; --this.size; } else { Node var2 = this.head; for(int var3 = 0; var3 < var1 - 1; ++var3) { var2 = var2.next; } var2.next = var2.next.next; --this.size; } } } public int size() { return this.size; } public char getValueAt(int var1) { if (var1 >= 0 && var1 < this.size) { Node var2 = this.head; for(int var3 = 0; var3 < var1; ++var3) { var2 = var2.next; } return var2.value; } else { return '\u0000'; } } public int positionOf(char var1) { Node var2 = this.head; for(int var3 = 0; var3 < this.size; ++var3) { if (var2.value == var1) { return var3; } var2 = var2.next; } return -1; } } 

Node Class from program 3:

class Node { char value; Node next; public Node(char var1) { this.value = var1; } } 

Queue Template:

/** 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() { } } 

Stack Template:

/** 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() { } } 

Main Template:

import java.util.Scanner; import java.util.concurrent.TimeUnit; /** contains our entry point */ public class Main { private static boolean REVERSE_MAP = false; private static Stack stack; private static Queue queue; private static String[] map; private static int playerRow; private static int playerCol; private static final char PLAYER_SYMBOL = ';'; private static final int PLAYER_START_ROW = 8; private static final int PLAYER_START_COL = 9; private static Scanner scanner; private static boolean running; /** entry point */ public static void main(String[] args) { stack = new Stack(); queue = new Queue(); playerRow = PLAYER_START_ROW; playerCol = PLAYER_START_COL; scanner = new Scanner(System.in); running = true; loadMap(); if (REVERSE_MAP) { reverseMap(); } run(); } private static void loadMap() { map = new String[12]; map[ 0] = "STATICxSTATICxSTATI"; map[ 1] = "ST ATI CxS * STATIC"; map[ 2] = "ST AT ICx STATICx"; map[ 3] = "S T AT ICx ST"; map[ 4] = "S T A TI CS"; map[ 5] = "STATIC xSTA TIC xS"; map[ 6] = "S TA TI"; map[ 7] = "S TATICxSTATIC xST"; map[ 8] = "S T"; map[ 9] = "S TATICxSTATICxST A"; map[10] = "S T"; map[11] = "STATICxSTATICxSTATI"; } private static void reverseMap() { // for(int i = 0; i < map.length; i++) { // String line = map[i]; // Queue queue = new Queue(); // for(char c : line.toCharArray()) { // queue.enqueue(c); // } // queue.reverse(); // String revLine = ""; // while (!queue.isEmpty()) { // revLine += queue.dequeue(); // } // map[i] = revLine; // } } private static void run() { while(running) { clearScreen(); draw(); menu(); } } private static void clearScreen() { // use whichever method works for you // comment out the other method // UNIX based systems System.out.print("\033[H\033[2J"); // WINDOWS based systems /*try { new ProcessBuilder("cmd", "/c", "cls").inheritIO().start().waitFor(); } catch(Exception e) { // couldn't clear, oh well }*/ } private static void draw() { if (!REVERSE_MAP && playerRow == 1 && playerCol == 11) { map[2] = "ST AT ICxxSTATICx"; map[9] = "S >>>>>>>>>>>>>>> "; } else if (REVERSE_MAP && playerRow == 1 && playerCol == 7) { loadMap(); map[2] = "ST AT ICxxSTATICx"; map[9] = "S <<<<<<<<<<<<<<< "; reverseMap(); } for(int i = 0; i < map.length; i++) { if (playerRow == i) { for(int j = 0; j < playerCol; j++) { System.out.print(map[i].charAt(j)); } System.out.print(PLAYER_SYMBOL); for(int j = playerCol + 1; j < map[i].length(); j++) { System.out.print(map[i].charAt(j)); } System.out.println(); } else { System.out.println(map[i]); } } System.out.println(); if (!REVERSE_MAP && playerRow == 9 && playerCol == 18) { int[] nums = {206, 232, 232, 212, 220, 106, 112, 242, 94, 218, 222, 198, 92, 216, 228, 234, 242, 220, 210, 232, 94, 94, 116, 230, 224, 232, 232, 208, 64, 222, 232, 64, 222, 142}; char[] chars = new char[nums.length]; for(int i = nums.length - 1; i >= 0; i--) { chars[nums.length - i - 1] = (char)(nums[i] / 2); } System.out.println(new String(chars)); System.out.println(); } else if (REVERSE_MAP && playerRow == 9 && playerCol == 0) { rr(); } } private static void rr() { String something = "110100001110100011101000111000001110011001110100010111100101111011101000110100101101110011110010111010101110010011011000010111001100011011011110110110100101111001100100110011001100011011100000111001001100101001101100"; String somethingElse = ""; String x = ""; int n; for(int i = 0; i < something.length(); i++) { char c = something.charAt(i); if (i != 0 && i % 8 == 0) { n = Integer.parseInt(x, 2); n /= 2; somethingElse += Character.toString((char)n); x = ""; } x += "" + c; } n = Integer.parseInt(x, 2); n /= 2; somethingElse += Character.toString((char)n); System.out.println(somethingElse); System.out.println(); } private static void menu() { System.out.println("Action?"); System.out.println("w: go up"); System.out.println("a: go left"); System.out.println("s: go down"); System.out.println("d: go right"); if (!stack.isEmpty()) { System.out.println("u: undo last move"); } if (!queue.isEmpty()) { System.out.println("r: replay all"); } System.out.println("q: quit"); System.out.print ("? "); String inputLine = scanner.nextLine().trim(); if (inputLine.length() <= 0) return; char choice = inputLine.charAt(0); char mapChar; switch(choice) { // go up case 'w': if (playerRow-1 >= 0) { mapChar = map[playerRow-1].charAt(playerCol); if (mapChar == ' ' || mapChar == '*') { playerRow--; stack.push('w'); queue.enqueue('w'); } } break; // go left case 'a': if (playerCol-1 >= 0) { mapChar = map[playerRow].charAt(playerCol-1); if (mapChar == ' ' || mapChar == '*') { playerCol--; stack.push('a'); queue.enqueue('a'); } } break; // go down case 's': if (playerRow+1 < map.length) { mapChar = map[playerRow+1].charAt(playerCol); if (mapChar == ' ' || mapChar == '*') { playerRow++; stack.push('s'); queue.enqueue('s'); } } break; // go right case 'd': if (playerCol+1 < map[0].length()) { mapChar = map[playerRow].charAt(playerCol+1); if (mapChar == ' ' || mapChar == '*') { playerCol++; stack.push('d'); queue.enqueue('d'); } } break; // undo using stack case 'u': if (!stack.isEmpty()) { char top = stack.pop(); switch(top) { case 'w': playerRow++; queue.enqueue('s'); break; case 'a': playerCol++; queue.enqueue('d'); break; case 's': playerRow--; queue.enqueue('w'); break; case 'd': playerCol--; queue.enqueue('a'); break; } } break; // replay using queue case 'r': if (!queue.isEmpty()) { playerRow = PLAYER_START_ROW; playerCol = PLAYER_START_COL; Queue newQueue = new Queue(); while(!queue.isEmpty()) { clearScreen(); draw(); System.out.flush(); char move = queue.dequeue(); switch(move) { case 'w': playerRow--; break; case 'a': playerCol--; break; case 's': playerRow++; break; case 'd': playerCol++; break; } newQueue.enqueue(move); try { TimeUnit.MILLISECONDS.sleep(600); } catch(InterruptedException e) { System.out.println("Shit happens"); } } queue = newQueue; } break; // quit case 'q': running = false; break; } } }