Implement Queue using Linked List

 

Question

  Implement Queue using singly linked list. Enqueue should take O(1) time and Dequeue should take O(1) time.

Concept

  Unlike stack, for queues, we need two pointers: first and last. Enqueue will happen in last. Dequeue will happen in the first. Initially first and last both will point to the one node. After that every enqueue will have insertion happen at last->next.

Dequeue will happen at the first. If first and last both are equal, both will equal to NULL.

Code

class QueueList

{

    struct ListNode

    {

        int data;

        ListNode* next;

    };

    ListNode *first, *last;

public:

    QueueList() : first(NULL), last(NULL) { }

    void enqueue(int data);

    int dequeue();

};

void QueueList::enqueue(int data)

{

    ListNode *n = new ListNode;

    n->data = data;

    if(first == NULL && last == NULL)

    {

        first = last = n;

    }

    last->next = n;

    n->next = NULL;

    last = n;

}

int QueueList::dequeue()

{

    if(first == NULL && last == NULL) return -1;

    int data = first->data;

    ListNode* next = first->next;

    if(first == last) {

        free(last); 

        last = NULL;

    } else {

        free(first);

    }

    first = next;

    return data;

}

void main()

{

    QueueList obj;

    obj.enqueue(10);

    obj.enqueue(20);

    obj.enqueue(30);

    obj.enqueue(40);

    cout<<obj.dequeue();

    cout<<obj.dequeue();

    cout<<obj.dequeue();

    cout<<obj.dequeue();

    obj.enqueue(20);

    cout<<obj.dequeue();

    cout<<obj.dequeue();

}