Question
In: Computer Science
Topic: Students will be able to create skills in the use of linked lists, the stack,...
Topic: Students will be able to create skills in the use of linked lists, the stack, and the queue abstract data types, by implementing solutions to fundamental data structures and associated problems.
Add the code for the methods where it says to implement. The main class is already done. There is a sample of the output.
1. A double-ended queue, or deque, is a data structure consisting of a list of items on which the following operations are defined:
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 a doubly linked list implementation.
|
Node |
|
-int info -Node next -Node prev |
|
+Node() +int getInfo() +Node getNext() +Node getPrev() +void setInfo(int i) +void setNext(Node n) +void setPrev(Node p) |
UML class diagram:
|
Deque |
|
-int count -Node back -Node front |
|
+Deque() +void addToBack(int x) +void addToFront(int x) +DequeItem getBack() +DequeItem getFront() +boolean isEmpty() +boolean removeBack() +boolean removeFront() +String toString() |
|
DequeItem |
|
+boolean valid +int item |
|
+DequeItem() +DequeItem(boolean v, int i) |
|
Main |
|
+static void main(String[] args) +Main() |
testset.txt
IS_EMPTY
ADD_TO_BACK 1
IS_EMPTY
ADD_TO_BACK 2
ADD_TO_BACK 3
GET_BACK
GET_FRONT
ADD_TO_FRONT 4
ADD_TO_FRONT 5
ADD_TO_FRONT 6
ADD_TO_BACK 7
GET_BACK
GET_FRONT
REMOVE_FRONT
REMOVE_BACK
GET_FRONT
GET_BACK
ADD_TO_BACK 8
ADD_TO_BACK 9
ADD_TO_FRONT 10
ADD_TO_BACK 11
ADD_TO_BACK 12
ADD_TO_BACK 0
REMOVE_BACK
REMOVE_BACK
ADD_TO_BACK 0
REMOVE_FRONT
REMOVE_FRONT
REMOVE_FRONT
REMOVE_FRONT
REMOVE_FRONT
REMOVE_FRONT
REMOVE_FRONT
REMOVE_FRONT
REMOVE_FRONT
REMOVE_FRONT
REMOVE_FRONT
Deque.java
public class Deque
{
/**
* Default constructor. Sets this object as an empty deque.
*
*/
public Deque()
{
front = new Node();
back = new Node();
front.setNext(back);
back.setPrev(front);
count = 0;
}
/**
* 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.
*/
public void addToBack(int x)
{
//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.
*/
public void addToFront(int x)
{
//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()
{
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 str = "";
Node current = front.getNext();
for (int i = 0; i < count - 1; i++)
{
str += current.getInfo() + ", ";
current = current.getNext();
}
if (count != 0)
return "Deque: [" + str + back.getPrev().getInfo() + "]";
else
return "Deque: []";
}
private int count; //number of elements in the deque
private Node back; //points to the item in the back
private Node front; //points to the item in the front
}
DequeItem.java
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
}
Main.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
/**
* Tester class.
*/
public class Main
{
public static void main(String[] args)
{
new Main();
}
/**
* Tester method.
*/
public Main()
{
Deque deque = new Deque();
File file = new File("assignment 2 test set.txt");
try
{
Scanner in = new Scanner(file);
String operation;
int item = 0;
int entryNumber = 0;
while (in.hasNextLine())
{
entryNumber++;
operation = in.next();
if (operation.equals("ADD_TO_BACK") || operation.equals("ADD_TO_FRONT"))
{
item = in.nextInt();
System.out.println("\n" + operation + " " + item);
}
else
System.out.println("\n" + operation);
DequeItem result;
switch (operation)
{
case "ADD_TO_BACK":
deque.addToBack(item);
System.out.println(deque);
break;
case "ADD_TO_FRONT":
deque.addToFront(item);
System.out.println(deque);
break;
case "GET_BACK":
result = deque.getBack();
if (result.valid)
System.out.println("Back item: " + result.item);
else
System.out.println("Cannot retrieve value, deque is empty!");
break;
case "GET_FRONT":
result = deque.getFront();
if (result.valid)
System.out.println("Front item: " + result.item);
else
System.out.println("Cannot retrieve value, deque is empty!");
break;
case "IS_EMPTY":
System.out.println(deque.isEmpty());
break;
case "REMOVE_BACK":
if (deque.removeBack())
System.out.println(deque);
else
System.out.println("Cannot remove, deque is empty!");
break;
case "REMOVE_FRONT":
if (deque.removeFront())
System.out.println(deque);
else
System.out.println("Cannot remove, deque is empty!");
break;
default:
System.out.println("Operation \"" + operation + "\" unknown at line " + entryNumber);
System.exit(1);
}
}
} catch (FileNotFoundException e)
{
System.out.println("File not found!");
System.exit(1);
}
}
}
Node.java
/**
* Implements the node of a doubly linked list of integers.
*/
public class Node
{
private int info;
private Node next;
private Node prev;
public Node()
{
//TO IMPLEMENT
}
public int getInfo()
{
return -1; //DUMMY CODE; TO IMPLEMENT
}
public Node getNext()
{
return null; //DUMMY CODE; TO IMPLEMENT
}
public Node getPrev()
{
return null; //DUMMY CODE; TO IMPLEMENT
}
public void setInfo(int i)
{
//TO IMPLEMENT
}
public void setNext(Node n)
{
//TO IMPLEMENT
}
public void setPrev(Node p)
{
//TO IMPLEMENT
}
}
Output
run:
IS_EMPTY true
ADD_TO_BACK 1 Deque: [1]
IS_EMPTY false
ADD_TO_BACK 2 Deque: [1, 2]
ADD_TO_BACK 3 Deque: [1, 2, 3]
GET_BACK Back item: 3
GET_FRONT Front item: 1
ADD_TO_FRONT 4 Deque: [4, 1, 2, 3]
ADD_TO_FRONT 5 Deque: [5, 4, 1, 2, 3]
ADD_TO_FRONT 6 Deque: [6, 5, 4, 1, 2, 3]
ADD_TO_BACK 7 Deque: [6, 5, 4, 1, 2, 3, 7]
GET_BACK Back item: 7
GET_FRONT Front item: 6
REMOVE_FRONT Deque: [5, 4, 1, 2, 3, 7]
REMOVE_BACK Deque: [5, 4, 1, 2, 3]
GET_FRONT Front item: 5
GET_BACK Back item: 3
ADD_TO_BACK 8 Deque: [5, 4, 1, 2, 3, 8]
ADD_TO_BACK 9 Deque: [5, 4, 1, 2, 3, 8, 9]
ADD_TO_FRONT 10 Deque: [10, 5, 4, 1, 2, 3, 8, 9]
ADD_TO_BACK 11 Deque: [10, 5, 4, 1, 2, 3, 8, 9, 11]
ADD_TO_BACK 12 Deque: [10, 5, 4, 1, 2, 3, 8, 9, 11, 12]
ADD_TO_BACK 0 Deque: [10, 5, 4, 1, 2, 3, 8, 9, 11, 12, 0]
REMOVE_BACK Deque: [10, 5, 4, 1, 2, 3, 8, 9, 11, 12]
REMOVE_BACK Deque: [10, 5, 4, 1, 2, 3, 8, 9, 11]
ADD_TO_BACK 0 Deque: [10, 5, 4, 1, 2, 3, 8, 9, 11, 0]
REMOVE_FRONT Deque: [5, 4, 1, 2, 3, 8, 9, 11, 0]
REMOVE_FRONT Deque: [4, 1, 2, 3, 8, 9, 11, 0]
REMOVE_FRONT Deque: [1, 2, 3, 8, 9, 11, 0]
REMOVE_FRONT Deque: [2, 3, 8, 9, 11, 0]
REMOVE_FRONT Deque: [3, 8, 9, 11, 0]
REMOVE_FRONT Deque: [8, 9, 11, 0]
REMOVE_FRONT Deque: [9, 11, 0]
REMOVE_FRONT Deque: [11, 0]
REMOVE_FRONT Deque: [0]
REMOVE_FRONT Deque: []
REMOVE_FRONT Cannot remove, deque is empty! BUILD SUCCESSFUL (total time: 0 seconds)
I already included the skeletons for most of the classes. All I need is the code for the few methods where it says implement. I would really appreciate it if this could be done by tonight. I've posted this question three times and have gotten no response.
Solutions
Expert Solution
// DequeItem.java
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
}
//end of DequeItem.java
// Node.java
/**
* Implements the node of a doubly linked list of integers.
*/
public class Node
{
private int info;
private Node next;
private Node prev;
// default constructor
public Node()
{
info = 0;
next = null;
prev = null;
}
// getters
public int getInfo()
{
return info;
}
public Node getNext()
{
return next;
}
public Node getPrev()
{
return prev;
}
// setters
public void setInfo(int i)
{
info = i;
}
public void setNext(Node n)
{
next = n;
}
public void setPrev(Node p)
{
prev = p;
}
}
// end of Node.java
// Deque.java
public class Deque
{
/**
* Default constructor. Sets this object as an empty
deque.
*
*/
public Deque()
{
front = new Node();
back = new Node();
front.setNext(back);
back.setPrev(front);
count = 0;
}
/**
* 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.
*/
public void addToBack(int x)
{
// create a new node for x
Node node = new Node();
node.setInfo(x);
// set next of node to back
node.setNext(back);
// set previous last node's next to
node
back.getPrev().setNext(node);
// set prev of node to previous
last node
node.setPrev(back.getPrev());
// set prev of back to node
back.setPrev(node);
count++; // increment count
}
/**
* 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.
*/
public void addToFront(int x)
{
// create a new node for x
Node node = new Node();
node.setInfo(x);
// set prev of node to front
node.setPrev(front);
// set next of node to previous
first node
node.setNext(front.getNext());
// set prev of previous first node
to node
node.getNext().setPrev(node);
// set next of front to node
front.setNext(node);
count++; // increment count
}
/**
* 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()
{
DequeItem item;
if(!isEmpty()) // not empty
item = new
DequeItem(true, back.getPrev().getInfo());
else // empty
item = new
DequeItem();
return item;
}
/**
* 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()
{
DequeItem item;
if(!isEmpty()) // not empty
item = new
DequeItem(true, front.getNext().getInfo());
else // empty
item = new
DequeItem();
return item;
}
/**
* Determines if deque is empty. The method takes O(1)
time.
*
* @return true if deque contains no elements, false
otherwise.
*/
public boolean isEmpty()
{
return count == 0;
}
/**
* 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()
{
if(!isEmpty()) // not empty
{
// set prev of
back to second last node
back.setPrev(back.getPrev().getPrev());
// update next
of last node to back
back.getPrev().setNext(back);
count--; //
decrement count
return
true;
}
return false;
}
/**
* 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()
{
if(!isEmpty()) // not empty
{
// set next of
front to second node
front.setNext(front.getNext().getNext());
front.getNext().setPrev(front); // update prev of new first node to
front
count--; //
decrement count by 1
return
true;
}
return false;
}
/**
* Constructs a String description of the deque.
*
* @return String containing the deque elements.
*/
public String toString()
{
String str = "";
Node current =
front.getNext();
for (int i = 0; i < count - 1;
i++)
{
str +=
current.getInfo() + ", ";
current =
current.getNext();
}
if (count != 0)
return "Deque:
[" + str + back.getPrev().getInfo() + "]";
else
return "Deque:
[]";
}
private int count; //number of elements in the
deque
private Node back; //points to the item in the
back
private Node front; //points to the item in the
front
}
// end of Deque.java
// Main.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
/**
* Tester class.
*/
public class Main
{
public static void main(String[] args)
{
new Main();
}
/**
* Tester method.
*/
public Main()
{
Deque deque = new Deque();
File file = new File("assignment 2
test set.txt");
try
{
Scanner in = new
Scanner(file);
String
operation;
int item =
0;
int entryNumber
= 0;
while
(in.hasNextLine())
{
entryNumber++;
operation = in.next();
if (operation.equals("ADD_TO_BACK") ||
operation.equals("ADD_TO_FRONT"))
{
item = in.nextInt();
System.out.println("\n" +
operation + " " + item);
}
else
System.out.println("\n" +
operation);
DequeItem result;
switch (operation)
{
case "ADD_TO_BACK":
deque.addToBack(item);
System.out.println(deque);
break;
case "ADD_TO_FRONT":
deque.addToFront(item);
System.out.println(deque);
break;
case "GET_BACK":
result =
deque.getBack();
if
(result.valid)
System.out.println("Back item: " +
result.item);
else
System.out.println("Cannot retrieve value, deque
is empty!");
break;
case "GET_FRONT":
result =
deque.getFront();
if
(result.valid)
System.out.println("Front item: " +
result.item);
else
System.out.println("Cannot retrieve value, deque
is empty!");
break;
case "IS_EMPTY":
System.out.println(deque.isEmpty());
break;
case "REMOVE_BACK":
if
(deque.removeBack())
System.out.println(deque);
else
System.out.println("Cannot remove, deque is
empty!");
break;
case "REMOVE_FRONT":
if
(deque.removeFront())
System.out.println(deque);
else
System.out.println("Cannot remove, deque is
empty!");
break;
default:
System.out.println("Operation \"" + operation + "\" unknown at line
" + entryNumber);
System.exit(1);
}
}
} catch (FileNotFoundException
e)
{
System.out.println("File not found!");
System.exit(1);
}
}
}
// end of Main.java
Output:
Input file:
Output:
venereology answered 11 months agoRelated Solutions
Skills needed to complete this assignment: linked lists, stacks. Postfix notation, is a mathematical notation in...
In C++ Use vectors instead of linked lists Create a Hash table program using H(key) =...
Using C++, you will create a program, where you will create two doubly linked lists. These...
In python i want to create a function. The function will take in two linked lists...
C++ Linked Lists Practice your understanding of linked lists in C++ by creating a list of...
The goal of this assignment is to implement a set container using linked lists. Use the...
6.9 Lab: Singly-Linked Lists As an entry-level programmer you have to be able to read, understand...
Suppose you are given two circularly linked lists, L and M. Create an algorithm for telling...
Write a code to implement a python stack class using linked list. use these operations isEmpty...
Given an array of Student type and size 10, create a linked list of students by...
- I have a question about difference between physical observables and eigenstates in quantum mechanics it is...
- in regard to seeing improvement in a child behavior, do you think there are other influences...
- Cash Budget The controller of Bridgeport Housewares Inc. instructs you to prepare a monthly cash budget...
- 6. Distillation: Why do we need reflux to return back to distillation columns? How the reflux...
- (d) A company has got “low” in all five forces when performing Porter’s Five Forces Model...
- Charles deposited $12,000 in the bank. He withdrew $5000 from his account after one year. If...
- 1) Does mass media have an influence on violent behavior? 2) How can we heal from...