Population

Queue

    A.First Edition

    This is my first edition of a simple queue based on array with very simple and limited methods.

    B.The problem

    A queue is an array with start and end points such that all elements between start and end is the elements of

    the queue. (redundant?)

C.The idea of program

    Very simple, that I only use a counter to verify if queue is full or empty.

    D.The major functions

    1. bool Queue::enqueue(int data)

    Add new data into queue except that I check all elements in queue to make sure there is no repetition of data.

    2. bool Queue::dequeue(int& data)

    Retrieve data from start position and in order to avoid remove data from empty queue, I make it return type of

    bool. Then data is passed by reference.

    C.Further improvement

    1. Its purpose is for my BFS with array. So far it is enough.

    กก

    #include <iostream>

    using namespace std;

    const int MaxQueueNumber = 4000;

    class Queue
    {
    private:
    	int lst[MaxQueueNumber];
    	int start;
    	int end;
    	int counter;
    	bool isRepeat(int data);
    	int next(int index);
    public:
    	void onVisitData(int data);
    	bool enqueue(int data);
    	bool dequeue(int& data);
    	int queueCount(){return counter;}
    	Queue();
    };

    int main()
    {
    	Queue Q;
    	int data;
    	for (int i=0; i<400; i++)
    	{
    		Q.enqueue(i);
    		cout<<Q.queueCount()<<endl;
    	}
    	for (i=0; i<401; i++)
    	{
    		Q.dequeue(data);
    		cout<<"data is"<<data<<endl;
    		cout<<Q.queueCount()<<endl;
    	}

    	return 0;
    }

    Queue::Queue()
    {
    	start = 0;
    	end = start;
    	counter =0;
    }

    bool Queue::dequeue(int& data)
    {
    	if (counter==0)
    	{
    		cout<<"Queue is empty!"<<endl;
    		return false;
    	}
    	data = lst[start];
    	start++;
    	if (start==MaxQueueNumber)
    	{
    		start=0;
    	}
    	counter--;
    	return true;
    }

    bool Queue::enqueue(int data)
    {
    	if (counter==MaxQueueNumber)
    	{
    		cout<<"Queue is full!"<<endl;
    		return false;
    	}
    	if (!isRepeat(data))
    	{
    		lst[end]=data;
    		end++;
    		if (end==MaxQueueNumber)
    		{
    			end=0;
    		}
    		counter++;
    		return true;
    	}
    	return false;
    }

    int Queue::next(int index)
    {
    	if (end>start)//normal
    	{
    		if (index<end-1&&index>=start)
    		{
    			return index+1;
    		}
    	}
    	else
    	{
    		if (end<start)//
    		{
    			if (index>=start&&index<MaxQueueNumber)//
    			{
    				if (index+1==MaxQueueNumber)
    				{
    					return 0;
    				}
    				else
    				{
    					return index+1;
    				}
    			}
    			else
    			{
    				if (index<end-1&&index>=0)
    				{
    					return index+1;
    				}
    			}
    		}
    	}
    	return -1;
    }

    bool Queue::isRepeat(int data)
    {
    	int index=start;

    	while(index!=-1)
    	{
    		if (lst[index]==data)
    		{
    			return true;
    		}
    		index = next(index);
    	}
    	return false;
    }