The queue class

[code lang=c++] #ifndef _CP_QUEUE_INCLUDED_ #define _CP_QUEUE_INCLUDED_

#include #include //#pragma once

namespace CP {

template class queue { protected: T *mData; size_t mCap; size_t mSize; size_t mFront;

void expand(size_t capacity) {
  T *arr = new T[capacity]();
  for (size_t i = 0;i < mSize;i++) {
    arr[i] = mData[(mFront + i) % mCap];
  }
  delete [] mData;
  mData = arr;
  mCap = capacity;
  mFront = 0;
}

void ensureCapacity(size_t capacity) {
  if (capacity > mCap) {
    size_t s = (capacity > 2*mCap) ? capacity : 2*mCap;
    expand(s);
  }
}

public: //-------------- constructor ----------

// copy constructor
queue(const queue<T>& a) {
  this->mData = new T[a.mCap]();
  this->mCap = a.mCap;
  this->mSize = a.mSize;
  for (size_t i = 0; i < a.mCap;i++) {
    mData[i] = a.mData[i];
  }
  this->mFront = a.mFront;
}

// default constructor
queue() {
  int cap = 1;
  mData = new T[cap]();
  mCap = cap;
  mSize = 0;
  mFront = 0;
}

// copy assignment operator
queue<T>& operator=(queue<T> other) {
  using std::swap;
  swap(mSize,other.mSize);
  swap(mCap,other.mCap);
  swap(mData,other.mData);
  return *this;
}

~queue() {
  delete [] mData;
}

//------------- capacity function -------------------
bool empty() const {
  return mSize == 0;
}

size_t size() const {
  return mSize;
}

//----------------- access -----------------
const T& front() {
  if (size() == 0) throw std::out_of_range("index of out range") ;
  return mData[mFront];
}
const T& back() {
  if (size() == 0) throw std::out_of_range("index of out range") ;
  return mData[(mFront + mSize - 1) % mCap];
}

//----------------- modifier -------------
void push(const T& element) {
  ensureCapacity(mSize + 1);
  mData[(mFront + mSize) % mCap] = element;
  mSize++;
}

void pop() {
  if (size() == 0) throw std::out_of_range("index of out range") ;
  mFront = (mFront + 1) % mCap;
  mSize--;
}

};

}

#endif [/code]

The testing unit

[code lang=c++] #include #include #include "queue.h" #include #include

//typedef CP::queue Queue; // typedef CP::queue Queue;

bool test1() { Queue q; assert(q.size() == 0);

q.push(1); q.push(2); q.push(3); q.push(3);

assert(q.front() == 1 && q.size() == 4); q.pop(); assert(q.front() == 2 && q.size() == 3); q.pop(); assert(q.front() == 3 && q.size() == 2); q.pop(); assert(q.front() == 3 && q.size() == 1); q.pop();

assert(q.size() == 0);

return true; }

bool test2() { Queue q; q.push(1); q.push(1); q.push(1); q.pop(); q.pop(); q.pop();

Queue s2 = q;

try { int x = q.front(); std::cout << "x = " << x << std::endl; q.pop(); } catch (std::exception &e) { std::cout << "Caught an exception " << e.what() << std::endl; return true; } return false; }

bool test3() { int nRun = 20; int nData = 1000000; for (int i = 0;i < nRun;i++) { Queue q; for (int j = 0;j < nData;j++) { q.push(j); } for (int j = 0;j < nData;j++) { assert(q.front() == j); q.pop(); } } return true; } bool test4() { Queue q; q.push(1); q.push(2); q.push(3); assert(q.back() == 3); q.pop(); q.push(4); assert(q.back() == 4); assert(q.front() == 2); q.pop(); assert(q.front() == 3); q.pop(); assert(q.back() == 4); assert(q.front() == 4); q.pop(); if (q.size() == 0) { return true; } else { return false; } } int main() { if (test1()) std::cout << "---------------------------------------- Test1 OK!" << std::endl; if (test2()) std::cout << "---------------------------------------- Test2 OK!" << std::endl; if (test3()) std::cout << "---------------------------------------- Test3 OK!" << std::endl; if (test4()) std::cout << "---------------------------------------- Test4 OK!" << std::endl; return 0; } [/code]