Saturday, February 6, 2016

Implement Queue by Linked List

Implement Queue by Linked List

Implement a Queue by linked list. Support the following basic methods:
  1. enqueue(item). Put a new item in the queue.
  2. dequeue(). Move the first item out of the queue, return it.

Example
enqueue(1)
enqueue(2)
enqueue(3)
dequeue() // return 1
enqueue(4)
dequeue() // return 2


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Queue {
    
    private ListNode tail;
    private ListNode head;
    
    public Queue() {
        // do initialize if necessary
        tail = null;
        head = tail;
    }

    public void enqueue(int item) {
        // Write your code here
        if (isEmpty()) {
            tail = new ListNode(item);
            head = tail;
        }
        else {
            ListNode newTail = new ListNode(item);
            tail.next = newTail;
            tail = newTail;
        }
    }

    public int dequeue() {
        // Write your code here
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        else {
            int val = head.val;
            head = head.next;
            return val;
        }
    }
    
    public boolean isEmpty() {
        return (head == null);
    }
}
Posted by at