Results 1 to 8 of 8

Thread: Need Java help

  1. #1
    Newbie is offline Member
    Join Date
    Feb 2013
    Posts
    4
    Rep Power
    0

    Default Need help with linked queue

    I am very new to java and getting very frustrated I'm almost thinking that a degree in CS might not be for me but I'm going to stick through it . I think I'm just stressing my self out . I have an assignment due soon so I figured I would start early so I can get a 100% on it. I dont expect you guys to give me the answers but just to try and help me out a little and guide me. So for my first question I have to make a function MyDeque() which basically just creates an empty deque. And I also have to make a class pushleft that adds an item to the left end of the deque. So far this is what I have there is more to the assignment but this is what I have so far.
    Java Code:
    import java.util.Iterator;
    
    // Doubly linked version
    public class MyDeque<Item> implements Iterable<Item> {
        
        private Node<Item> first = null;
        private Node<Item> last = null;
        private int N = 0;
        
        private static class Node<Item> {
            Item item;
            Node<Item> next;
            Node<Item> prev;
        }
        
        public MyDeque () { 
        	first = null;
        	last = null;
        	N = 0;
    
    public void pushLeft (Item item) {
        	Node oldfirst = first;
        	first = new Node();
        	first.item = item;
        	first.next = oldfirst;
        	N++;
            
        }
    Last edited by Newbie; 02-09-2013 at 06:37 AM.

  2. #2
    Ronin is offline Senior Member
    Join Date
    Oct 2010
    Posts
    317
    Rep Power
    4

    Default Re: Need Java help

    Hi Newbie, welcome to the forum.

    What exactly is your question?

  3. #3
    Newbie is offline Member
    Join Date
    Feb 2013
    Posts
    4
    Rep Power
    0

    Default Re: Need Java help

    For my Deque() its suppose to create an empty deque and pushleft is suppose to add an item to the left end just making sure im doing this right before i move on. Sorry trying to learn

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,005
    Blog Entries
    7
    Rep Power
    20

    Default Re: Need Java help

    If you're pushing a node on the left of an empty deque you're not updating the 'last' member.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    Newbie is offline Member
    Join Date
    Feb 2013
    Posts
    4
    Rep Power
    0

    Default Re: Need Java help

    But I will have to write code for pushright as well. what is wrong with my pushright function that it doesnt add anything to the linked queue ?

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,005
    Blog Entries
    7
    Rep Power
    20

    Default Re: Need Java help

    Quote Originally Posted by Newbie View Post
    But I will have to write code for pushright as well. what is wrong with my pushright function that it doesnt add anything to the linked queue ?
    I don't see a pushRight( ... ) method but your pushLeft( ... ) method is incorrrect (see my previous reply).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    Newbie is offline Member
    Join Date
    Feb 2013
    Posts
    4
    Rep Power
    0

    Default Re: Need Java help

    Java Code:
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    import java.util.ConcurrentModificationException;
    
    
    
    // 1.3.33 Doubly linked version
    public class MyDeque<Item> implements Iterable<Item> {
        
        // you may need more fields
        private Node<Item> first = null;
        private Node<Item> last = null;
        private int N = 0;
        private int opcount = 0;
        
        private static class Node<Item> {
            Item item;
            Node<Item> next;
            Node<Item> prev;
        }
        
        public MyDeque () { 
        	first = null;
        	last = null;
        	N = 0;
        	opcount = 0;
        	
        	
            //TODO
        }
        public boolean isEmpty () {
        	return first == null;
            //TODO
            
        }
        public int size () {
            //TODO
            return N;
        }
        public void pushLeft (Item item) {
        	if(N==0){
        		Node oldfirst = first;
        		first = new Node();
        		last = first;
        		first.item=item;
        		
        		N++;
        	}
        	else{
        		first.next=last.prev;
        		Node newfirst = first;
        		//first = last;
        		first = new Node();
        		first.item=item;
        		first.next = null;
        		if (last.next == null){
        			last=last.next;
        		}
        		N++;
        	}
        }
        	
            // TODO
        
        public void pushRight (Item item) {
            //TODO
        	
        }
        public Item popLeft () {
            //TODO
            return null;
        }
        public Item popRight () {
            //TODO
            return null;
        }
        // 1.3.50 -- make a fail fast iterator -- it should fail if the Deque is changed after the iterator is created
        public Iterator<Item> iterator ()  { return new ListIterator();  }
    
        	private class ListIterator implements Iterator<Item> {
        		private Node<Item> current = first;
        		public boolean hasNext()  { return current != null;                     }
        		public void remove()      { throw new UnsupportedOperationException();  }
    
        		public Item next() {
        			if (!hasNext()) throw new NoSuchElementException();
        			final Item item = current.item;
        			current = current.next;
        			return item;
        		}
        	}
    
        	
    
        	
        	
            //TODO
            //return null;
        
        // 1.3.47 -- you can destroy "that"
        public void concat (MyDeque<Item> that) {
            //TODO
        }
    
        // delete and return the kth element from the left.
        public Item delete (int k) {
            //TODO
            return null;
        }
    
        // Write a test to ensure that you methods work!
        // Here's some code to start:
        public String toString () {
            if (isEmpty ()) return "[]";
            StringBuilder sb = new StringBuilder ("[");
            Iterator<Item> i = iterator ();
            sb.append (i.next ());
            while (i.hasNext ()) {
                sb.append (" ");
                sb.append (i.next ());
            }
            sb.append ("]");
            return sb.toString ();
        }
        private void check (String expected) {
            if (N < 0) throw new Error ();
            if (N == 0) {
                if (first != null || last != null) throw new Error ();
            } else {
                if (first == null || last == null) throw new Error ();
            }
            if (N > 0) {
                Node<Item> prev = null;
                Node<Item> current = first;
                for (int i = 0; i < N; i++) {
                    //StdOut.println ("checking " + current.item);
                    if (current.prev != prev) throw new Error ();
                    prev = current;
                    current = current.next;
                }
                if (current != null) throw new Error ();
                Node<Item> next = null;
                current = last;
                for (int i = 0; i < N; i++) {
                    //StdOut.println ("checking " + current.item);
                    if (current.next != next) throw new Error ();
                    next = current;
                    current = current.prev;
                }
                if (current != null) throw new Error ();
            }
            if (expected != null) {
                if (!expected.equals (this.toString ())) throw new Error ();
            }
            StdOut.println (this);
        }
        private void check (Item iExpected, Item iActual, String expected) {
            if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\"");
            check (expected);
        }
        public static void main (String args[]) {
            MyDeque<Integer> d1, d2, d3;
            Integer k;
            d1 = new MyDeque<Integer> ();
            d1.pushLeft (11);
            d1.check ("[11]");
            d1.pushLeft (12);
            d1.check ("[12 11]");
            k = d1.popLeft ();
            d1.check (12, k, "[11]");
            k = d1.popLeft ();
            d1.check (11, k, "[]");
    
            d1 = new MyDeque<Integer> ();
            d1.pushRight (11);
            d1.check ("[11]");
            d1.pushRight (12);
            d1.check ("[11 12]");
            k = d1.popRight ();
            d1.check (12, k, "[11]");
            k = d1.popRight ();
            d1.check (11, k, "[]");
    
            d1 = new MyDeque<Integer> ();
            for (int i = 10; i < 15; i++)
                d1.pushLeft (i);
            for (int i = 20; i < 25; i++)
                d1.pushRight (i);
            d1.check ("[14 13 12 11 10 20 21 22 23 24]");
            d2 = new MyDeque<Integer> ();
            d1.concat (d2);
            d1.check ("[14 13 12 11 10 20 21 22 23 24]");
            d2.check ("[]");
    
            for (int i = 30; i < 35; i++)
                d2.pushLeft (i);
            for (int i = 40; i < 45; i++)
                d2.pushRight (i);
            d2.check ("[34 33 32 31 30 40 41 42 43 44]");
    
            d3 = new MyDeque<Integer> ();
            d2.concat (d3);
            d2.check ("[34 33 32 31 30 40 41 42 43 44]");
            d3.check ("[]");
    
            d1.concat (d2);
            d1.check ("[14 13 12 11 10 20 21 22 23 24 34 33 32 31 30 40 41 42 43 44]");
            d2.check ("[]");
    
            for (int i = 0; i < 20; i++) {
                d1.popLeft ();
                d1.check (null);
            }
            try {
                d1.popLeft ();
                throw new Error ("Expected exception");
            } catch (RuntimeException e) {}
            try {
                d1.popRight ();
                throw new Error ("Expected exception");
            } catch (RuntimeException e) {}
        }}
    I am still having problems with pushleft.

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,005
    Blog Entries
    7
    Rep Power
    20

    Default Re: Need Java help

    Quote Originally Posted by Newbie View Post
    Java Code:
        public void pushLeft (Item item) {
        	if(N==0){
        		Node oldfirst = first;
        		first = new Node();
        		last = first;
        		first.item=item;
        		
        		N++;
        	}
        	else{
        		first.next=last.prev;
        		Node newfirst = first;
        		//first = last;
        		first = new Node();
        		first.item=item;
        		first.next = null;
        		if (last.next == null){
        			last=last.next;
        		}
        		N++;
        	}
        }
    I am still having problems with pushleft.
    I don't understand all that juggling; when there are no items in the deque, update the first and last pointer to point to the single new element; else, when there are items in the deque already, just prepend the new item to the deque and only update the first pointer (it should point to the new item).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •