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();

}

Priority Queues–An Introduction

“We saw queues in which the people who come first goes out of the queue first!!.. even rowdies and politicians must follow this rule!!.. But current system doesn’t work like that..!! if rowdies or politicians come, they get more priority and VIP status.. For this we use priority queues”

See also

http://analgorithmaday.blogspot.com/2011/02/queuean-introduction.html

Metaphor

  As I said in the above quote, we need assign priority to each and every element instead of having just one priority condition, FIFO. This is major reason for going to priority queues.

Concept

  As explained by many, Priority Queues are not necessarily need to be implemented using Binary Heaps. But priority queues used for real time applications need to be efficient and faster. Where in computer world priority queue is used? Schedulers!!

  All OS schedulers use priority queues to allot CPU. The process with higher priority get CPU most of the time just because of this priority queues. So to get more efficient queues, people tend to use heaps. But we will first understand implementation of priority queue using array.

The important concept to be understood in priority queue is that, at most cases it just holds the priority value corresponding to an object. So, the priority is mostly an integer value associated with an object. They call this value as “key”. This first time we learn about keys!!.. so be careful to understand this.

“key1” “key2” “key3”   ---> Priority Queue

  V           V         V

  Obj1    Obj2   Obj3  ---> real system objects

For the example of OS Scheduler, process priority is the key and process itself is the real system object. The implementation internals of a small scheduler will be discussed in coming sections..

But in this article we will see about how these key’s are prioritized. Mostly based on max or min value!! min value suits some applications, max value suits some..

Some more examples of priority queues: Any Scoring system, Outlook task priority system, even gmail priority inbox.

Code

#define MAXQSIZE 10

class PriorityQueue

{

    int arr[MAXQSIZE];

    int idx;

public:

    PriorityQueue()

    {

        idx = 0;

    }

    bool insert(int elem)

    {

        if(idx > MAXQSIZE-1)

            return false;

        arr[idx++] = elem;

        return true;

    }

    bool remove(int& elem)

    {

        int maxIndex = 0;

        if(idx < 0)

            return false;

        for(int i = 1; i <= idx; i++) {

            if(arr[i] > arr[maxIndex])

                maxIndex = i;

        }

        elem = arr[maxIndex];

        //since idx++ is done by insert

        arr[maxIndex] = arr[idx-1]; 

        idx -= 1;

        return true;

    }

};

void main()

{

    int A[] = { 5, 4, 3, 2, 20, 7, 10};

    PriorityQueue pq;

    for(int i=0; i<7;i++) {

        pq.insert(A[i]);

    }

    int val=0;

    pq.remove(val);

}

Important points

• The above is a very simple implementation of priority queue based on queue implementation
• There is no front or back since we take the max element in each remove function call. This creates the hole we need. This hole is reused.
• This is very very simple priority queue with basic operations. Priority Queue ADT requires some more operations.
• The remove operations takes O(n) and insert operation in O(1). But both needs be at constant time for a real time scheduler
• The above code is practically very bad!! consider this equal to bubble sort :)
• We can use binary heaps, which gives heap remove with O(1) since the max element is always in index 0 in a heap
• Even insert takes less time O(log n) in case we use max heap. This is the wonder of data structures altering the performance of algorithms ;). But note that reverse is not true. Not all performance can be achieved by just changing the data structure..

Queue–An Introduction

“Queue of things!! A queue to buy tickets!!.. Its the same queue we talk about in computers as well.. The first person in the queue gets the chance to get the ticket first!!”

Metaphor

   The metaphor is as same as buying tickets for a movie in a theatre by standing in a queue. Only the first person in the queue gets the ticket first. This approach is called First-in, First-out in short (FIFO). Stack data structure is that’s why called as LIFO (Last-in, First out) and Queue is FIFO type.

  What is the use of such things in a computer? The same use like what we get in a real life queues. Order the items based on the order in which they are processed. In a scheduler, if a job is scheduled, it means it is put in a queue. The job which came first is allowed to be executed by a scheduler. In olden times, they just used a simple queues. But with advancement in mathematics and computer memory, very good scheduling algorithms came which never makes the CPU idle.

  Stack & Queues are the very basic data structures used in computers in almost all the algorithms.

Concept

  What would a queue need to be implemented? As usual, a dynamic or static structure, array or linked list.

The operations:

  - Enqueue or insertion

  - Dequeue or deletion

Queues have a front and a back. Insertion happens at the front. Deletion happens at the back. As you rotate inside if its a static array, like we did in all in-place algorithm. We must create a hole in this algorithm as well!!

Rotations also needs a hole!!.

i.e, if there is an Array like A[1…n], you can use only up to n-1. So, in an array like A[0..4], you can use only 0,1,2,3 indexes. The one index left is the hole index.

Code

Some important confusions:

• The first confusion is the index!!. You need both front and back
• When Front == back, queue is empty!!. This is a invariant btw. :D
• When front = back + 1 or front is zero and back > queue size, queue is full
• Note that we never fill more than index 3. Even though we have an array of size 5 running from 0..4
• The initial hole created at index 4, keeps on moving.. Since we maintain front = back+1 for a full condition!! THIS IS VERY VERY IMPORTANT
• If a character is given using “”, its a const char*.
• If a member function needs to be marked as const, it should not do any assignment operations using the argument!!! So, dequeue cannot be a const function

 

   1:   

   2:  const int QSIZE=5;

   3:   

   4:  template<class T>

   5:  class Queue

   6:  {

   7:      T arr[QSIZE];

   8:      int front;

   9:      int back;

  10:   

  11:  public:

  12:      Queue()

  13:      {

  14:          front=0;

  15:          back=0;

  16:      }

  17:   

  18:      bool enqueue(const T val)

  19:      {

  20:          if(isFull()) return false;

  21:   

  22:          arr[back] = val;

  23:          if(back == QSIZE-1)

  24:              back = 0;

  25:          else

  26:              back++;

  27:   

  28:          return true;

  29:      }

  30:   

  31:      // cannot mark this fn as const

  32:      bool dequeue(T& val)

  33:      {

  34:          if(isEmpty()) 

  35:              return false;

  36:   

  37:          val = arr[front];

  38:          arr[front] = "";

  39:          if(front == QSIZE-1)

  40:              front = 0;

  41:          else

  42:              front++;

  43:   

  44:          return true;

  45:      }

  46:   

  47:      bool isEmpty() const { return (front == back); }

  48:   

  49:      bool isFull() const { return (front == back + 1 || (front ==0 && back==QSIZE-1)); }

  50:  };

  51:   

  52:  void main()

  53:  {

  54:      Queue<char*> names;

  55:      // Note that all are const char*

  56:      names.enqueue("Jack");

  57:      names.enqueue("Muthu");

  58:      names.enqueue("Murugan");

  59:      names.enqueue("Kumar");

  60:      names.enqueue("Vinay");

  61:      names.enqueue("Purva");

  62:   

  63:      char* toppers="";

  64:      // remove jack, muthu

  65:      for(int i=0; i<2;i++)

  66:          names.dequeue(toppers);

  67:   

  68:      // enqueue rowdi

  69:      // eventhough they go at top index

  70:      // they are not at front :)

  71:      for(int i=0;i<4;i++) 

  72:          names.enqueue("Rowdis");

  73:   

  74:      // Now, murugan & kumar 

  75:      // Rowdis cannot do anything!!

  76:      for(int i=0; i<2;i++)

  77:          names.dequeue(toppers);

  78:   

  79:      // Polician join Rowdies now

  80:      // here too only after Rowdies, Politicians :)

  81:      for(int i=0;i<4;i++) 

  82:          names.enqueue("Politician");

  83:   

  84:  }