Cormen Edition 3 Exercise 10.1 Question 4 (Page No. 235)

Question

Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue.

Answer 1

Consider the following pseudo code

Generalisation: Implement queue using notation with initial value of rear, front is -1. N is max_size of array which implements queue.

The enqueue operation
Two main points to lay emphasis

1. Is queue already full (The Overflow)
2. Is queue empty

enqueue(Q, data):
    // Check queue is full
    if (front == (rear + 1) % N): // The overflow condition
        print "Queue is full, Better luck next time"
    // Check if queue is empty
    if (front == -1 && rear == -1):
        front += 1
    // Now put the value in array
    rear = (rear + 1) mod N;
    arr_queue[rear] = data

The Dequeue Operation:

Two main points to consider:

1. Is queue already empty (The Underflow Condition)
2. Is the element to be dequeue is the last element

dequeue(Q):
    // Check if queue is already empty
    if (front == -1 && rear == -1):  // Underflow condition
        print "There does not exist any element to be removed"
        return -1
    // The element to be removed
    data = array[front]
    // Checking if the element to be dequeued is the last element
    if (front == rear):
        // restoring the intial state of the queue.
        front = rear = -1;
    else:
        front = (front + 1) % N;
    return data;