Queue data structure

 
###################### 
####    queue     #### 
###################### 
 
another abstract data structure (ADT). 
 
it is FIFO (first-in, first-out). 
 
- enqueue(elem)    in O(1) 
- dequeue()        in O(1) 
- is_empty()       in O(1)     ## needed before running dequeue() 
 
 
same age-old discussion of array VS linked-list applies when it comes to implementation. 
see the stack article for the summary of pros and cons. 
 
 
 
############################# 
###    priority queue     ### 
############################# 
 
it is a queue that always keeps its contents sorted based on some priority metrics. so you can always pop the smallest(biggest) priority elem from the top, etc. 
 
 
################################ 
###   implementation (C++)   ### 
################################ 
 
since LL is too simple, lets use array for implementation. 
 
when using array, to efficiantly use the allocated space, we will use "ring buffer" concept. 
 
that is to say that we treat the last elem of the array to be connecting to the top of the array. 
 
 
---------------------------------------------------  //  kqueue.h 
 
template<typename T> class kqueue 

 public: 
 kqueue() : head(0),tail(0),arrSize(5){ arr = new T[arrSize]; }  // default array size 5 
  void enqueue(T); 
  T dequeue(); 
  bool is_empty(); 
  int sizeQ(){ return qSize; }   // just made a pub func for debugging 
  int sizeA(){ return arrSize; } // same 
 private: 
  T* arr; 
  int arrSize; 
  int qSize; 
  int head; 
  int tail; 
}; 
 
template<typename T> void kqueue<T>::enqueue(T t) 

 
  if( qSize == arrSize )   // if full, resize 
  { 
    arrSize *= 2; 
    T* arr2 = new T[arrSize]; 
    int p = head; 
    int i = 0; 
    while(1) 
    { 
      if ( i == (arrSize/2) ){  // finished oopying everything from the old array 
        head = 0; 
        tail = i;               // points to the first empty cell in the newly extended array 
        break; 
      } 
      arr2[i] = arr[p]; 
      i++; 
      if(p == arrSize -1) 
        p = 0; 
      else 
        p++; 
    } 
    delete [] arr; 
    arr = arr2; 
  } 
 
  int tmp = tail; 
  if (tail == arrSize - 1)    // if tail is at the last pos of the array 
    tail = 0; 
  else 
    tail++; 
  arr[tmp] = t; 
  qSize++; 
 

 
 
template<typename T> T kqueue<T>::dequeue() 

  if( is_empty() )   // should throw error, but just being lazy here. 
    return -99999;   // also, the assumption is that user uses is_empty() before dequeue() 
  else{ 
    int tmp = head; 
    if(arrSize == (head + 1)) 
      head = 0; 
    else 
      head++; 
    qSize--; 
    return arr[tmp]; 
  } 

 
template<typename T> bool kqueue<T>::is_empty() 

  if( qSize == 0) 
    return true; 
  else 
    return false; 

 
----------------------------------------------- 
----------------------------------------------- // main.cpp 
 
#include <iostream> 
#include "kqueue.h" 
using namespace std; 
 
int main() 

  kqueue<int> kq; 
 
  cout << kq.is_empty() << endl;    //  1 
  cout << kq.sizeA() << endl;       //  5 
  cout << kq.sizeQ() << endl;       //  0 
 
  kq.enqueue(12); 
 
  cout << kq.is_empty() << endl;    //  0 
  cout << kq.sizeA() << endl;       //  5 
  cout << kq.sizeQ() << endl;       //  1 
 
  kq.enqueue(34); 
  kq.enqueue(56); 
  kq.enqueue(78); 
  kq.enqueue(90); 
 
  cout << kq.is_empty() << endl;    //  0 
  cout << kq.sizeA() << endl;       //  5 
  cout << kq.sizeQ() << endl;       //  5 
 
  // enqueue() looks ok 
 
  kq.enqueue(11); 
 
  cout << kq.is_empty() << endl;    //  0 
  cout << kq.sizeA() << endl;       //  10 
  cout << kq.sizeQ() << endl;       //  6 
 
  // resize worked. 
  // now, lets start dequeue'ing 
 
  cout << kq.dequeue() << endl;     //  12 
  cout << kq.dequeue() << endl;     //  34 
  cout << kq.dequeue() << endl;     //  56 
 
  kq.enqueue(777); 
 
  cout << kq.dequeue() << endl;     //  78 
  cout << kq.dequeue() << endl;     //  90 
  cout << kq.dequeue() << endl;     //  11 
  cout << kq.dequeue() << endl;     //  777 
  cout << kq.dequeue() << endl;     //  -99999 
 
  // ok. 
 
  return 0; 

 
------------------------------------------------ 
 

  1. 2014-06-05 23:36:10 |
  2. Category : data_structure
  3. Page View:

Google Ads