Stacks and queues with linked lists in Java No additional fields or static varia
ID: 3834933 • Letter: S
Question
Stacks and queues with linked lists in Java
No additional fields or static variables can be added.
Method declarations cannot be changed.
Loops and recursion cannot be used unless otherwise specified.
I've worked on this code and left what I've come up with below method declarations. My code does not work properly, can you help?
Thanks!!
public class MyDeque {
Node first = null;
Node last = null;
int N = 0;
static class Node {
public Node() { }
public double item;
public Node next;
public Node prev;
}
public MyDeque () { };
public boolean isEmpty () { return N == 0; }
public int size () { return N; }
public void pushLeft (double item) {
// TODO
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
first.prev = null;
if (last == null) {
last = first;
}
// oldfirst.prev = first;
N++;
}
public void pushRight (double item) {
// TODO
if (last == null) {
first = new Node ();
last = first;
}
last = last.next;
N++;
}
public double popLeft () {
if (N == 0) throw new NoSuchElementException ();
// TODO
Node r = first;
if (first == last) {
last = null;
}
first = first.next;
N--;
return r.item;
}
public double popRight () {
if (N == 0) throw new NoSuchElementException ();
// TODO
}
/* The concat method should take the Nodes from "that" and add them to "this"
* After execution, "that" should be empty.
* See the tests in the main program.
*
* Do not use a loop or a recursive definition.
* This method should create no new Nodes;
* therefore it should not call pushLeft or pushRight.
*/
public void concat (MyDeque that) {
// TODO
this.last.next = that.first;
last = that.last;
N = N + that.N;
}
/* Delete should delete and return the kth element from the left (where k is between 0 and N-1).
* See the tests in the main program.
*
* You may use a loop or a recursive definition here.
* This method should create no new Nodes;
* therefore it should not call pushLeft or pushRight.
*/
public double delete (int k) {
if (k < 0 || k >= N) throw new IllegalArgumentException ();
// TODO
// prev.next = next;
}
Some tests:
////////////////////////////////////////////////////////////////////
// test exceptions
////////////////////////////////////////////////////////////////////
try {
d1.popLeft ();
showError ("Expected exception");
} catch (NoSuchElementException e) {}
try {
d1.popRight ();
showError ("Expected exception");
} catch (NoSuchElementException e) {}
////////////////////////////////////////////////////////////////////
// concat tests (and more push/pop tests)
////////////////////////////////////////////////////////////////////
d1 = new MyDeque ();
d1.concat (new MyDeque ());
check ("concat", d1, "[ ]");
d1.pushLeft (11);
d1.concat (new MyDeque ());
check ("concat", d1, "[ 11 ]");
d1 = new MyDeque ();
d2 = new MyDeque ();
d2.pushLeft (11);
d1.concat (d2);
check ("concat", d1, "[ 11 ]");
d1 = new MyDeque ();
d2 = new MyDeque ();
d1.pushLeft (11);
d1.pushLeft(12);
d2.pushLeft (21);
d2.pushLeft(22);
d1.concat (d2);
check ("concat", d1, "[ 12 11 22 21 ]");
check ("concat", d1, "[ ]");
d1 = new MyDeque ();
for (int i = 10; i < 15; i++) { d1.pushLeft (i); checkInvariants ("left", d1); }
for (int i = 20; i < 25; i++) { d1.pushRight (i); checkInvariants ("right", d1); }
check ("concat", d1, "[ 14 13 12 11 10 20 21 22 23 24 ]");
d2 = new MyDeque ();
d1.concat (d2);
check ("concat", d1, "[ 14 13 12 11 10 20 21 22 23 24 ]");
check ("concat", d2, "[ ]");
for (int i = 30; i < 35; i++) { d2.pushLeft (i); checkInvariants ("left", d2); }
for (int i = 40; i < 45; i++) { d2.pushRight (i); checkInvariants ("right", d2); }
check ("concat", d2, "[ 34 33 32 31 30 40 41 42 43 44 ]");
d3 = new MyDeque ();
d2.concat (d3);
check ("concat", d2, "[ 34 33 32 31 30 40 41 42 43 44 ]");
check ("concat", d3, "[ ]");
d1.concat (d2);
check ("concat", d1, "[ 14 13 12 11 10 20 21 22 23 24 34 33 32 31 30 40 41 42 43 44 ]");
check ("concat", d2, "[ ]");
for (int i = 0; i < 20; i++) { d1.popLeft (); checkInvariants ("left", d1); }
////////////////////////////////////////////////////////////////////
// delete tests
////////////////////////////////////////////////////////////////////
d1 = new MyDeque ();
d1.pushLeft (11);
k = d1.delete (0);
check ("delete", d1, "[ ]", k, 11);
for (int i = 10; i < 20; i++) { d1.pushRight (i); checkInvariants ("right", d1); }
k = d1.delete (0);
check ("delete", d1, "[ 11 12 13 14 15 16 17 18 19 ]", k, 10);
k = d1.delete (8);
check ("delete", d1, "[ 11 12 13 14 15 16 17 18 ]", k, 19);
k = d1.delete (4);
check ("delete", d1, "[ 11 12 13 14 16 17 18 ]", k, 15);
StdOut.println ("Finished tests");
}
Explanation / Answer
Hi, Please find my complete implementation.
Please let me know in case of any issue.
import java.util.NoSuchElementException;
public class MyDeque {
Node first = null;
Node last = null;
int N = 0;
static class Node {
public Node(double data) {
item = data;
next = null;
prev = null;
}
public double item;
public Node next;
public Node prev;
}
public MyDeque () { };
public boolean isEmpty () { return N == 0; }
public int size () { return N; }
public void pushLeft (double item) {
// TODO
Node oldfirst = first;
first = new Node(item);
first.next = oldfirst;
first.prev = null;
if (last == null) {
last = first;
}
if(oldfirst != null)
oldfirst.prev = first;
N++;
}
public void pushRight (double item) {
// TODO
if (last == null) {
first = new Node (item);
last = first;
}else{
Node newNode = new Node(item);
last.next = newNode;
newNode.prev = last;
last = newNode;
}
N++;
}
public double popLeft () {
if (N == 0) throw new NoSuchElementException ();
// TODO
Node r = first;
if (first == last) {
last = null;
first = null;
}else{
first = first.next;
first.prev = null;
}
N--;
return r.item;
}
public double popRight () {
if (N == 0) throw new NoSuchElementException ();
// TODO
Node r = last;
if(first == last){
first = null;
last = null;
}else{
last = last.prev;
last.next = null;
}
return r.item;
}
/* The concat method should take the Nodes from "that" and add them to "this"
* After execution, "that" should be empty.
* See the tests in the main program.
*
* Do not use a loop or a recursive definition.
* This method should create no new Nodes;
* therefore it should not call pushLeft or pushRight.
*/
public void concat (MyDeque that) {
// TODO
if(last == null){
this.first = that.first;
this.last = that.last;
}else{
this.last.next = that.first;
last = that.last;
}
N = N + that.N;
}
/* Delete should delete and return the kth element from the left (where k is between 0 and N-1).
* See the tests in the main program.
*
* You may use a loop or a recursive definition here.
* This method should create no new Nodes;
* therefore it should not call pushLeft or pushRight.
*/
public double delete (int k) {
if (k < 0 || k >= N) throw new IllegalArgumentException ();
// TODO
// prev.next = next;
Node toDelete;
if(k == 0){ // deleting first element
toDelete = first;
first = first.next;
if(first == null) // if there was only one element
last = null;
else
first.prev = null;
}else if(k == N-1){
toDelete = last;
if(first == last){
first = null;
last = null;
}else{
last = last.prev;
last.next = null;
}
}else{
Node temp = first;
int i = 0;
while(i < N){
temp = temp.next;
}
toDelete = temp;
toDelete.prev.next = toDelete.next;
toDelete.next.prev = toDelete.prev;
toDelete.next = null;
toDelete.prev= null;
}
N = N-1;
return toDelete.item;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.