В прошлой статье я писал о том, что такое стек, его реализацию, да и вообще, что такое структуры данных. В этом посте я продолжу начатую тему, так что сейчас мы с Вами будем рассматривать структуру данных типа очередь.
Очередь — это последовательность, у которой включение элементов производится с одной стороны последовательности, а исключение — с другой.
Та сторона, где происходит включение элементов называется хвостом, а где происходит исключение — головой. Поначалу многие не понимают, почему включаются элементы в хвост, а не в голову. Все просто! Давайте представим обычную очередь в буфет, в которой стоит 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;
Суть ее состоит в том, что мы сдвинем указатель на один элемент вправо, так как при исключении мы достаем элемент из головы, то есть из начала.
