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

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

Понятие очереди

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

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

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

Реализация очереди

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

Файл Queue_Array.h

/****************************************/
/*			Очередь на массиве			*/
/****************************************/
#ifndef _QUEUE_ARRAY_H_
#define _QUEUE_ARRAY_H_
/*Размер очереди*/
#define SIZE_QUEUE_ARRAY 3
/*Описание исключительных ситуаций*/
const int okQueueArray = 0;									// Все нормально
const int fullQueueArray = 1;								// Очередь переполнена
const int emptyQueueArray = 2;								// Очередь пуста
/**********************************/
/*Переменная ошибок*/
extern int errorQueueArray;
/*Базовый тип очереди*/
typedef int queueArrayBaseType;
/*Дескриптор очереди*/
typedef struct {
queueArrayBaseType buf[SIZE_QUEUE_ARRAY];				// Буфер очереди
unsigned ukEnd;											// Указатель на хвост (по нему включают)
unsigned ukBegin;										// Указатель на голову (по нему исключают)
unsigned len;											// Количество элементов в очереди
} QueueArray;
/********************/
/*Функции работы с очередью*/
void initQueueArray(QueueArray *F);								// Инициализация очереди
void putQueueArray(QueueArray *F, queueArrayBaseType E);		// Включение в очередь
void getQueueArray(QueueArray *F, queueArrayBaseType *E);		// Исключение из очереди
int isFullQueueArray(QueueArray *F);							// Предикат: полна ли очередь
int isEmptyQueueArray(QueueArray *F);							// Предикат: пуста ли очередь
/***************************/
#endif

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

Файл Queue_Array.c

/****************************************/
/*			Очередь на массиве			*/
/****************************************/
#include <stdio.h>
#include "Queue_Array.h"
/*Переменная ошибок*/
int errorQueueArray;
/*Инициализация очереди*/
void initQueueArray(QueueArray *F) {
F->ukBegin = 0;
F->ukEnd = 0;
F->len = 0;
errorQueueArray = okQueueArray;
}
/*Включение в очередь*/
void putQueueArray(QueueArray *F, queueArrayBaseType E) {
/*Если очередь переполнена*/
if (isFullQueueArray(F)) {
return;
}
/*Иначе*/
F->buf[F->ukEnd] = E;									// Включение элемента
F->ukEnd = (F->ukEnd + 1) % SIZE_QUEUE_ARRAY;			// Сдвиг указателя
F->len++;												// Увеличение количества элементов очереди
}
/*Исключение из очереди*/
void getQueueArray(QueueArray *F, queueArrayBaseType *E) {
/*Если очередь пуста*/
if (isEmptyQueueArray(F)) {
return;
}
/*Иначе*/
*E = F->buf[F->ukBegin];								// Запись элемента в переменную
F->ukBegin = (F->ukBegin + 1) % SIZE_QUEUE_ARRAY;		// Сдвиг указателя
F->len--;												// Уменьшение длины
}
/*Предикат: полна ли очередь*/
int isFullQueueArray(QueueArray *F) {
if (F->len == SIZE_QUEUE_ARRAY) {
errorQueueArray = fullQueueArray;
return 1;
}
return 0;
}
/*Предикат: пуста ли очередь*/
int isEmptyQueueArray(QueueArray *F) {
if (F->len == 0) {
errorQueueArray = emptyQueueArray;
return 1;
}
return 0;
}

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

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

#include <stdio.h>
#include <locale.h>
#include "Queue_Array.h"
int main() {
setlocale(LC_CTYPE, "");
/*Тестирование очереди*/
QueueArray F;
queueArrayBaseType b;
puts("Очередь на массиве");
initQueueArray(&F);
putQueueArray(&F, 10);
putQueueArray(&F, 15);
puts("\tВвели: 10, 15\n\tВывод: ");
getQueueArray(&F, &b);
printf("%d ", b);
getQueueArray(&F, &b);
printf("%d\n", b);
return 0;
}

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

  1. Евгений

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

  2. Mike_Device

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *