Implement Queue by Linked List II (Ladder)

Description

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.

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

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   class Dequeue {
   public:    
    Dequeue() {
        // do initialize if necessary
        head = nullptr;
        tail = nullptr;
        // prevtail = nullptr;
    }
    void push_front(int item) {
        // Write your code here
        // whether the whole list is empty
        if (!head) {
            head = new ListNode(item);
            tail = head;
        } else {
            ListNode* cur = new ListNode(item);
            cur->next = head;
            head = cur;
        }
    }
    void push_back(int item) {
        // Write your code here
        // whether the whole list is empty
        if (!head) {
            head = new ListNode(item);
            tail = head;
            // prevtail = nullptr;
        } else {
            // prevtail = tail;
            tail->next = new ListNode(item);
            tail = tail->next;
        }
    }
    int pop_front() {
        // Write your code here
        if (head) {
            ListNode* cur = head;
            int res = cur->val;
            head = head->next;
            delete cur;
            return res;
        }
        return -1;
    }
    int pop_back() {
        // Write your code here
        if (!head) {
            return -1;
        }
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while (cur->next) {
            prev = cur;
            cur = cur->next;
        }
        // head is the last one
        if (cur == head) {
            int res = cur->val;
            head = nullptr;
            tail = nullptr;
            // disconnect and delete
            delete cur;
            return res;
        } else {
        // head has many nodes
            int res = cur->val;
            tail = prev;
            // disconnect and delete
            prev->next = nullptr;
            delete cur;
            return res;
        }
    }
   private:
    ListNode* head;
    ListNode* tail;
    // ListNode* prevtail;
   };
   

Similar problems

x

Tags

x