Структура данных и алгоритмы - очередь

Очередь - это абстрактная структура данных, несколько похожая на стеки. В отличие от стеков, очередь открыта с обоих концов. Один конец всегда используется для вставки данных (постановка в очередь), а другой - для удаления данных (снятие очереди). Очередь следует методологии «первым пришел - первым обслужен», то есть элемент данных, сохраненный первым, будет доступен первым.

Пример очереди

Реальным примером очереди может быть дорога с односторонним движением с односторонним движением, на которой транспортное средство въезжает первым, выезжает первым. Более реальные примеры можно увидеть в виде очередей в кассах и на автобусных остановках.

Представление очереди

Как мы теперь понимаем, в очереди мы получаем доступ к обоим концам по разным причинам. Следующая диаграмма, приведенная ниже, пытается объяснить представление очереди как структуру данных -

Пример очереди

Как и в стеках, очередь также может быть реализована с использованием массивов, связанных списков, указателей и структур. Для простоты мы будем реализовывать очереди, используя одномерный массив.

Основные операции

Операции с очередями могут включать инициализацию или определение очереди, ее использование, а затем полное удаление из памяти. Здесь мы попытаемся понять основные операции, связанные с очередями -

  • enqueue () - добавить (сохранить) элемент в очередь.

  • dequeue () - удалить (получить доступ) элемент из очереди.

Еще несколько функций требуется, чтобы сделать вышеупомянутую работу очереди эффективной. Это -

  • peek () - получает элемент в начале очереди, не удаляя его.

  • isfull () - Проверяет, заполнена ли очередь.

  • isempty () - Проверяет, пуста ли очередь.

В очереди мы всегда удаляем данные (или обращаемся к ним), на которые указывает передний указатель, и, помещая (или сохраняя) данные в очередь, мы пользуемся задним указателем.

Давайте сначала узнаем о вспомогательных функциях очереди -

PEEK ()

Эта функция помогает видеть данные в начале очереди. Алгоритм функции peek () выглядит следующим образом:

Алгоритм

begin procedure peek
   return queue[front]
end procedure

Реализация функции peek () на языке программирования C -

пример

int peek() {
   return queue[front];
}

полон()

Поскольку мы используем массив одного измерения для реализации очереди, мы просто проверяем наличие заднего указателя в MAXSIZE, чтобы определить, что очередь заполнена. Если мы будем поддерживать очередь в круговом связанном списке, алгоритм будет отличаться. Алгоритм функции isfull () -

Алгоритм

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Реализация функции isfull () на языке программирования C -

пример

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

пустой()

Алгоритм функции isempty () -

Алгоритм

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure

Если значение front меньше MIN или 0, это говорит о том, что очередь еще не инициализирована и, следовательно, пуста.

Вот программный код C -

пример

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

Операция постановки в очередь

Очереди поддерживают два указателя данных, спереди и сзади . Поэтому его операции сравнительно сложны для реализации, чем операции со стеками.

Для постановки (вставки) данных в очередь необходимо выполнить следующие шаги:

  • Шаг 1 - Проверьте, заполнена ли очередь.

  • Шаг 2 - Если очередь заполнена, выведите ошибку переполнения и выйдите.

  • Шаг 3 - Если очередь не заполнена, увеличьте задний указатель, чтобы указать следующий пустой пробел.

  • Шаг 4 - Добавьте элемент данных в расположение очереди, куда указывает указатель.

  • Шаг 5 - верните успех.

Операция вставки

Иногда мы также проверяем, инициализирована очередь или нет, для обработки любых непредвиденных ситуаций.

Алгоритм постановки в очередь

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

Реализация enqueue () на языке программирования C -

пример

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

Операция Dequeue

Доступ к данным из очереди представляет собой процесс двух задач - получить доступ к данным, куда указывает фронт, и удалить данные после доступа. Для выполнения операции удаления очереди предпринимаются следующие шаги:

  • Шаг 1 - Проверьте, пуста ли очередь.

  • Шаг 2 - Если очередь пуста, выдайте ошибку недостаточного значения и выйдите.

  • Шаг 3 - Если очередь не пуста, получите доступ к данным, куда указывает фронт .

  • Шаг 4 - Увеличьте передний указатель, чтобы он указывал на следующий доступный элемент данных.

  • Шаг 5 - Верните успех.

Удалить операцию

Алгоритм работы с дежурной

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

Реализация dequeue () на языке программирования C -

пример

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

Для полной программы Queue на языке программирования C, пожалуйста, нажмите здесь .