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...
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...
Discuss the queue data structure. What are its unique structural and behavioral concepts? What are its...
- There are a large number of tasks involved in information technology and programming, and many of...
- Using one quantitative and one qualitative health policy research method described in this chapter, design a...
- What is the Rawls' solution to the age-old question of social (economic / distributive) justice?...
- St. Johns River Shipyards' welding machine is 15 years old, fully depreciated, and has no salvage...
- The following information is available for Robstown Corporation for 20Y8: Inventories January 1 December 31 Materials...
- /* Complete the TO DO comments below */ window.onload = function() { /* TODO add a...
- Trevor Price bought 10-year bonds issued by Harvest Foods five years ago for $4,532.35. The bonds...