CODEWITHSUNDEEP
arraysalgorithmdata-structuresqueuecircular-buffer
Ravindra
Ravindra

Reputation: 95

Full / Empty Buffer distinction in Circular Queue

In array implementation of circular queue if we point front to a slot before the first element and rear to the last element, hen we face the problem of how to identify whether the queue is full or empty.

To solve this problem we use either a counter or waste one space in the buffer.

I was thinking of the following approach. Please correct me where I am going wrong, and if not please let me know if this is a better/worse solution than the above.

  1. Point front to the first element and rear to the last element;
  2. Have a function to check if the Queue has only 1 element left;
  3. If we are dequeing the last element, make front and rear -1;
  4. isEmpty() will be true if both front & rear are -1;
  5. isFull will be true if front = (rear + 1) % size.

Upvotes: 2

Views: 4034

Answers (1)

jxh
jxh

Reputation: 70382

There is not much wrong logically with this approach. You are treating negative values in front and rear as a kind of flag to indicate the queue is empty. Assuming your logic to update front and rear keeps the values in the range 0..size, you only need to set one of them to be outside that range to indicate the queue is empty.

Consider this alternative. Many circular queues work with the front and rear indices as unsigned values, and the size as a power of 2. The updating of their values is always to increment, and they are allowed to wrap around. This avoids complicated logic to adjust those indices. Because the indices are unsigned, even if they wrap around, the difference arithmetic works properly to determine the number of elements.

The trick with the modulus working even if the indices wrap around on increment is that size is a power of 2. This ensures that the wrapping around does not affect the modulus computation.

unsigned front_ = 0, rear_ = 0;
Type q_[SIZE];

unsigned getCount () { return rear_ - front_; }
bool isEmpty () { return getCount() == 0; }
bool isFull () { return getCount() == SIZE; }
bool enQ (Type val) {
    bool result = !isFull();
    if (result) q_[rear_++ % SIZE] = val;
    return result;
}
bool deQ (Type *val) {
    bool result = !isEmpty();
    if (result) *val = q_[front_++ % SIZE];
    return result;
}

Upvotes: 4

Related Questions