## Sunday, 5 June 2011

### 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();`
`}`