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:


Related Solutions

A deque is a data structure consisting of a list of items, on which the following...
A deque is a data structure consisting of a list of items, on which the following operations are possible: • push(x): Insert item x on the front end of the deque. • pop(): Remove the front item from the deque and return it. • inject(x): Insert item x on the rear end of the deque. • eject(): Remove the rear item from the deque and return it. Write routines to support the deque that take O(1) time per operation. In...
Study and implement data structure deque (double ended queue, pronounced as "deck"). IN C++ PLEASE
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...
A deque (short for double-ended queue, but pronounced “deck”) is an abstract data type that supports adding and removing at both the front and back. So, at a bare minimum, a deque has four operations: addFront(), removeFront(), addBack(), removeBack(). Suppose you have a deque D containing the numbers (1, 2, 3, 4, 5, 6, 7, 8), in this order. Suppose further that you have an initially empty queue Q. Give pseudo-code description of a method that uses only D and...
Create a Deque class based on the following description of deque (double-ended queues). A dequeue is...
Create a Deque class based on the following description of deque (double-ended queues). A dequeue is a double-ended queue. You can insert items at either end and delete them from either end. Therefore, the deque offers two insert operations and two remove operations: insertLeft() and insertRight() removeLeft() and removeRight(). Deques may also have "peek" methods ( peekLeft() and peekRight() )that let you see the left or right item in the deque without remove the item from the deque. For this...
Python: Solve following problems using Linked List Data Structure 2. Create a Queue class. In the...
Python: Solve following problems using Linked List Data Structure 2. Create a Queue class. In the queue class create enqueue, dequeue, first, empty, len and resize methods. The class should support circular queue and have the ability to resize the queue.
C++ PROGRAM Code a generic (with templates) Queue structure (linear Data structure with FIFO functionality) and...
C++ PROGRAM Code a generic (with templates) Queue structure (linear Data structure with FIFO functionality) and create a test to validate its functionality. The data consists of persons with the attributes of name, last name, age, height and weight. - Remembrer that, Their structure consists of: Head: Pointer to the first element of the queue Tail: Pointer to the last element of the queue And the following operations: Pop: Removes the element at the head Top: Returns the current element...
Solve in C++ program. Modify the use of queue data structure such that the array used...
Solve in C++ program. Modify the use of queue data structure such that the array used to implement the queue is dynamically allocated for a fast food autoservice
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you will implement the functionality of a stack and a queue using a linked list. Your program must use of the declaration of the Stack and Queue class in Stack.h and Queue.h You have to implement the functionalities of queue (enq, deq, displayQueue) in a file called Queue.cpp. All the functions in Queue.cpp should follow the prototypes declared in Queue.h. Your code should make use...
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 most frequently used methods? What implementations are provided? What practical applications does it support? Discuss the priority queue variant.
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 most frequently used methods? What implementations are provided? What practical applications does it support? Discuss the priority queue variant.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT