Рубрики

Структуры данных | Очередь | Вопрос 11

Предположим, что круговая очередь из элементов вместимости (n — 1) реализована с помощью массива из n элементов. Предположим, что операция вставки и удаления выполняется с использованием REAR и FRONT в качестве переменных индекса массива соответственно. Первоначально REAR = FRONT = 0. Условия для определения полной очереди и пустой очереди:
(A) Полный: (REAR + 1) mod n == FRONT, пустой: REAR == FRONT
(B) Полный: (REAR + 1) mod n == FRONT, пустой: (FRONT + 1) mod n == REAR
(C) Полный: REAR == FRONT, пустой: (REAR + 1) mod n == FRONT
(D) Полный: (FRONT + 1) mod n == REAR, пустой: REAR == FRONT

Ответ: (А)
Объяснение:

Suppose we start filling the queue.

Let the maxQueueSize ( Capacity of the Queue) is 4.
So the size of the array which is used to implement 
this circular queue is 5, which is n.

In the beginning when the queue is empty, FRONT and REAR 
point to 0 index in the array.

REAR represents insertion at the REAR index.
FRONT represents deletion from the FRONT index.

enqueue("a"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 1)
enqueue("b"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 2)
enqueue("c"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 3)
enqueue("d"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 4)

Now the queue size is 4 which is equal to the maxQueueSize. 
Hence overflow condition is reached.

Now, we can check for the conditions.

When Queue Full :

( REAR+1)%n = (4+1)%5 = 0

FRONT is also 0.

Hence ( REAR + 1 ) %n is equal to FRONT.

When Queue Empty :

REAR was equal to FRONT when empty ( because in the starting 
before filling the queue FRONT = REAR = 0 )

Hence Option A is correct. 

Тест на этот вопрос

Рекомендуемые посты:

Структуры данных | Очередь | Вопрос 11

0.00 (0%) 0 votes