Monday, February 8, 2016

Implement Queue by Linked List II

Implement Queue by Linked List II

Implement a Queue by linked list. Provide the following basic methods:
  1. push_front(item). Add a new item to the front of queue.
  2. push_back(item). Add a new item to the back of the queue.
  3. pop_front(). Move the first item out of the queue, return it.
  4. pop_back(). Move the last item out of the queue, return it.


Example
push_front(1)
push_back(2)
pop_back() // return 2
pop_back() // return 1
push_back(3)
push_back(4)
pop_front() // return 3
pop_front() // return 4




 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

public class Dequeue {
    
    private Node head, tail;
    
    public Dequeue() {
        // do initialize if necessary
        head = tail = null;
    }

    public void push_front(int item) {
        // Write your code here
        Node node = new Node(item);
        if (head == null) {
            head = tail = node;
        }
        else {
            head.prev = node;
            node.next = head;
            head = node;
        }
    }

    public void push_back(int item) {
        // Write your code here
        Node node = new Node(item);
        if (tail == null) {
            head = tail = node;
        }
        else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }

    public int pop_front() {
        // Write your code here
        if (head == null) {
            throw new NoSuchElementException();
        }
        else {
            int val = head.val;
            head = head.next;
            
            if (head == null) {
                tail = head;
            }
            else {
                head.prev = null;
            }
            
            return val;
        }
    }

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