Question
In: Computer Science
1. A double-ended queue, or deque, is a data structure consisting of a list of items...
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)
Solutions
Expert Solution
Answer:
Input file:
Code:
// Node.java
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
/**
* The class Deque implements a double-ended queue with a doubly
linked list.
* The list uses a header and a trailer (dummy) nodes.
*/
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
Output:
venereology answered 2 years agoRelated Solutions
A deque is a data structure consisting of a list of items, on which the following...
Study and implement data structure deque (double ended queue, pronounced as "deck"). IN C++ PLEASE
A deque (short for double-ended queue, but pronounced “deck”) is an abstract data type that supports...
Create a Deque class based on the following description of deque (double-ended queues). A dequeue is...
Python: Solve following problems using Linked List Data Structure 2. Create a Queue class. In the...
C++ PROGRAM Code a generic (with templates) Queue structure (linear Data structure with FIFO functionality) and...
Solve in C++ program. Modify the use of queue data structure such that the array used...
In Java or C++, implement a stack and a queue using a linkedlist data structure. You may...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you...
Discuss the queue data structure. What are its unique structural and behavioral concepts? What are its...
- “Triangle Guessing” game in Python The program accepts the lengths of three (3) sides of a...
- THIS PROGRAM HAS TO BE WRITTEN IN C Single function to perform the parity computation on...
- Consider a buffer system consisting of Benzoic acid (pKa = 4.20) and sodium benzoate, a) Would...
- Decision Variables S T Minimize 1.8S + 2.20T Subject to: Potassium 5S + 8T >= 200...
- A neurologist needs to counsel a stroke victim and her husband about possible outcomes, treatment options,...
- Case Study: Personal Beliefs in the Workplace Don Shakow was a prominent professional who worked in...
- 1: Competency framework usage is the modern best practice in management. What is meant by competency...