Круговая очередь в C: как реализовать?
Опубликовано: 2020-10-23Данные располагаются в циклической очереди по круговому шаблону, где последний элемент соединен с первым элементом. В отличие от линейной очереди, где задачи выполняются по принципу FIFO (First In First Out), порядок выполнения задач в циклической очереди может меняться. Операции вставки и удаления можно выполнять в любом месте.
Круговая очередь более эффективна, чем линейная очередь. В графическом представлении циклической очереди вы можете заметить, что передняя и задняя позиции связаны, что делает ее кругом, в котором операции всегда выполняются на основе FIFO. Каждый новый элемент добавляется в конце и удаляется в начале. Круговая очередь имеет лучшее использование и имеет временную сложность O (1).
Источник
Оглавление
Применение циклической очереди
- Планирование ЦП: Циклические очереди используют пустые области памяти, которые находятся в линейных очередях.
- Система трафика: в системе трафика с помощью круговых очередей светофоры работают через заданный интервал времени.
- Управление памятью. Операционные системы часто поддерживают ряд процессов, готовых к выполнению или ожидающих наступления определенного события.
Изучите: Программа C для сортировки пузырьком: Сортировка пузырьком на C
Пример кода с объяснением
Строка 1: // (1) Препроцессоры
Строка 2: // Установить лимит очереди на 5 элементов
Строка 3: #include<stdio.h>
Строка 4: #define LIM 5
Строка 5: // (2) объявления типа данных очереди
Строка 6: // данные содержат данные; delPos, позиция для удаления; длина, нет. из
Строка 7: // элементы, находящиеся в данный момент в очереди
Строка 8: typedef struct queue {
Строка 9: int data[LIM], delPos, длина;
Строка 10: } Q;
Строка 11: // (3) Глобальные объявления
Строка 12: // Функции и глобальная переменная q типа struct queue
Строка 13: Qq;
Строка 14: void ui_Q_Ops(), insertQel(), deleteQel(), displayQels(), initQ();
Строка 15: // (4) Вызов функции пользовательского интерфейса после инициализации
Строка 16: int main()
Строка 17: {
Строка 18: initQ();
Строка 19: ui_Q_Ops();
Строка 20: вернуть 0;
Строка 21: }
Строка 22: // (5) Инициализировать очередь
Строка 23: void initQ()
Строка 24: {
Строка 25: q.length = 0;
Строка 26: q.delPos = 0;
Строка 27: }
Строка 28: // (6) Menu Driven Loop вызывает правильные функции
Строка 29: void ui_Q_Ops()
Строка 30: {
Строка 31: intchoice=0;
Строка 32: ввод символов[16];
Строка 33: пока(выбор!=4){
Строка 34: printf(" \n ———————-\n ");
Строка 35: printf(" 1. Вставить в очередь \n ");
Строка 36: printf(" 2. Удалить из очереди \n ");
Строка 37: printf(" 3. Показать элементы очереди \n ");
Строка 38: printf(" 4. Выход из программы \n ");
Строка 39: printf("Введите выбор: ");
Строка 40: if (fgets(input, 15, stdin) != NULL){
Строка 41: если (sscanf(input, «%d», &choice) == 1){
Строка 42: переключатель(выбор){
Строка 43: случай 1: insertQel();
Строка 44: перерыв;
Строка 45: случай 2: deleteQel();
Строка 46: перерыв;
Строка 47: случай 3: displayQels();
Строка 48: перерыв;
Строка 49: случай 4: возврат;
Строка 50: по умолчанию: printf("Неверный выбор\n ");
Строка 51: продолжить;
Строка 52: }
Строка 53: } еще
Строка 54: printf("Неверный выбор\n");
Строка 55: }
Строка 56: }
Строка 57: }
Строка 58: // (7) Вставить в очередь
Строка 59: // Если длина равна MAX Limit, очередь заполнена, иначе вставить
Строка 60: // круговое достижение с суммой длины и модуля delPos с помощью MAX Limit
Строка 61: // и увеличиваем длину
Строка 62: void insertQel()
Строка 63: {
Строка 64: int el, inspos;
Строка 65: ввод символов[16];
Строка 66: если (q.length == LIM){
Строка 67: printf("Очередь заполнена\n");
Строка 68: возврат;
Строка 69: }
Строка 70: inspos = (q.delPos + q.length) % LIM;
Строка 71: printf("Введите элемент для вставки: ");
Строка 72: if (fgets(input, 15, stdin) != NULL){
Строка 73: если (sscanf(ввод, «%d», &el)){
Строка 74: q.data[inspos] = el;
Строка 75: q.length++;
Строка 76: } еще
Строка 77: printf("Неверный ввод\n");
Строка 78: }
Строка 79: }
Строка 80: // (8) Удалить из очереди
Строка 81: // Если длина равна 0, очередь пуста, иначе удалить в delPos
Строка 82: // и уменьшаем длину
Строка 83: void deleteQel()
Строка 84: {
Строка 85: если (q.length == 0){
Строка 86: printf("Очередь пуста\n");
Строка 87: } еще {
Строка 88: printf("Удален элемент %d\n", q.data[q.delPos]);
Строка 89: q.delPos = (q.delPos + 1) % LIM;
Строка 90: q.length–;
Строка 91: }
Строка 92: }
Строка 93: // (9) Показать элементы очереди
Строка 94: // Отображаем по кругу, запуская цикл, начинающийся с delPos
Строка 95: // и добавление итератора и модуля по Max Limit
Строка 96: void displayQels()
Строка 97: {
Строка 98: интервал i;
Строка 99: если (q.length == 0){
Строка 100: printf("Очередь пуста\n");
Строка 101: } иначе {
Строка 102: printf("Элементы очереди: ");
Строка 103: for(i = 0; i < q.length; i++){
Строка 104: printf("%d", q.data[(q.delPos+i)%LIM]);
Строка 105: }
Строка 106: printf("\n");
Строка 107: }
Строка 108: }
Строка 109:
Выходы:
Операции с циклической очередью
1. insertQel() — вставка элемента в циклическую очередь
В циклической очереди функция enQueue() используется для вставки элемента в циклическую очередь. В циклической очереди новая функция всегда вставляется в последнюю позицию. Функция enQueue() принимает одно целое значение в качестве параметра и вставляет его в циклическую очередь. Для вставки элемента в циклическую очередь реализованы следующие шаги:
Шаг 1. Проверьте, совпадает ли длина с MAX Limit. Если это правда, это означает, что очередь ЗАПОЛНЕНА. Если он ПОЛНЫЙ, то отобразите «Очередь заполнена» и завершите функцию.
Шаг 2. Если он НЕ ПОЛНЫЙ, вставьте значение, которое циклически достигается с суммой длины и модуля delPos с помощью MAX Limit и увеличения длины.
2. deleteQel() — удаление элемента из циклической очереди
В циклической очереди deQueue() — это функция, используемая для удаления элемента из циклической очереди. В круговой очереди элемент всегда удаляется из первой позиции. Функция deQueue() не принимает никаких значений в качестве параметра. Следующие шаги реализованы для удаления элемента из циклической очереди…
Шаг 1 – Проверьте, ПУСТА ли очередь. (спереди == -1 и сзади == -1)
Шаг 2. Если он ПУСТОЙ, отобразите «Очередь пуста» и завершите функцию.
Шаг 3 – Если он НЕ ПУСТОЙ, отобразите удаленные элементы в соответствии с позициями. После того, как каждый элемент добавлен, перейдите к пределу очереди модов следующей позиции.
3. displayQels() — отображает элементы очереди, присутствующие в циклической очереди. Для отображения элементов циклической очереди реализованы следующие шаги:
Шаг 1 – Проверьте, ПУСТА ли очередь.
Шаг 2. Если длина равна 0, она ПУСТА, затем отобразите «Очередь пуста» и завершите функцию.
Шаг 3. Если он НЕ ПУСТОЙ, определите целочисленную переменную «i».
Шаг 4 – Установите я на 0.
Шаг 5 — Снова отобразите элементы в соответствии с позицией и увеличьте значение на единицу (i++). Повторяйте то же самое, пока 'i <q.length' не станет FALSE.
Циклическая очередь также может быть реализована с использованием связанного списка. Алгоритмы следующие:
- Алгоритм постановки в очередь:
if (FRONT == NULL) // Вставка в пустую очередь
ПЕРЕДНЯЯ = ЗАДНЯЯ = новый узел
конец, если
еще
REAR -> next = newNode // Вставка после последнего элемента
ЗАДНИЙ = новый узел
конец еще
ЗАДНИЙ -> следующий = ПЕРЕДНИЙ
Завершить очередь
- Алгоритм удаления из очереди:
if(FRONT == NULL) // Условие потери значимости
Распечатать «Очередь не заполнена»
конец вывода из очереди
конец, если
else if(FRONT == REAR) // Очередь содержит только один узел
темп = ПЕРЕДНЯЯ -> данные
бесплатно (временно)
ПЕРЕДНЯЯ = ПЕРЕДНЯЯ -> следующая
ЗАДНИЙ -> следующий = ПЕРЕДНИЙ
конец, если
else if (FRONT == N — 1) // Если FRONT — последний узел
front = 0 // Сделать FRONT первым узлом
конец, если
конец вывода из очереди
Читайте также: Python против C: полное параллельное сравнение
Заключение
Структуры данных и алгоритмы имеют большое значение не только в программировании на C, но и в других языках. Его ценность беспрецедентна, и для таких важных тем лучше инвестировать в курсы, разработанные и проводимые экспертами, которые обеспечат отличную добавочную стоимость к вашему портфолио. upGrad предлагает широкий спектр мощных курсов, которые не только повышают ваши навыки, но и создают прочные основы основ.
Он разработан высоко оцененным IIIT-B, где они не только предоставляют контент премиум-качества, но и делают вас частью сильной сети, где вы будете общаться с людьми, которые развиваются на том же карьерном пути, а также с отраслевыми экспертами, которые разрешить ваши сомнения и поддерживать вас каждый раз.
Знакомство с их менталитетом и мыслительным процессом поможет вам. И одна из уникальных вещей, которые вы получаете в upGrad, заключается в том, что вы можете выбрать опции EMI и не тратить много денег.
Мы надеемся, что у вас будет отличная возможность научиться выполнять эти проекты на C. Если вы хотите узнать больше и нуждаетесь в наставничестве от отраслевых экспертов, ознакомьтесь с дипломом PG upGrad & IIIT Banglore в области разработки программного обеспечения с полным стеком .