Implement Queue by Linked List (Ladder)

Description

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

enqueue(item). Put a new item in the queue.
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

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   // class ListNode {
   // public:
   //     int val;
   //     ListNode* next;
   //     ListNode(int _val): val(_val), next(nullptr) {}
   // }
   // -----------------------------------------------------
   // // raw
   class Queue {
   public:
    Queue() {
        // do initialize if necessary
        prevhead = new ListNode(0);
        prevtail = prevhead;
    }
    void enqueue(int item) {
        // Write your code here
        if (!prevhead->next) {
            prevhead->next = new ListNode(item);
            prevtail = prevhead->next;
        } else {
            prevtail->next = new ListNode(item);
            prevtail = prevtail->next;
            return;
        }
    }
    int dequeue() {
        // Write your code here
        if (prevhead->next) {
            ListNode* cur = prevhead->next;
            int result = prevhead->next->val;
            prevhead->next = prevhead->next->next;
            delete cur;
            return result;
        }
        return -1;
    }
   private:
    ListNode* prevhead;
    ListNode* prevtail;
   };
   // -------------------------------------------------------
   // Better
   class Queue {
   public:
    Queue() {
        // do initialize if necessary
        head = nullptr;
        tail = nullptr;
    }
    void enqueue(int item) {
        // Write your code here
        if (!head) {
            head = new ListNode(item);
            tail = head;
        } else {
            tail->next = new ListNode(item);
            tail =  tail->next;
        }
    }
    int dequeue() {
        // Write your code here
        if (head) {
            ListNode* cur = head;
            int result = head->val;
            head = head->next;
            delete cur;
            return result;
        }
        return -1;
    }
   private:
    ListNode* head;
    ListNode* tail;
   };
   

Similar problems

x

Tags

x