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");

}