#include <iostream>
using namespace std;

class Queue {
private: //private members can only be accessed in the class
	int queue_size;
protected:
	int* buffer;
	int front;
	int rear;
	static int counter;
public:
	Queue(void) {
		front = 0;
		rear = 0;
		queue_size = 10;
		buffer = new int[queue_size];	// create an array in the heap
		if (buffer != NULL) counter++;
	}
	Queue(int n) {
		front = 0;
		rear = 0;
		queue_size = n;
		buffer = new int[queue_size];
		if (buffer != NULL) counter++;
	}
	virtual ~Queue(void) {
		delete buffer;
		counter--;
	}

	void enqueue(int v) { // add element at the end of queue
		if (rear < queue_size) buffer[rear++] = v;
		else if (compact()) buffer[rear++] = v;
	}
	int dequeue(void) { // return and remove 1st element from queue
		if (front < rear) return buffer[front++];
		else { cout << "Error:Queue empty" << endl; return -1; }
	}
private:
	bool compact(void);
};
int Queue::counter = 0;
//End of class definition

class PriQueue : public Queue {//PriQueue derived from Queue
public:
	int getMax(void);
	PriQueue(int n) : Queue(n) {};
	~PriQueue() {
		delete buffer;
		buffer = NULL;
		counter--;
	}
};


bool Queue::compact(void) {
	if (front == 0) {
		cout << "Error: Queue overflow" << endl;
		return false;
	}
	else {
		for (int i = 0; i < rear - front; i++)
		{
			buffer[i] = buffer[i + front];
		}
		rear = rear - front;
		front = 0;
		return true;
	}
}

int PriQueue::getMax(void) {// get & remove max value from priority queue
	int i, max, imax;
	if (front < rear) {
		max = buffer[front];
		imax = front; // imax is index of current max value
		for (i = front; i < rear; i++) {
			if (max < buffer[i]) {
				max = buffer[i];
				imax = i;
			}
		}
		for (i = imax; i < rear - 1; i++)
			buffer[i] = buffer[i++]; // remove max value
		rear = rear - 1;
		return max;
	}
	else {
		cout << "Error: Queue empty" << endl;
		return -1;
	}
}

//main outside all classes
void main() {
	Queue Q1(5);		// variable/object created using constructor in stack memory (note that buffer will create an array on the heap)
	Q1.enqueue(2);
	Q1.enqueue(8);
	int x = Q1.dequeue();
	int y = Q1.dequeue();
	cout << "x = " << x << endl << "y = " << y << endl;

	Queue* Q2;
	Q2 = new Queue(4);
	Q2->enqueue(12);	// insert 12
	Q2->enqueue(18);	// insert 18
	x = Q2->dequeue();
	y = Q2->dequeue();
	cout << "x = " << x << endl << "y = " << y << endl;

	PriQueue* Q3 = new PriQueue(4);
	Q3->enqueue(12);
	Q3->enqueue(18);
	Q3->enqueue(14);
	x = Q3->getMax();
	y = Q3->getMax();
	cout << "x = " << x << endl << "y = " << y << endl;


	delete Q2; Q2 = NULL;
	delete Q3; Q3 = NULL;
	system("pause");
}