Введение
Очередь — это линейная структура данных на языке C, которая придерживается правила FIFO (First In, First Out). Массивы или связанные списки могут использоваться для статической или динамической реализации. В реализации массива элементы добавляются в конец очереди и удаляются из начала. И операции вставки, и операции удаления ищут обстоятельства переполнения и потери значимости соответственно. Компоненты очереди также можно распечатать с помощью операции отображения. Память динамически выделяется для каждой записи в реализации связанного списка, и операции вставки и удаления имеют аналогичный ход. Однако для связанных списков не существует условия переполнения очереди. Обработка данных становится эффективной благодаря знанию того, как очереди реализованы в C.
Очередь в C
- Представьте, что вы стоите в очереди, чтобы купить билет в кино. Способ настройки очереди известен как очередь. Тот, кто стоит первым в этой очереди, первым покупает билет. Это указывает на то, что человек перед очередью получит обслуживание первым.
- Очередь в C — это не что иное, как линейная структура данных, которая придерживается принципа FIFO (First In, First Out). Передняя часть используется для удаления, а задняя — для вставки.
- Давайте теперь сравним эту идею очереди со структурой данных компьютерного языка Си. Подобно очереди для билетов в кино, очередь в C — это механизм для организации компонентов данных. Так же, как и ожидание билетов в кино, здесь действует принцип "первым пришел, первым ушел" (FIFO).
- Элемент перемещается в конец очереди, когда вы добавляете его в очередь. С технической точки зрения это называется вставкой и происходит в конце очереди. Элемент берется из начала очереди, когда он удаляется из очереди. Первый человек, который присоединится к очереди, также будет первым, кто уйдет, что является основным принципом удаления.
- В языке C очередь представляет собой линейную структуру данных, которая работает аналогично очереди заявок в том смысле, что вы можете добавлять компоненты сзади и удалять их спереди. Это простой способ обработки данных в определенном порядке.
Существует два подхода к построению очереди:
- Статически. Построение очередей в виде массивов позволяет размещать их компоненты данных в статической памяти. Важно отметить, что таким образом очередь получает все характеристики массива.
- Динамически. Очереди реализованы в виде связанных списков, которые используют динамическое выделение памяти для своих компонентов данных. Важно помнить, что очередь в этой технике приобретает все черты связанного списка.
- Основные выводы: в C очереди и стеки могут быть как статическими, так и динамическими, в зависимости от того, как они реализованы.
Реализация очереди в массиве на C
- Перед запуском программы очень важно определить размер очереди.
Вставка
Вставка элементов в очередь происходит из заднего конца. Вставка элемента в очередь также называется постановкой в очередь.
Пример
#include <stdio.h>
#define LIMIT 100
void insert() {
int element;
if (rear == LIMIT - 1) {
printf("Queue Overflow\n");
} else {
if (front == -1) {
front = 0;
}
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &element);
rear++;
queue[rear] = element;
}
}
Сначала в методе объявляется переменная «элемент» для хранения значения, которое будет добавлено в очередь.
Программа проверяет, равна ли переменная «задний» значению константы «LIMIT — 1». Проверьте, не заполнена ли очередь элементами, и вы не можете добавить больше.
Если условие выполнено, в очередь нельзя добавлять дополнительные компоненты, поскольку она уже заполнена. В этом случае очередь заполнена и никакие вставки не разрешены, поэтому код показывает сообщение «Queue Overflow», чтобы выделить это.
Если условие на шаге 2 ложно, очередь не заполнена, и код переходит к циклу «иначе».
Код проверяет, равна ли переменная «front» -1 внутри предложения «else». Чтобы определить, пуста ли очередь, примените это условие. Если условие выполнено, очередь будет пустой и этот элемент будет добавлен первым. Затем код устанавливает значение «front» в 0 в этой ситуации. На этом этапе должен быть инициализирован передний индекс очереди.
Функция просит пользователя ввести элемент для добавления в очередь после инициализации переднего индекса (при необходимости). На экране написано: «Введите элемент, который нужно вставить в очередь:»
Функция «scanf» используется в коде для чтения пользовательского ввода и сохранения его в переменной «element».
Затем задний индекс перемещается на следующее открытое место в очереди путем увеличения значения «задний» на 1.
Обновленный «задний» индекс используется для определения того, где в очереди должно быть присвоено значение «элемент». На этом этапе элемент фактически добавляется в очередь.
Удаление
Действие по удалению компонентов данных в очереди выполняется спереди. Dequeue — частое название этого процесса. Когда элемент удаляется из очереди, элемент в начале очереди удаляется, чтобы освободить место для следующего в очереди элемента, к которому можно получить доступ или удалить.
Пример
void delet()
{
if (front == - 1 || front > rear)
{
printf("Stack Underflow");
}
else
{
printf("The deleted element in the queue is: %d\n", queue[front]);
front++;
}
}
Первый тест определяет, больше ли передняя переменная, чем задняя, или равна -1.
Если передний план имеет значение -1, очередь обычно пуста,
когда передняя часть превышает заднюю, все элементы удаляются из очереди. В очереди нет записей для удаления, если хотя бы одно из этих условий выполняется.
Функция выводит сообщение «Очередь не заполнена» при определенных обстоятельствах, чтобы показать, что очередь пуста и удаление не может быть завершено.
Блок else достигается, если первое условие ложно (очередь не пуста). Когда в очереди есть элементы, этот блок выполняется.
Линия фронт++; увеличивает значение front на 1 после печати элемента.
При перемещении переднего указателя на одну позицию вперед это действие фактически удаляет элемент из очереди.
Подводя итог, можно сказать, что метод delet() определяет, пуста ли очередь. Если он не пуст, он удаляет элемент в начале очереди и перемещает передний указатель. Уведомление «Очередь не заполнена» указывает на то, что никакие элементы не могут быть удалены, если очередь пуста.
Отображать
Выкладка по FIFO😎 для мужчин это FIFO, а не FIFA😂😂
Пример
void display()
{
int i;
if (front == -1)
{
printf("Queue Underflow");
}
else
{
printf("The elements of the queue are:\n");
for (i = 0; i < rear; i++)
{
printf("%d\n", queue[i]);
}
}
}
выведите «Queue underflow», если очередь пуста, и мы проверяем это условие по фронту -1.
Код переходит к блоку else, если очередь не пуста (т. е. фронт не равен -1). Когда в очереди есть элементы, этот блок выполняется. Сообщение «Элементы очереди: n» просто отображаются строкой printf («Элементы очереди: n»);.
Элементы очереди перебираются в цикле for (i = front; i = back; i++), начиная с переднего и заканчивая последним. Для доступа к элементам массива очереди используется счетчик циклов I.
Строка printf("%dn", очередь[i]); внутри цикла публикует каждый элемент очереди на отдельной строке.
Пример
#include <stdio.h>
#include <stdlib.h>
#define LIMIT 100 // Max limit of the queue elements
// Global Variables
int queue[LIMIT]; // Array implementation of the queue
int front = -1, rear = -1; // Front and rear pointers
int choice;
// Function prototypes
void insert();
void delet();
void display();
int main() {
printf("Array implementation of a queue\n");
do {
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice! Please try again.\n");
}
} while (choice != 4);
return 0;
}
void insert() {
int element;
if (rear == LIMIT - 1) {
printf("Queue Overflow\n");
} else {
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &element);
if (front == -1) {
front = 0;
}
rear++;
queue[rear] = element;
printf("Element %d has been inserted into the queue.\n", element);
}
}
void delet() {
if (front == -1 || front > rear) {
printf("Queue Underflow\n");
} else {
printf("The deleted element in the queue is: %d\n", queue[front]);
front++;
}
}
void display() {
if (front == -1) {
printf("Queue is empty.\n");
} else {
printf("Elements of the queue are:\n");
for (int i = front; i <= rear; i++) {
printf("%d\n", queue[i]);
}
}
}
Максимальное количество элементов, которые могут храниться в очереди, определяется определением кода константы LIMIT, которая имеет значение 100.
Объявляет глобальные переменные: очередь: очередь будет реализована с использованием массива.
Спереди и сзади: указывает на начало и конец очереди с помощью указателей. Изначально для них установлено значение -1, что означает пустую очередь.
выбор — это переменная, используемая для хранения выбора меню пользователя.
В коде определены три операции над очередью: вставка(), удаление() и показ(). Позже в коде эти функции будут определены.
Объявлена функция main(), с которой начинается программа. «Реализация массива очереди» представлена в качестве вступительного сообщения. До тех пор, пока пользователь не решит выйти, меню периодически отображается, и действия выполняются в очереди с использованием цикла do-while.
Пункты меню отображаются внутри цикла, и пользователю предлагается ввести свой выбор с помощью метода scanf(). Чтобы ответить на выбор пользователя,
Используется оператор switch:
Метод вставки() используется для добавления элемента в очередь, если выбран вариант 1.
Метод delet() используется для удаления элемента из очереди, если выбран вариант номер два.
Метод display() вызывается для отображения компонентов очереди, если выбран вариант 3.
Если выбрана опция 4, программа завершается с помощью выхода (0). Сообщение об ошибке отображается, если ни один из параметров не выбран.
определение функции вставки () Она проверяет, имеет ли конец строки максимальную длину. В этом случае функция выводит сообщение «Queue Overflow», поскольку очередь заполнена.
Пользователю предлагается ввести элемент для вставки, если очередь не заполнена. Он устанавливается в 0, если фронт равен -1, что означает пустую очередь.
Введенный элемент помещается в заднюю позицию в массиве очереди после увеличения задней части. Далее следует печать сообщения об успешном завершении.
определение функции delet(). Она определяет, является ли передняя часть нулевой или больше задней, что обозначает пустую строку. Если true, печатается «Очередь не заполнена».
Элемент в передней позиции отображается как удаленный элемент, а передняя часть увеличивается, чтобы удалить элемент из очереди, если очередь не пуста.
Display() определяется следующим образом: проверяется, равен ли фронт -1, что означает пустую очередь. Если это правда, печатается «Очередь пуста». Если в очереди есть какие-либо элементы, он отображает «Элементы очереди:», а затем перебирает массив очереди, печатая каждый элемент по мере его поступления.
Вывод
Связанный список
- Как мы только что упомянули, связанные списки позволяют динамически распределять память для элементов данных очереди. В результате размер очереди определяется во время работы программы и не требует предварительного определения.
- Три основные операции организации очереди — вставка, удаление и отображение — следуют той же схеме, что и реализация массива.
- Важно отметить, что реализация связанных списков очередей не поддерживает ситуацию переполнения очереди, и размер стека не задан заранее. Однако условие потери очереди по-прежнему действует.
Мы можем добавлять элементы в очередь следующим образом:
Пример
void insert()
int ele
struct node *temp = malloc(sizeof(struct node*));
if (temp == NULL)
{
return NULL
}
printf("Please enter an elements: ");
scanf("%d", $ele);
temp->data = ele;
temp->link = NULL;
if (rear == NULL)
{
front = rear = temp;
}
else
{
rear->link = temp;
rear = temp;
}
}
В первой строке метода insert() объявляется переменная ele, которая будет содержать введенный пользователем элемент.
Затем объявляется временная переменная-указатель типа struct node*. Чтобы сохранить введенный элемент, будет создан новый узел с использованием этой ссылки.
Чтобы освободить память для нового узла, используется метод malloc(). Размер структуры рассчитывается с использованием размера (узла структуры*).
Функция возвращает NULL, если выделение памяти не удалось (т. е. если значение temp равно NULL).
Затем код просит пользователя ввести элемент с помощью функции printf(), чтобы отобразить подсказку, если процесс выделения памяти прошел успешно. Необходимо ввести целое число, как указано спецификатором формата %d.
Введенный пользователем элемент считывается методом scanf() и сохраняется в переменной ele. Адрес переменной ele получается с помощью оператора &, так что scanf() может сохранить там значение.
Используя синтаксис temp-›data, код вставляет значение ele в поле данных вновь созданного узла.
Поле ссылки вновь сгенерированного узла устанавливается в NULL, чтобы показать, что это последний узел в связанном списке.
Затем проверяется задний указатель, чтобы убедиться, что он равен NULL, что означает пустой связанный список.
Наличие узлов указывает на то, что связанный список не пуст. В этом случае вновь созданный узел (временный) упоминается в поле ссылки существующего тылового узла. Затем новый узел становится новым конечным узлом в связанном списке путем обновления заднего указателя, чтобы он также указывал на него.
Удалить
Пример
void dele()
{
struct node* temp; // Declare a temporary pointer variable
temp = front; // Assign the value of front pointer to temp
if (front == NULL) // Check if the queue is empty (front is NULL)
{
printf("Queue Underflow");
// Set front and rear pointers to NULL to indicate an empty queue
front = rear = NULL;
}
else
{
// Print the value of the data in the front node
printf("The deleted element is: %d\n", front->data);
// Move the front pointer to the next node in the queue
front = front->link;
// Deallocate the memory occupied by the previous front node
free(temp);
}
}
Отображать
Пример
void display()
{
counter = 0;
struct node* temp;
temp = front;
if (front == NULL) // Check if the queue is empty (front is NULL)
{
printf("Queue Underflow");
}
else
{
printf("The queue elemtns are: %d\n");
while (temp) // Loop through the nodes until temp becomes NULL
{
// Print the value of data in the current node
printf("%d", temp->data);
temp = temp->link; // Move to the next node in the queue
counter++; // Increment the counter variable
}
}
}
Полный код
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *link;
} *front, *rear;
void insert(); // Function used to insert an element into the queue
void delet(); // Function used to delete an element from the queue
void display(); // Function used to display all the elements in the queue according to the FIFO rule
int main()
{
printf("Welcome to DataFlair tutorials!\n\n");
int choice;
printf("LINKED LIST IMPLEMENTATION OF QUEUES\n\n");
do
{
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while (choice != 4);
return 0;
}
void insert()
{
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &temp->data);
temp->link = NULL;
if (rear == NULL)
{
front = rear = temp;
}
else
{
rear->link = temp;
rear = temp;
}
}
void delet()
{
struct node *temp;
temp = front;
if (front == NULL)
{
printf("Queue underflow\n");
front = rear = NULL;
}
else
{
printf("The deleted element from the queue is: %d\n", front->data);
front = front->link;
free(temp);
}
}
void display()
{
struct node *temp;
temp = front;
int cnt = 0;
if (front == NULL)
{
printf("Queue underflow\n");
}
else
{
printf("The elements of the queue are:\n");
while (temp)
{
printf("%d\n", temp->data);
temp = temp->link;
cnt++;
}
}
}
Код создает узел структуры, который представляет узел в очереди и включает в себя необходимые файлы заголовков. Каждый узел имеет ссылку-указатель на следующий узел, а также поле данных типа int.
Существуют определенные прототипы функций для show(), delete() и insert().
Метод main() определен. Отображается приветственное сообщение, и пользователь может выбрать из меню действий очереди. Он постоянно запрашивает ввод данных пользователем, используя цикл do-while, пока не будет показана опция 4 (выход).
Удалить() — это определенная функция. Он удаляет первый элемент очереди. Подтвердив, что фронт равен NULL, он сначала определяет, пуста ли очередь. Он отображает содержимое переднего узла, изменяет передний указатель для ссылки на следующий узел и освобождает память предыдущего переднего узла, если очередь не пуста.
Display() — это заданная функция. Он перемещается по очереди и показывает каждый компонент. Подтвердив, что фронт равен NULL, он определяет, пуста ли очередь.
Если очередь не пуста, она начинается с переднего узла и проходит по связанному списку, выводя содержимое каждого узла и изменяя временную ссылку так, чтобы она указывала на последующий узел.
Выход
Круговая очередь
Циклическая очередь — это тип структуры данных, изображающий очередь, в которой связаны последний и первый элементы. Благодаря этой круговой ссылке мы можем воспользоваться свободными местами, оставшимися после удаления элементов из очереди. Другими словами, он создает цикл, который эффективно использует доступную оперативную память.
Структура. Массив с передними и задними указателями образует циклическую очередь. Содержимое очереди хранится в массиве, а передний и задний указатели идентифицируют первый и последний элементы в очереди соответственно.
Циклическое соединение. В отличие от обычной линейной очереди, обратный указатель циклической очереди может возвращаться к началу массива. Мы можем использовать свободные места, оставшиеся после удаления элементов из очереди, благодаря этой круговой ссылке.
Пустая очередь. Изначально передняя и задняя точки имеют значение -1, когда круговая очередь пуста.
Полная очередь:задний указатель находится на одно место позади переднего указателя, когда круговая очередь заполнена. Используя этот критерий, мы можем отличить пустую очередь от заполненной очереди.
Операция постановки в очередь: задний указатель увеличивается, и новый элемент помещается туда для добавления в циклическую очередь (операция постановки в очередь). Задний указатель зацикливается на начало массива, если он приближается к концу массива (циклическое поведение).
Операция удаления из очереди: мы поднимаем передний указатель и извлекаем элемент из этого места, чтобы удалить элемент из циклической очереди (операция удаления из очереди). Передний указатель вернется к началу массива, если он достигнет конца массива (круговое поведение).
Переполнение и недополнение. Когда передний указатель догоняет задний указатель, происходит переполнение, означающее, что циклическая очередь заполнена. Когда передний указатель больше заднего, возникает потеря значимости и циклическая очередь пуста.
Обработка переполнения: мы можем либо отказаться от постановки в очередь и показать уведомление о переполнении для обработки переполнения, либо динамически расширить массив, чтобы вместить больше записей.
Обработка недозагрузки: мы можем отображать уведомление при задержке при попытке удаления из очереди в пустой циклической очереди, чтобы устранить недозагрузку.
Вставка
Пример
void insert()
{
// Check if the circular queue is full
if ((front == 0 && rear == LIMIT-1) || (front == rear+1))
{
printf("Queue Overflow\n");
// We need this step to prevent inserting elements when the circular queue is already full.
}
// Check if the circular queue is empty
if (front == -1)
{
front = rear = 0;
// If the queue is empty, set both front and rear pointers to 0, indicating the first element.
}
else
{
printf("Enter the element to be inserted in queue: ");
scanf("%d", &item);
// Check if the rear pointer is at the last position of the queue
if (rear == LIMIT-1)
{
rear = 0;
// If the rear pointer is at the last position, wrap around to the beginning of the queue.
}
else
{
rear++;
// Move the rear pointer to the next position.
}
}
cqueue[rear] = item;
// Insert the element at the current rear position of the circular queue.
}
В циклическую очередь можно добавлять элементы с помощью метода insert(). Емкость циклической очереди проверяется в первом условии if.
Циклическая очередь заполнена и не может больше принимать элементы, если передний указатель находится в первой позиции, а задний указатель — в конечной позиции, или если передний указатель опережает задний указатель на одну позицию. В этой ситуации функция завершает работу и показывает уведомление «Queue Overflow».
Второй оператор if определяет, пуста ли циклическая очередь. Очередь пуста, если передний указатель установлен на -1. В этом случае мы указываем начальное расположение элемента в очереди, устанавливая передний и задний указатели на 0.
Функция просит пользователя ввести элемент для вставки, если круговая очередь не пуста.
Условие if блока else определяет, находится ли задний указатель в последней позиции очереди. Чтобы использовать доступное пространство, если задний указатель находится в конечной позиции, он переходит к началу очереди (позиция 0).
Функция переходит к следующему месту в очереди, увеличивая задний указатель, если он еще не находится в последней позиции.
Затем введенный пользователем элемент помещается в текущую обратную позицию циклической очереди.
Удаление
Пример
void delet()
{
// Check if the circular queue is empty
if (front == -1)
{
printf("Queue Underflow\n");
// We need this step to prevent deleting elements when the circular queue is empty.
}
printf("Element deleted from queue is: %d\n", cqueue[front]);
// Print the element being deleted from the front of the circular queue.
// Check if the queue has only one element
if (front == rear)
{
front = rear = -1;
// If the queue has only one element, set both front and rear pointers to -1, indicating an empty queue.
}
else
{
// Check if the front pointer is at the last position of the queue
if (front == LIMIT-1)
{
front = 0;
// If the front pointer is at the last position, wrap around to the beginning of the queue.
}
else
{
front++;
// Move the front pointer to the next position.
}
}
}
Член круговой очереди может быть удален с помощью метода delet(). Оператор if определяет, пуста ли циклическая очередь.
Очередь нельзя использовать для каких-либо операций удаления, если передний указатель установлен на -1, что указывает на то, что она пуста. В этой ситуации функция завершает работу и показывает уведомление «Очередь не заполнена».
Функция печатает удаляемый элемент из начала циклической очереди, если очередь не пуста.
Условие if блока else определяет, содержит ли очередь только один элемент. Очередь содержит только один член, если передний и задний указатели равны. В этом случае мы указываем пустую очередь, устанавливая переднюю и заднюю точки на 1.
Функция определяет, находится ли передний указатель в последней позиции очереди, если в очереди несколько элементов. Если передний указатель находится на последнем месте в очереди, он перемещается на первое место в очереди (положение 0).
Функция переходит к следующему месту в очереди, увеличивая передний указатель, если он еще не находится в последней позиции.
Отображать
Пример
void display()
{
int front_position = front;
int rear_position = rear;
// Check if the circular queue is empty
if (front == -1)
{
printf("Queue underflow\n");
// We need this step to prevent displaying elements when the circular queue is empty.
}
printf("The elements of the queue are:\n");
// Check the position of the front and rear pointers
if (front_position <= rear_position)
{
// Loop through the elements from front to rear
while (front_position <= rear_position)
{
printf("%d\n", cqueue[front_position]);
front_position++;
}
}
else
{
// Loop through the elements from front to the last position in the queue
while (front_position <= LIMIT-1)
{
printf("%d\n", cqueue[front_position]);
front_position++;
}
front_position = 0; // Reset the front position to the beginning of the queue
// Loop through the elements from the beginning to the rear position
while (front_position <= rear_position)
{
printf("%d\n", cqueue[front_position]);
front_position++;
}
}
}
Объяснение
Все элементы циклической очереди отображаются в соответствии с правилом FIFO с помощью функции display().
Значения переднего и заднего указателей используются для инициализации переменных front_position и Rear_position соответственно.
Оператор if определяет, пуста ли циклическая очередь. Очередь пуста и нет записей для отображения, если передний указатель установлен на -1. В этой ситуации функция завершает работу и показывает уведомление «Очередь не заполнена».
Функция пишет сообщение о том, что она раскроет содержимое очереди, если очередь не пуста.
Расположение переднего и заднего указателей проверяется в следующем операторе if. Элементы сохраняются последовательно спереди назад, если переднее положение меньше или равно заднему положению.
Затем функция начинает цикл, который повторяется от передней позиции к задней позиции в этой ситуации. Каждый элемент в текущем месте печатается во время цикла.
Элементы переходят от конца очереди к началу, если переднее положение больше, чем заднее.
В этом случае функция начинает первый цикл, который перебирает позиции в очереди от первой до последней (LIMIT-1). Каждый элемент в текущем месте печатается во время цикла.
Передняя позиция сбрасывается на 0, чтобы вернуться к началу очереди после достижения последнего места в очереди.
Затем функция вводит второй цикл, который повторяется от начала очереди к концу. Каждая итерация цикла
Для стека перейдите по этой ссылке:
Заключение
придерживаясь правила FIFO. Он предлагает действия по вставке, удалению и отображению, и это можно сделать с использованием массивов или связанных списков. Реализация массива решает проблемы переполнения и потери значимости, но требует, чтобы размер очереди был указан заранее. С другой стороны, подход связанного списка не имеет условия переполнения и допускает динамическое выделение памяти. Вы можете эффективно организовывать и обрабатывать данные последовательным образом, если понимаете лежащие в основе идеи и то, как очереди реализованы в C.
С уважением, Норан❤️
