Announcement

Collapse
No announcement yet.

Double-ended queue in Java

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Double-ended queue in Java

    I managed to code it myself after all... here's my solution:
    class Deque {

    private Node front, rear;
    private int counter;

    public Deque() {
    front = null;
    rear = null;
    counter = 0;
    }

    public void push(Object x) {
    if (front==null) {
    Node T = new Node(x, null, null);
    rear = T;
    front = T;
    counter++;
    } else {
    Node T = new Node(x, front, null);
    front.next=T;
    front = T;
    counter++;
    }

    }

    public Object pop() {
    if (counter==0) {
    return null;
    } else if (counter==1) {
    counter=0;
    Object x = front.data;
    rear = null;
    front = null;
    return x;
    }
    else {
    Object x = front.data;
    front=front.prev;
    rear.prev = front;
    counter--;
    return x;
    }
    }

    public void inject (Object x) {
    if (rear==null) {
    Node T = new Node(x, null, null);
    rear = T;
    front = T;
    counter++;
    } else {
    Node T = new Node(x, null, rear);
    rear.prev=T;
    rear = T;
    counter++;
    }
    }

    public Object eject() {
    if (counter==0) {
    rear=null;
    front=null;
    return null;
    } else if (counter==1) {
    counter=0;
    Object x = rear.data;
    rear=null;
    front=null;
    return x;
    }
    else {
    Object x = rear.data;
    rear=rear.next;
    front.next = rear;
    counter--;
    return x;
    }
    }

    class Node {

    Node prev;
    Node next;
    Object data;

    Node(Object d, Node p, Node n) {
    next = n;
    prev = p;
    data = d;
    }

    }

    }

    I managed to code it so that all operations are done in constant time, O(1) complexity, but it should be possible implement it without the counter. I also think that there are more unnecessary things in my solution and I would like to know how you can make it more compact.
    Last edited by mate88; September 24, 2011, 06:18 PM.
    I don't actively visit this forum anymore, but you'll find me at #torrent-invites on T-I IRC

    They call me the Count because I love to count things...

  • #2
    Why are you using Objects everywhere and not generics?

    Comment


    • #3
      Originally posted by roamer View Post
      Why are you using Objects everywhere and not generics?
      I'm not familiar with the concept and this was an assignment I had to write from scratch. I'm still learning java. This was a task given at a course on data structures.
      I don't actively visit this forum anymore, but you'll find me at #torrent-invites on T-I IRC

      They call me the Count because I love to count things...

      Comment


      • #4
        This thread is old and I'm guessing you've moved on by now. But I'll add my thoughts in case anyone is interested.

        Definitely seems over-complicated to me. I would do something like (e.g.)
        public void push(Object x) {
        Node T = new Node(x, null, null);
        T.next = front;
        front = T;
        }
        And the other functions are similar. With practice, you will be able to write code that addresses the general sense of the problem, rather than addressing cases individually. Keep it up -- you are off to a good start.

        You are correct that the counter is unnecessary. However, you should consider what would happen if you want to ask how many elements are in the deque, and you want the computation of the answer to be O(1). Updating a count variable would help you with that.

        Comment

        Working...
        X