Implement Queue by Linked List II

题目:

Implement a Queue by linked list. Provide the following basic methods:

push_front(item). Add a new item to the front of queue.
push_back(item). Add a new item to the back of the queue.
pop_front(). Move the first item out of the queue, return it.
pop_back(). Move the last item out of the queue, return it.

分析:

这道题目实际是要求实现deque,并不是太难

解法:

class DoublyListNode {
    public int val;
    public DoublyListNode prev, next;
    DoublyListNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

public class Dequeue {

    DoublyListNode first, last;

    public Dequeue() {
        // do initialize if necessary
    }

    public void push_front(int item) {
        // Write your code here
        if (first == null || last == null) {
            first = new DoublyListNode(item);
            last = first;
        } else {
            DoublyListNode temp = new DoublyListNode(item);
            temp.next = first;
            first.prev = temp;
            first = temp;
        }
    }

    public void push_back(int item) {
        // Write your code here
        if (first == null || last == null) {
            first = new DoublyListNode(item);
            last = first;
        } else {
            DoublyListNode temp = new DoublyListNode(item);
            last.next = temp;
            temp.prev = last;
            last = temp;
        }
    }

    public int pop_front() {
        // Write your code here
        int res = -1;
        if (this.isEmpty() ) {
            return res;
        } else if (first == last) {
            res = first.val;
            first = null;
            last = null;
        } else {
            res = first.val;
            first = first.next;
            first.prev = null;
        }
        return res;
    }

    public int pop_back() {
        // Write your code here
        int res = -1;
        if (this.isEmpty() ) {
            return res;
        } else if (first == last) {
            res = last.val;
            first = null;
            last = null;
        } else {
            res = last.val;
            last = last.prev;
            last.next = null;
        }
        return res;
    }

    public boolean isEmpty() {
        return first == null || last == null;
    }
}

results matching ""

    No results matching ""