Поиск по сайту:

Создание очереди в C

Очередь в C — это, по сути, линейная структура данных для хранения элементов данных и управления ими. Он следует порядку «первым пришел — первым вышел» (FIFO).

В очередях первый элемент, введенный в массив, является первым элементом, который будет удален из массива.

Например, давайте рассмотрим сценарий киоска по бронированию билетов на автобус. Здесь следует мода очереди программирования C. Билеты распределяются по принципу «первым пришел – первым обслужен», т. е. тот, кто первым войдет, первым получит билеты.

Очередь открыта с обоих концов. Один конец предназначен для вставки данных, а другой конец для удаления данных.

Очередь может быть реализована на любом языке программирования, таком как C, Java, Python и т. д.

Операции, связанные с очередью в C

Очередь, являющаяся абстрактной структурой данных, обеспечивает следующие операции для манипулирования элементами данных:

  • isEmpty(): чтобы проверить, пуста ли очередь
  • isFull(): чтобы проверить, заполнена ли очередь или нет
  • dequeue(): удаляет элемент из передней части очереди
  • enqueue(): вставляет элементы в конец очереди
  • Передний: элемент указателя, отвечающий за получение первого элемента из очереди
  • Rear: элемент указателя, отвечающий за получение последнего элемента из очереди

Работа со структурой данных очереди

Очередь следует схеме «первый пришел — первый обслужен». Первый элемент первым извлекается из списка элементов.

    Указатели
  • Передний и Задний сохраняют запись о первом и последнем элементе в очереди.
  • Сначала нам нужно инициализировать очередь, установив Front=-1 и Rear=-1
  • Чтобы вставить элемент (поставить в очередь), нам нужно проверить, не заполнена ли уже очередь, т. е. проверить условие переполнения. Если очередь не заполнена, нам придется увеличить значение индекса Rear на 1 и поместить элемент в позицию переменной указателя Rear. Когда мы сможем вставить первый элемент в очередь, нам нужно установить значение Front равным 0.
  • Чтобы удалить элемент (удалить из очереди) из очереди, нам нужно проверить, не пуста ли уже очередь, т. е. проверить условие потери значимости. Если очередь не пуста, нам придется удалить и вернуть элемент в позиции переднего указателя, а затем увеличить значение переднего индекса на 1. Когда мы доберемся до удаления последнего элемента из очереди, у нас будет чтобы установить значения переднего и заднего индекса на -1.

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

Очереди в C могут быть реализованы с использованием массивов, списков, структур и т. д. Ниже мы реализовали очереди с использованием массивов в C.

Пример:

#include <stdio.h>
# define SIZE 100
void enqueue();
void dequeue();
void show();
int inp_arr[SIZE];
int Rear = - 1;
int Front = - 1;
main()
{
    int ch;
    while (1)
    {
        printf("1.Enqueue Operation\n");
        printf("2.Dequeue Operation\n");
        printf("3.Display the Queue\n");
        printf("4.Exit\n");
        printf("Enter your choice of operations : ");
        scanf("%d", &ch);
        switch (ch)
        {
            case 1:
            enqueue();
            break;
            case 2:
            dequeue();
            break;
            case 3:
            show();
            break;
            case 4:
            exit(0);
            default:
            printf("Incorrect choice \n");
        } 
    } 
} 
 
void enqueue()
{
    int insert_item;
    if (Rear == SIZE - 1)
       printf("Overflow \n");
    else
    {
        if (Front == - 1)
      
        Front = 0;
        printf("Element to be inserted in the Queue\n : ");
        scanf("%d", &insert_item);
        Rear = Rear + 1;
        inp_arr[Rear] = insert_item;
    }
} 
 
void dequeue()
{
    if (Front == - 1 || Front > Rear)
    {
        printf("Underflow \n");
        return ;
    }
    else
    {
        printf("Element deleted from the Queue: %d\n", inp_arr[Front]);
        Front = Front + 1;
    }
} 
 
void show()
{
    
    if (Front == - 1)
        printf("Empty Queue \n");
    else
    {
        printf("Queue: \n");
        for (int i = Front; i <= Rear; i++)
            printf("%d ", inp_arr[i]);
        printf("\n");
    }
}

Выход:

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 10

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 20

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 3
Queue: 
10 20 

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 2
Element deleted from the Queue: 10

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations: 3
Queue: 
20

Реализация очереди с использованием стеков

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

Очередь может быть реализована с использованием стеков одним из следующих способов:

  • Удорожание операции постановки в очередь
  • Удорожание операции удаления из очереди

Метод 1: сделать операцию постановки в очередь дорогостоящей

Предположим, два стека: S1 и S2 для реализации операций с очередью с использованием одного и того же.

  • Если S1 не пуст, поместите все элементы в стек 2 (S2)
  • Чтобы выполнить операцию постановки в очередь, мы предположим, что «x» — это элемент, который нужно ввести в очередь. Мы поместим «x» обратно в стек S1, чтобы он оказался наверху.
  • Далее поместите все элементы стека S2 обратно в стек S1.

Примечание. Временная сложность операции постановки в очередь будет O(n).

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

Примечание. Временная сложность операции удаления из очереди будет O(1).

Если вы проанализируете временные сложности операций Enqueue и Dequeue с использованием стека, вы обнаружите, что операция Enqueue намного дороже, чем операция Dequeue.

Таким образом, как упоминалось выше, мы делаем так, чтобы первый введенный или самый старый введенный элемент оставался на вершине стека S1, чтобы он удалялся при вызове операции удаления из очереди.

Способ 2: сделать операцию удаления из очереди дорогостоящей

Давайте снова предположим два стека: S1 и S2 для реализации операций с очередями с использованием одного и того же.

  • Чтобы реализовать операцию постановки в очередь, мы вставляем вновь введенный элемент в верхнюю часть стека S1. Таким образом, временная сложность операции постановки в очередь с использованием стеков становится равной O(1).
  • Для реализации операции удаления из очереди он проверяет состояние потери памяти стека S1 и S2. Если оба стека окажутся пустыми, возникнет ошибка.
  • Если стек S2 пуст, а S1 не пуст, то все элементы из стека S1 перемещаются в стек S2, а верхний элемент стека S2 извлекается и возвращается из операции удаления из очереди.
  • Таким образом, временная сложность операции удаления из очереди с использованием стеков становится O(n).

Применение структуры данных очереди

  • Планирование ЦП
  • Расписание дисков
  • Асинхронная передача данных между процессорами, например файловый ввод-вывод и т. д.
  • Алгоритм поиска в ширину (BFS)

Заключение

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

Рекомендации

  • Очередь в C
  • Очередь с использованием стеков