From 13cf790b6f0a9a316e2661adf280f72ca80909e9 Mon Sep 17 00:00:00 2001 From: RossTheRoss Date: Thu, 5 Dec 2019 12:00:21 -0600 Subject: Implement enqueue --- csci1913/Java/lab12_strap012.java | 37 +++++++++++++++++++++++++++++-------- 1 file changed, 29 insertions(+), 8 deletions(-) (limited to 'csci1913/Java') diff --git a/csci1913/Java/lab12_strap012.java b/csci1913/Java/lab12_strap012.java index 433f58a..86da35c 100644 --- a/csci1913/Java/lab12_strap012.java +++ b/csci1913/Java/lab12_strap012.java @@ -1,7 +1,7 @@ class PriorityQueue { private class Node { private Base object; - private int rank; + private int rank; private Node left; private Node right; private Node(Base object, int rank) { @@ -19,13 +19,17 @@ class PriorityQueue { return root.right==root.left; } public Base dequeue() { - if (isEmpty()) { + if (isEmpty()) throw new IllegalStateException(); - } else { - Node Test = root.right; - - return Test.object; + Node top = root; + Node bottom = root.right; //First node is always to the right of the root. + while (bottom.right != null) { //Find lowest rank + top = bottom; + bottom = bottom.right; } + + return bottom.object; + } // Unlike the BST’s discussed in the lectures, the nodes in // each left subtree have ranks less than or equal to the @@ -33,10 +37,27 @@ class PriorityQueue { // ranks greater than the rank at the root. // This allows two or more nodes to have the same rank. public void enqueue(Base object, int rank) { - if (rank < 0) { + if (rank < 0) throw new IllegalArgumentException(); + boolean LR = true; + Node top = root; + Node bottom = root.right; + while (bottom != null) { + top = bottom; + if (bottom.rank <= rank) { + bottom = bottom.left; + LR = false; + //LR = true; + } else { + bottom = bottom.right; + LR = true; + //LR = false; + } + } + if (LR) { + top.right = new Node(object, rank); } else { - + top.left = new Node(object, rank); } } -- cgit v1.2.3