Рубрики

ВОРОТА | GATE CS 2012 | Вопрос 33

Предположим, что круговая очередь из элементов вместимости (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

Ответ: (А)
Объяснение:
Внедрение круговой очереди:

Head — всегда указывает на место, откуда происходит следующее удаление из очереди.
Хвост — всегда указывает на следующее пустое место, в котором будет происходить следующая вставка в очереди.

Мы будем использовать функцию обтекания, поскольку это круговая очередь, в которой хвост или голова имеют индекс n-1, следующая операция приведет их к индексу 0. Несмотря на наличие емкости n внутри массива, мы зарезервируем одно пустое место для определения условий переполнения (очередь заполнена) и условий недостаточного заполнения (очередь пуста). Элементы в очереди находятся в местоположениях Q.head, Q.head + 1,. , , , Q.tail + 1, где мы «оборачиваемся» в том смысле, что местоположение 0 следует сразу же за местоположением n-1 в круговом порядке.

Алгоритм:

ENQUEUE(Q, x)                        
{

  if Q.head == Q.tail + 1
      error "Queue overflow"

  Q[Q.tail] = x

  if Q.tail == Q.length    - 1
      Q.tail = 0
  else
      Q.tail = Q.tail + 1
}


DEQUEUE(Q)
{
  if Q.head == Q.tail
      error "Queue underflow"

  x = Q[Q.head]

  if Q.head == Q.length - 1
      Q.head = 0
  else
      Q.head = Q.head + 1

  return x
}

См. Http://en.wikipedia.org/wiki/Circular_buffer#Always_Keep_One_Slot_Open

Это решение предоставлено Пранджул Ахаджа
Тест на этот вопрос

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

ВОРОТА | GATE CS 2012 | Вопрос 33

0.00 (0%) 0 votes