Circular Queue Help

[polarpandabear]

Hello Guys, I'm new here and I would like to ask help from you in making circular queue. I'm solving these for days but I can't have any idea anymore to solve for it's algorithm...

I made this code so far...

#include <iostream>
#define SIZE 5
using namespace std;

int queueArr[SIZE];
void dequeue();
void enqueue(int);
void display();
int front(-1);
int rear(-1);

int main(){
	while(1){
		int choice;
		system("cls");
		cout << "[1] - Enqueue\n";
		cout << "[2] - Dequeue\n";
		cout << "[3] - Display\n";
		cout << "[4] - Exit\n";
		cout << "===================\n";
		cout << "Enter your choice: ";
		cin >> choice;
		switch(choice){
			case 1: 
				int num;
				cout << "Enter a number to enqueue: ";
				cin >> num;
				enqueue(num);				
				break;
			case 2:
				dequeue();		
				break;
			case 3:
				display();
				break;
			case 4:
				exit(1);
			default:
				cout << "\nWrong choice!\n";
		}
		cout << endl;
		system("pause");
	}
	return 0;
}

void display(){
	if(rear == -1 || front > rear)
		cout << "Queue is empty!";
	else
		for(int i=front; i<=rear; i++)
			cout << queueArr[i] << " ";
}

void enqueue(int n){
	if(rear < SIZE-1){
		if(front==-1)
			front++;
		queueArr[++rear]=n;	
	}
	else
		cout << "Queue is overflow!";
}

void dequeue(){	
	if(rear<front || front==-1){
		cout << "Queue is empty!";
		front = -1;
		rear= -1;
	}
	else
		cout << "Dequeue value is " << queueArr[front++];
}

I provided an attachment where you can see the algoithm of the circular queue but I'm having trouble on implementing it into code.

Thanks :)

[rubberman]

This is C++ exercise? You show code, but no data structures (classes) for modeling this problem. This means that you are going backward, from code to structure. You need to design the classes you are going to use in terms of their contained data (attributes/properties) and behavior (methods/functions). So, what do you need?

1. A class for the queue I think.
2. A class for members of the queue.

The queue class should probably have a pointer to a member of the queue. Each member should have a pointer to the next member in the queue, and the last will point back to the first. That way, a pointer to any member in the queue object itself will be sufficient to reach any other member, so call that the "current active member"?

Anyway, your code as you show it now is C code, not C++. No classes == C code.

[polarpandabear]

Our topic in class discussion is all about queues and our professor wants us to explore what are the elements in the queue and its types. he assigned me on making circular queues.

I only need to modify the code that I made because there's an error on that code and I'm still working on it

[rubberman]

Well, you aren't accommodating the possibility that front can be > rear when the queue has wrapped around. IE:

void display(){
	if(rear == -1 || front > rear)
		cout << "Queue is empty!";
	else
		for(int i=front; i<=rear; i++)
			cout << queueArr[i] << " ";
}

I guess what I'm saying, is that what you have implemented here is NOT a circular queue! Another observation is that when front has reached the end of the array, it doesn't wrap back around to index 0.

So, break the problem down into discrete operations within each function.

Enqueue:

// Set full indicator flag to false.
bool isfull = false;

// Check if queue is empty.
if (front == -1)
{
  front = rear = 0;
}
else if ((rear+1) == SIZE)
{ // reached end of array - wrap around.
  rear = 0;

  // Check for queue full.
  isfull = (front == 0);
}
else
{
  ++rear;
  if (rear == front)
  {
    // Overflow.
    isfull = true;
  }
}

// Now, test if queue is full.
if (!isfull)
{
  queue[rear] = newvalue;
}
else
{
   // Overflow, reset rear
   if (rear == 0)
   {
     rear = SIZE-1;
   }
   else
   {
     --rear;
   }
   throw QueueOverflowException;
}

This (untested) code should allow for the queue front and rear to wrap around from the end to beginning of the array. This is a common algorithm that is used frequently for circular buffers where you don't want the overhead of a linked list, such as what I suggested originally. I leave the dequeueing up to you. Remember, just because front == rear, this does not mean that the queue is full, since they would be the same if there is only one entry in the queue. You have to test on enqueuing. On dequeuing you need to detect if front == rear, in which case, you reset both to -1, indicating an empty queue.

In any case, for this sort of exercise, you really should write out what you need to do in some sort of pseudo code as it will help clarify things in your mind much better than code itself, unless you have a lot of experience with the language(s) in question.

[rubberman]

Note that in my example, there are alternative implementations where resetting the rear indicator is not necessary. However, that is an enhancement. The code I provided shows clearly what you are trying to accomplish, and should do that nicely. Efficiency and code reduction can be done later.

[polarpandabear]

void enqueue(int n){
	if(rear < SIZE-1){
		if(front == -1){
			front++;
			queueArr[++rear] = n;
		}
	}
	else if (rear == (SIZE-1)){
		rear = -1;
		if(front == 0)
			cout << "Queue is oveflow";
		else{
			if(rear == front)
				cout << "Queue is overflow";
			else
				queueArr[++rear] = n;
		}
	}
}

is it possible if I write in in this way?

[rubberman]

Huh? What are you trying to accomplish? I don't think this will work, your latest posting. First, test and deal with the empty situation where front (or rear, you can use either) == -1. Next deal with when rear (the "end" of the queue) is at the end of the array, detecting if the queue is full (front == 0). Finally, deal with other situations, detecting if the queue is full ((rear+1) == front). This will allow the front and rear markers to safely wrap around the end of the array, creating a circular queue. The steps I noted here, testing for empty, testing for end-of-array, and finally normal processing, is necessary because you ALWAYS want to detect boundary conditions (empty, end, full) as soon as possible before you get on to normal processing. This is a rule you should learn, and never forget when doing this sort of algorithmic programming.

So, in the words of a professor I once had, "Go home, redo it, and bring the results back to me in the morning!"... :-)

[mike_2000_17]

I think enough time and ink has been spent on this already, so let me lay out a clearer, step-by-step explanation of this circular-queue implementation.

You have to first examine what you need those "rear" and "front" indices for.

The rear index is used to find the next available free slot in your array, in order to enqueue a new element. So, it is natural that the "rear" index should be the index of the first free slot immediately following the last occupied slot in the array.

The front index is used to read the value of the first occupied slot in your array, in order to dequeue it. So, it's natural that the "front" index should point to the first occupied slot in the array.

Then, doing the "wrap-around" in the array is a simple matter of applying a modulus operation. That is, you increment the index, and then you apply a modulus with the size of the array which will cause the index to wrap back around to 0 when it reaches the end of the array. There is no need for a conditional statement to check the "end" condition, and applying a modulus instead is way more efficient too.

So, at the very least, your enqueue and dequeue functions should be:

void enqueue(int n) {
  queueArr[rear] = n;  //fill the first empty slot with value n.
  ++rear;              //move rear to the next empty slot.
  rear %= SIZE;        //wrap-around with a modulus.
};

int dequeue() {
  int result = queueArr[front];  //read the first occupied slot.
  ++front;                       //move front to the next occupied slot.
  front %= SIZE;                 //wrap-around with a modulus.
  return result;                 //return the value of the element that was dequeued.
};

If you run the above code, it will work fine as long as you don't hit the two problematic situations: dequeue on an empty queue, or enqueue on a full queue. Clearly, you need to check for these situations, which means you need some way to detect them.

At first, it seems hard to detect because these two situations have the same symptom if you apply the above enqueue and dequeue code, that is, in both cases (empty or full) you will end up with both "rear" and "front" having the same index value. Either the queue is full and "rear" has caught up to "front", or the queue is empty and "front" has caught up to "rear". You have to capitalize on that difference (who catches up to who), to detect the situations. Obviously, the queue can only become empty when you dequeue, and it can only become full when you enqueue, so that is where you must check for that.

Now, you also need a way to mark, in "rear" or "front", that emptyness or fullness has been detected. Going by the principle that "rear" points to the first free slot, then if the queue is full, that free slot doesn't exist, so "rear" can be set to -1 (invalid index). Conversely, if there is no occupied slot, the "front" index should be -1 (invalid).

So, we can now add the detection and marking of the two situations to the code:

void enqueue(int n) {
  queueArr[rear] = n;  //fill the first empty slot with value n.
  ++rear;              //move 'rear' to the next empty slot.
  rear %= SIZE;        //wrap-around with a modulus.
  if(rear == front) {  //check if 'rear' has caught up to 'front'.
    rear = -1;         //if yes, there is no empty slot for 'rear' to point to.
  };
};

int dequeue() {
  int result = queueArr[front];  //read the first occupied slot.
  ++front;                       //move 'front' to the next occupied slot.
  front %= SIZE;                 //wrap-around with a modulus.
  if(front == rear) {            //check if 'front' has caught up to 'rear'.
    front = -1;                  //if yes, there is no occupied slot to point to.
  };
  return result;                 //return the value of the element that was dequeued.
};

Then, you need to check the situations before you attempt the operations that would be impossible, that is, you can't enqueue in a full queue, and you can't dequeue in an empty queue. That's easy enough with a simple if-statement at the beginning of the functions:

void enqueue(int n) {
  if(rear == -1) {     //check if the queue is full (no empty slot).
    std::cout << "Queue is full!" << std::endl;
    return;            //if yes, report error, and cancel the operation.
  };
  queueArr[rear] = n;  //fill the first empty slot with value n.
  ++rear;              //move 'rear' to the next empty slot.
  rear %= SIZE;        //wrap-around with a modulus.
  if(rear == front) {  //check if 'rear' has caught up to 'front'.
    rear = -1;         //if yes, there is no empty slot for 'rear' to point to.
  };
};

int dequeue() {
  if(front == -1) {              //check if queue is empty (no occupied slot)
    std::cout << "Queue is empty!" << std::endl;
    return 0;                    //if yes, report error, and cancel operation.
  };
  int result = queueArr[front];  //read the first occupied slot.
  ++front;                       //move 'front' to the next occupied slot.
  front %= SIZE;                 //wrap-around with a modulus.
  if(front == rear) {            //check if 'front' has caught up to 'rear'.
    front = -1;                  //if yes, there is no occupied slot to point to.
  };
  return result;                 //return the value of the element that was dequeued.
};

Finally, you need some way to recover from the situations, that is, when you enqueue an element in an empty queue, or when you dequeue from a full queue. This is simply a matter of detecting the converse situation and remedying it:

void enqueue(int n) {
  if(rear == -1) {     //check if the queue is full (no empty slot).
    std::cout << "Queue is full!" << std::endl;
    return;            //if yes, report error, and cancel the operation.
  };
  if(front == -1) {    //check if the queue was empty.
    front = rear;      //if yes, 'rear' will become the first occupied element.
  };
  queueArr[rear] = n;  //fill the first empty slot with value n.
  ++rear;              //move 'rear' to the next empty slot.
  rear %= SIZE;        //wrap-around with a modulus.
  if(rear == front) {  //check if 'rear' has caught up to 'front'.
    rear = -1;         //if yes, there is no empty slot for 'rear' to point to.
  };
};

int dequeue() {
  if(front == -1) {              //check if queue is empty (no occupied slot)
    std::cout << "Queue is empty!" << std::endl;
    return 0;                    //if yes, report error, and cancel operation.
  };
  if(rear == -1) {    //check if the queue was full.
    rear = front;      //if yes, 'front' will become the first empty slot.
  };
  int result = queueArr[front];  //read the first occupied slot.
  ++front;                       //move 'front' to the next occupied slot.
  front %= SIZE;                 //wrap-around with a modulus.
  if(front == rear) {            //check if 'front' has caught up to 'rear'.
    front = -1;                  //if yes, there is no occupied slot to point to.
  };
  return result;                 //return the value of the element that was dequeued.
};

Don't you just love the wonderful symmetry of these two functions! The two functions are literally exactly the same if you swap "rear" and "front". This duality just comes from the fact that adding an element (enqueueing) is the same as removing an empty slot, and vice versa.

I wanted to expose all this code for the simple reason that this is a good way to construct an algorithm: start with the fundamental operations and then handle each sub-problem at a time, adding to the code.

Also, this is not the way the circular queue is shown in that picture you attached. First, it is a fairly trivial difference ("rear" points to the last occupied slot as opposed to the first empty slot). And second, doing it the way that it is illustrated in that figure is simply a very poor choice of indices (a simple difference that makes the code quite a bit nastier). Sometimes, text-book illustration of algorithms have these kinds of blatantly wrong choices in them.

[polarpandabear]

I did it thanks for your efforts to help me :)