Реализация структуры данных "очередь" на C

Введение

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

👀 Предварительный просмотр

$ gcc queue.c -o queue
$./queue
11250

🎯 Задачи

В этом проекте вы научитесь:

• Как реализовать метод front(), чтобы вернуть значение первого элемента в очереди
• Как реализовать метод pop(), чтобы удалить и вернуть первый элемент из очереди
• Как реализовать метод count(), чтобы вернуть количество элементов, находящихся в очереди в данный момент
• Как реализовать метод is_empty(), чтобы проверить, пуста ли очередь

🏆 Достижения

После завершения этого проекта вы сможете:

• Разобраться в основных операциях со структурой данных "очередь"
• Реализовать核心 методы очереди на C
• Применить свои знания о очередях для решения реальных задач

Skills Graph

Реализовать метод front()

В этом шаге вы научитесь реализовывать метод front() очереди.

Метод front() должен возвращать значение первого элемента в очереди. Если очередь пуста, метод должен завершить программу с помощью exit(-1).

Следуйте шагам ниже, чтобы завершить этот шаг:

1. Откройте файл queue.c, расположенный по адресу /home/labex/project/queue.c.
2. Найдите метод front() в коде.
3. Реализуйте метод front() следующим образом:

static int front() {
    if(!phead) {
        exit(-1);
    }
    return phead->val;
}

Метод front() сначала проверяет, является ли указатель phead равным NULL, что указывает на пустую очередь. Если очередь пуста, метод завершает программу с помощью exit(-1).

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

Реализовать метод pop()

В этом шаге вы научитесь реализовывать метод pop() очереди.

Метод pop() должен удалить и вернуть первый элемент из очереди. Если очередь пуста, метод должен завершить программу с помощью exit(-1).

Следуйте шагам ниже, чтобы завершить этот шаг:

1. Откройте файл queue.c, расположенный по адресу /home/labex/project/queue.c.
2. Найдите метод pop() в коде.
3. Реализуйте метод pop() следующим образом:

static int pop() {
    if(!phead) {
        exit(-1);
    }
    int val = phead->val;
    phead = phead->next;
    return val;
}

Метод pop() сначала проверяет, является ли указатель phead равным NULL, что указывает на пустую очередь. Если очередь пуста, метод завершает программу с помощью exit(-1).

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

Реализовать метод count()

В этом шаге вы научитесь реализовывать метод count() очереди.

Метод count() должен возвращать количество элементов, находящихся в очереди в данный момент.

Следуйте шагам ниже, чтобы завершить этот шаг:

1. Откройте файл queue.c, расположенный по адресу /home/labex/project/queue.c.
2. Найдите метод count() в коде.
3. Реализуйте метод count() следующим образом:

static int count() {
    int cnt = 0;
    for(struct node* p = phead; p; p=p->next) {
        cnt++;
    }
    return cnt;
}

Метод count() инициализирует переменную cnt значением 0. Затем он обходит очередь, следуя указателям next узла phead и его последующих узлов. Для каждого встреченного узла метод увеличивает переменную cnt. Наконец, метод возвращает значение cnt, которое представляет количество элементов в очереди.

Реализовать метод is_empty()

В этом шаге вы научитесь реализовывать метод is_empty() очереди.

Метод is_empty() должен возвращать 1, если очередь пуста, и 0 в противном случае.

Следуйте шагам ниже, чтобы завершить этот шаг:

1. Откройте файл queue.c, расположенный по адресу /home/labex/project/queue.c.
2. Найдите метод is_empty() в коде.
3. Реализуйте метод is_empty() следующим образом:

static int is_empty() {
    return phead == NULL;
}

Метод is_empty() просто проверяет, равен ли указатель phead NULL, что указывает на пустую очередь. Если phead равен NULL, метод возвращает 1, что означает, что очередь пуста. В противном случае он возвращает 0, что означает, что очередь не пуста.

Поздравляем! Теперь вы реализовали все необходимые методы для структуры данных "очередь". Теперь вы можете скомпилировать и выполнить программу, чтобы протестировать функциональность очереди.

4. Компилировать и выполнять:

$ gcc queue.c -o queue
$./queue
00000

Ожидаемый вывод выглядит следующим образом:

$ gcc queue.c -o queue
$./queue
11250

Резюме

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