Java-Netbeans Skeleton

Deque:

import java.util.Arrays;

/** * The class Deque implements an array-based double-ended queue. public class Deque {

int SIZE; int[] list; int front; int rear; int count;

/** * Default constructor. Initial deque capacity is 10. * */ public Deque() { this.SIZE = 10; this.list = new int[this.SIZE]; this.front = -1; this.rear = -1; this.count = 0;

//TO IMPLEMENT }

/** * Parameterized constructor. Initial deque capacity is "size". * */ public Deque(int size) { this.SIZE = size; this.list = new int[this.SIZE]; this.front = -1; this.rear = -1; this.count = 0; //TO IMPLEMENT }

/** * Adds new element to the back end of the deque. The method takes O(1) * time. * * @param x new element to be added to the deque. * @return false if addition cannot be performed (i.e. the deque is full), * true otherwise */ public boolean addToBack(int x) { return false; //DUMMY CODE; TO IMPLEMENT }

/** * Adds new element to the front end of the deque. The method takes O(1) * time. * * @param x new element to be added to the deque. * @return false if addition cannot be performed (i.e. the deque is full), * true otherwise */ public boolean addToFront(int x) { return false; //DUMMY CODE; TO IMPLEMENT }

/** * Retrieves element on the back end of the deque. The method takes O(1) * time. * * @return operation is successful: valid = true and item = element on the * back end; operation is unsuccessful (i.e. empty deque): valid = false and * item = dummy value */ public DequeItem getBack() { return new DequeItem(); //DUMMY CODE; TO IMPLEMENT }

/** * Retrieves element on the front end of the deque. The method takes O(1) * time. * * @return operation is successful: valid = true and item = element on the * front end; operation is unsuccessful (i.e. empty deque): valid = false * and item = dummy value */ public DequeItem getFront() { return new DequeItem(); //DUMMY CODE; TO IMPLEMENT }

/** * Determines if deque is empty. The method takes O(1) time. * * @return true if deque contains no elements, false otherwise. */ public boolean isEmpty() { if (this.count == 0) return true; return false; //DUMMY CODE; TO IMPLEMENT }

/** * Determines if deque is full. The method takes O(1) time. * * @return true if deque has reached maximum capacity, false otherwise. */ public boolean isFull() { return false; //DUMMY CODE; TO IMPLEMENT }

/** * Removes element on the back end of the deque. The method takes O(1) time. * * @return false if removal cannot be performed (i.e. the deque is empty), * true otherwise */ public boolean removeBack() { return false; //DUMMY CODE; TO IMPLEMENT }

/** * Removes element on the front end of the deque. The method takes O(1) * time. * * @return false if removal cannot be performed (i.e. the deque is empty), * true otherwise */ public boolean removeFront() { return false; //DUMMY CODE; TO IMPLEMENT }

/** * Constructs a String description of the deque. * * @return String containing the deque elements. */ public String toString() { String[] stringArray = new String[list.length]; Arrays.fill(stringArray, "X");

for (int i = 0; i

return Arrays.toString(stringArray); }

private int back; //points to the last element of the deque private int count; /umber of elements in the deque private int front; //points to the first element of the deque private int[] list; //array that stores the deque elements private int SIZE; //deque capacity }

DequeItem

/** * Return value of methods getBack and getFront in the Deque class. * public class DequeItem {

/** * Default constructor. Sets this object to a invalid deaue item. * */ public DequeItem() { valid = false; item = 0; }

/** * Parameterized constructor. * * @param v value of the "valid" component of this object * @param i value of the "item" component of this object */ public DequeItem(boolean v, int i) { valid = v; item = i; }

public boolean valid; //true if "item" is a valid element, false otherwise public int item; //deque element }

1. (This exercise is a variation of Exercise 3.28 in Chapter 3 of the textbook) A double-ended queue, or deque, is a data structure consisting of a list of items on which the following operations are possible: addToBack(x): insert item x on the back end of the queue addToFront(x): insert item x on the front end of the queue getBack(): returns the element on the back end of the queue getFront(): returns the element on the front end of the queue removeBack(): remove the back item from the queue removeFront(): remove the front item from the queue Write routines to support the deque that take O(1) time per operation. Use an array-based implementation. UML class diagram: Deque Main +static void main(String[] args) +Main() -int back -int count -int front -int[] list -int SIZE +Deque() +Deque(int size) +boolean addToBack(int x) +boolean addToFront(int x) +Dequeltem getBack() +Dequeltem getFront() +boolean isEmpty() +boolean isFull() +boolean removeBack() +boolean removeFront() +String toString() Dequeltem +boolean valid +int item +Dequeltem() +Dequeltem(boolean v, inti) 1. (This exercise is a variation of Exercise 3.28 in Chapter 3 of the textbook) A double-ended queue, or deque, is a data structure consisting of a list of items on which the following operations are possible: addToBack(x): insert item x on the back end of the queue addToFront(x): insert item x on the front end of the queue getBack(): returns the element on the back end of the queue getFront(): returns the element on the front end of the queue removeBack(): remove the back item from the queue removeFront(): remove the front item from the queue Write routines to support the deque that take O(1) time per operation. Use an array-based implementation. UML class diagram: Deque Main +static void main(String[] args) +Main() -int back -int count -int front -int[] list -int SIZE +Deque() +Deque(int size) +boolean addToBack(int x) +boolean addToFront(int x) +Dequeltem getBack() +Dequeltem getFront() +boolean isEmpty() +boolean isFull() +boolean removeBack() +boolean removeFront() +String toString() Dequeltem +boolean valid +int item +Dequeltem() +Dequeltem(boolean v, inti)