The goal of this lab is to implement methods of a deque (pronounced "deck" and short for the double-ended queue). This is an individual assignment; you cannot share code with other students.

To implement a deque, we will use the LinkedList class that we implemented in the class and past labs.

In this lab, you need to implement the methods outlined in Table 3.17.1: Common deque ADT operations.

• void pushFront(int item)
• void pushBack(int item)
• int popFront()
• int popBack()
• int peekFront()
• int peekBack()
• boolean isEmpty()
• int getLength()
• void print( )

The template contains the required code to test your implementation. Find text //Your code here inside Dequeue.java and use the methods from LinkedListForDeque.java to implement the methods above.

CLASS DEQUEUE__________________(change this) public class Dequeue { LinkedListForDeque list = new LinkedListForDeque(); public void pushFront(int item) { list.prepend(item); } public void pushBack(int item) { list.append(item); } public int popFront() { // Your code here if(!list.isEmpty()) { int removedNumber; removedNumber = list.get(0); list.removeFirst(); } return removedNumber; } public int popBack() { // Your code here if(!list.isEmpty()) { list.removeLast(); } return list.get(getLength()); }

public int peekFront() { // Your code here Node firstNode = null; if(!list.isEmpty()) { firstNode = list.removeFirst(); int data = firstNode.data; list.prepend(data); return data; } else { return -1; } } public int peekBack() { // Your code here Node lastNode = null; if(!list.isEmpty()) { lastNode = list.removeLast(); int data = lastNode.data; list.append(data); return data; } else { return -1; } } public int getLength() { // Your code here return list.length(); } public void print() { list.print(); } public boolean isEmpty() { // Your code here return list.isEmpty(); } }

CLASS LINKEDLISTFORDQQUE________________________

public class LinkedListForDeque { Node head;

// inserts data to the end of the list only using the head pointer public void append(int data){ Node newNode = new Node(data); if(head == null){ head = newNode;

} else { Node currentNode = head; while(currentNode.next != null){ currentNode = currentNode.next; } currentNode.next = newNode; } } // inserts data to the beginning of the list public void prepend(int data){ if(head == null){ Node newNode = new Node(data); head = newNode; return; } Node newNode = new Node(data); newNode.next = head; head = newNode; } // print the linked list elements public void print() { Node currentNode = head; if(head == null) { System.out.println("Empty!"); return; } System.out.printf("["); while (currentNode.next != null) { System.out.printf("%d, ", currentNode.data); currentNode = currentNode.next; } System.out.printf("%d]%n", currentNode.data); } // counts the length of the list public int length(){ int length = 0; Node currentNode = head; while(currentNode != null){ length++; currentNode = currentNode.next; } return length; } public boolean isEmpty() { return length() == 0; } // get an item from the list specified by the index public int get(int index){ int len = length(); if(index > len){ return -1; } Node currentNode = head; int currentIndex = 0; while(currentNode != null){ if(index == currentIndex){ return currentNode.data; } else{ currentNode = currentNode.next; currentIndex++; } } return -1; }

// insert a new data after the given one public void insertAfter(int givenData, int newData){ Node newNode = new Node(newData); if(head == null){ head = newNode; return; } else{ Node currentNode = head; while(currentNode != null){ if(currentNode.data == givenData){ newNode.next = currentNode.next; currentNode.next = newNode; break; } else{ currentNode = currentNode.next; } } } }

// Removes the Node with the given data public void remove(int current) { Node currentNode = head;

if (head.data == current) { head = currentNode.next; return; } else { while (currentNode.next != null) { Node nextNode = currentNode.next; if (nextNode.data == current) { currentNode.next = currentNode.next.next; break; } else { currentNode = currentNode.next; }

} }

} }

CLASS NODE

class Node{ int data; Node next; public Node(int data){ this.data = data; } }

C:ASS DEQUEUETEST___________________________

import java.util.Scanner;

public class DequeueTest { public static void main(String[] args) { Dequeue dequeue = new Dequeue(); Scanner input = new Scanner(System.in); System.out.println("Enter integers to insert into the Deque (-1 to end)"); while(true) { int number = input.nextInt(); if(number == -1) break; if(number % 2 == 1) dequeue.pushFront(number); else dequeue.pushBack(number); } input.close(); System.out.printf("Deque contains %d items%n", dequeue.getLength()); System.out.printf("Printing the dequeue items:"); dequeue.print(); System.out.printf("Popping from the front!:%d%n", dequeue.popFront()); System.out.printf("Popping from the back!:%d%n", dequeue.popBack()); System.out.printf("Now the dequeue contains %d item(s): ", dequeue.getLength()); dequeue.print(); System.out.printf("%nThe first element is %d%n", dequeue.peekFront()); System.out.printf("The last element is %d%n", dequeue.peekBack()); System.out.printf("Is the dequeue empty? %s%n", dequeue.isEmpty() ? "Yes" : "No"); } }