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.
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.
UML class diagram: see image.
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.
*
* @author (add here name and Panther ID)
*/
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) {
}
/*
* 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) {
}
/*
* 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() {
}
/*
* 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() {
}
/*
* 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() {
}
/*
* 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() {
}
/*
* Constructs a String description of the deque.
*
* @return String containing the deque elements.
*/
@Override
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
/*
* Return value of methods getBack and getFront in the Deque class.
*/
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() {
}
public int getInfo() {
}
public Node getNext() {
}
public Node getPrev() {
}
public void setInfo(int i) {
}
public void setNext(Node n) {
}
public void setPrev(Node p) {
}
}
assignment 2 test set.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