Очередь на массиве и ее реализация на языке Си

d0bed187d0b5d180d0b5d0b4d18c d0bdd0b0 d0bcd0b0d181d181d0b8d0b2d0b5 d0b8 d0b5d0b5 d180d0b5d0b0d0bbd0b8d0b7d0b0d186d0b8d18f d0bdd0b0 d18f статьи

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

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

Та сторона, где происходит включение элементов называется хвостом, а где происходит исключение — головой. Поначалу многие не понимают, почему включаются элементы в хвост, а не в голову. Все просто! Давайте представим обычную очередь в буфет, в которой стоит 10 человек. Если в буфет зайдет одиннадцатый, то куда он станет? Правильно, в конец, другими словами, в хвост очереди.

Если же стек являлся структурой типа LIFO, то очередь — структура типа FIFO (от англ. First In, First Out — "Первым пришел — первым ушел"). Это вполне логично, стоит лишь вспомнить описанный выше пример с очередью в буфете.

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

Файл Queue_Array.h

Думаю здесь все понятно, комментарии все объясняют. Единственное скажу, если Вам не понятно, зачем описывать исключительные ситуации, Вы можете рассмотреть пример со стеком, в котором я все описал.

Файл Queue_Array.c

Я обращаю Ваше внимание на строки с номерами 28 и 42. Почему здесь используется остаток от деления на размер буфера? Суть состоит в том, что мы делаем как бы кольцо, а если точнее, то кольцевую очередь. Дело в том, что если при включении и исключении элементов просто сдвигать указатель вперед, то может случиться так, что мы достигли конца массива, а в самом начале все еще есть свободные ячейки. Чтобы избежать подобного, мы просто, используя как раз-таки остаток от деления, будем устанавливать указатель в начало очереди, если был достигнут конец.

На этом все! И напоследок сделаем тест нашей очереди.

5 отзывов на “ Очередь на массиве и ее реализация на языке Си ”

«Суть состоит в том, что мы делаем как бы кольцо, а если точнее, то кольцевую очередь. Дело в том, что если при включении иисключении элементов просто сдвигать указатель вперед, то может случиться так, что мы достигли конца массива, а в самом начале все еще есть свободные ячейки.»
я не совсем понял зачем использовать мод. Ведь конца очереди мы достигнем когда добавим n элементов, это n-кол-во эл-тов совпадет с SIZE_QUEUE_ARRAY и тогда это будет означать что очередь заполнена.

Внимательно посмотрите на функцию исключения из очереди. Там есть такая строка:
F->ukBegin = (F->ukBegin + 1) % SIZE_QUEUE_ARRAY;
Суть ее состоит в том, что мы сдвинем указатель на один элемент вправо, так как при исключении мы достаем элемент из головы, то есть из начала.

Оцените статью
Секреты программирования
Добавить комментарий