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 1 year ago
Next > < Previous

Related Solutions

Skills needed to complete this assignment: linked lists, stacks. Postfix notation, is a mathematical notation in...
Skills needed to complete this assignment: linked lists, stacks. Postfix notation, is a mathematical notation in which operators follow their operands; for instance, to add 3 and 4, one would write 3 4 + rather than 3 + 4 (infix notation). If there are multiple operations, operators are given immediately after their second operands; so, the expression written 3 − 4 + 5 in conventional notation would be written 3 4 − 5 + in postfix notation: 4 is first...
In C++ Use vectors instead of linked lists Create a Hash table program using H(key) =...
In C++ Use vectors instead of linked lists Create a Hash table program using H(key) = key%tablesize with Chaining and Linear probing for a text file that has a list of 50 numbers Ask the user to enter the file name, what the table size is, and which of the two options they want to use between chaining and linear probing
Using C++, you will create a program, where you will create two doubly linked lists. These...
Using C++, you will create a program, where you will create two doubly linked lists. These doubly linked lists will contain integers within them. Using the numbers in both of these linked lists, you add the numbers together, and insert the addition of the two numbers into a singly linked list. the input can be from the user or you just write the input. for example, if one number in the doubly linked list is 817 and in the other...
In python i want to create a function. The function will take in two linked lists...
In python i want to create a function. The function will take in two linked lists as the parameters. If one is shorter than the other then the shorter will be the length. I want to take the values from both linked lists and turn them into tuples. I then want these tuples to be put into a new linked list. I want to return that linked list. I want to do this using recursion and no helper functions or...
C++ Linked Lists Practice your understanding of linked lists in C++ by creating a list of...
C++ Linked Lists Practice your understanding of linked lists in C++ by creating a list of songs/artist pairs. Allow your user to add song / artist pairs to the list, remove songs (and associated artist) from the list and be sure to also write a function to print the list! Have fun! Make sure you show your implementation of the use of vectors in this lab (You can use them too ) You MUST modularize your code ( meaning, there...
2.1 Linked Lists Linked lists are an example of an unbound data structure. Whereas the array...
2.1 Linked Lists Linked lists are an example of an unbound data structure. Whereas the array is based around having a fixed size per array creation, there is no logical limit on the ability of a linked list to grow. Physical limitations aside, linked lists are capable of growing largely without any limitations. To achieve this, they trade easier access to their individual elements. This is because linked lists have to be traversed from their root node to any node...
JAVA Stack - Implementation. You will be able to use the push, pop and peek of...
JAVA Stack - Implementation. You will be able to use the push, pop and peek of Stack concept. Post-Fix calculator - When an arithmetic expression is presented in the postfix form, you can use a stack to evaluate the expression to get the final value. For example: the expression 3 + 5 * 9 (which is in the usual infix form) can be written as 3 5 9 * + in the postfix. More interestingly, post form removes all parentheses...
6.9 Lab: Singly-Linked Lists As an entry-level programmer you have to be able to read, understand...
6.9 Lab: Singly-Linked Lists As an entry-level programmer you have to be able to read, understand existing code and update it (add new features). One of this assignment’s goals is to read about 400 lines of code in five files, compile and run the program, understand it, and change it as required. Download and review the following files (read code and all comments carefully): College.h College.cpp LinkedList.h LinkedList.cpp main.cpp --------------------------------------------------------- //colleges.txt 3 SBCC Santa Barbara City College; 18524 97 ZZC...
The goal of this assignment is to implement a set container using linked lists. Use the...
The goal of this assignment is to implement a set container using linked lists. Use the authors bag3.h and bag3.cpp as a basis for implementing your set container using linked lists. The authors bag3.h and bag3.cpp can be found here https://www.cs.colorado.edu/~main/chapter5/ Since you are using the authors bag3.h and bag3.cpp for your Set container implementation, make sure that you change the name of the class and constructors to reflect the set class. Additionally you will need to implement the follow...
A Lecturer wishes to create a program that lists his students sorted by the number of...
A Lecturer wishes to create a program that lists his students sorted by the number of theory assignment marks they have completed. The listing should be greatest number of assignment first, sub-sorted by name in lexicographical order (A to Z). A class Student stores the name and marks of assignment completed for a student.                                                    [5 marks] Note: Assume the variable name of collection is list.       i.         Provide a definition of Student with an equals() method. The comparison is based...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT