Очередь с кольцевым буфером

@dihlofos · Регистрация: 27.08.2010

Студворк — интернет-сервис помощи студентам

Добрый день. Решаю вобщем одну задачку, но сомневаюсь в правильности и оптимальности кода.

Собственно задача: организовать очередь (по принципу FIFO), используя в качестве буфера одномерный массив. Предусмотреть функции помещения/извлечения элемента и вывода всех элементов на печать. Буфер для хранения элементов должен быть циклическим, т.е. при достижении конца буфера, продолжить заполнение с его обратной стороны. Сделать также проверку на переполнение буфера.

С виду несложное задание, малость запарился именно на "цикличности". Ввёл дополнительный параметр - длина очереди (для проверок на пустоту/переполнение), как красиво без него обойтись - не придумал. Также пришлось пару дополнительных условий в ф-цию печати очереди добавить, получилось малость громоздко.

Что можете посоветовать по данной проблеме, может я что-то упустил, или что-то переусложнил? Спасибо.

Вот код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <iostream>
#include <cstdlib>
///////////////////////////////////////////////
class Queue
{
public:
    Queue( int size ) // конструктор
    {
        head = tail = length = 0;
 
        // создаём буфер заданного размера
        bufferSize = size;
        arr = new int[bufferSize];
 
        // заполняем буфер нулями*
        for ( int i = 0; i < bufferSize; ++i )
            arr[i] = 0;
    }
//---------------------------------------------
    ~Queue() // деструктор
    {
        delete[] arr;
    }
//---------------------------------------------
    void put( int value ) // помещаем элемент в очередь
    {
        // проверяем, полна ли очередь
        if ( length == bufferSize )
                {
            std::cout << "Queue is full!\n";
            return;
                }
 
        // "зацикливаем" буфер
        if ( tail == bufferSize )
            tail = 0;
    
        // помещаем значение в очередь
        arr[tail] = value;
        ++tail;
        ++length;
    }
//---------------------------------------------
    void get() // извлекаем элемент из очереди
    {
        // проверяем, пуста ли очередь
        if ( length == 0 )
                {
            std::cout << "Queue is empty!\n";
                        return;
                }
 
        // "зацикливаем" буфер
        if ( head == bufferSize )
            head = 0;
 
        // печатаем элемент
        std::cout << "Element = " << arr[head] << "\n";
        arr[head] = 0; // обнуляем элемент буфера*
                ++head;
        --length;
    }
//---------------------------------------------
    void printQueue() const // печатаем очередь
    {
        int i;
 
        std::cout << "Queue is: ";
 
        // проверяем, пуста ли очередь
        if ( length == 0 )
            std::cout << " empty";
        
        // если элементы в буфере идут по порядку
        else if ( tail > head )
        {
            for ( i = head; i < tail; ++i )
                std::cout << arr[i] << ' ';
        }
 
        // если буфер уже "зациклен"
        else
        {
            // выводим часть от головы
            for ( i = head; i < bufferSize; ++i )
                std::cout << arr[i] << ' ';
 
            // выводим часть до хвоста
            for ( i = 0; i < tail; ++i )
                std::cout << arr[i] << ' ';
        }
 
        std::cout << '\n';
 
        // доп. информация
        // std::cout << "Length is: " << length << '\n';
        // std::cout << "Head is: " << head << '\n';
        // std::cout << "Tail is: " << tail << '\n';
    }
//---------------------------------------------
    void printBuffer() const // печать всего буфера*
    {
        std::cout << "Array is: ";
 
        for ( int i = 0; i < bufferSize; ++i )
            std::cout << arr[i] << ' ';
 
        std::cout << '\n';
    }
//---------------------------------------------
private:
    int * arr;  // массив-буфер
    int bufferSize; // размер буфера
    int length; // длина очереди
    int tail;   // конец очереди
    int head;   // начало очереди
};
///////////////////////////////////////////////
int main()
{
    // создаём очередь, макс.длина = 5
    Queue myQueue(5);
 
    // Выводим первоначальную очередь
    myQueue.printBuffer();
    myQueue.printQueue();
 
    std::cout << "______________________________\n";
 
    // помещаем в очередь 6 элементов (1 не влезет)
    for ( int i = 1; i <= 6; ++i )
    {
        myQueue.put( i * 2 );
        myQueue.printBuffer();
        myQueue.printQueue();
        std::cout << "______________________________\n";
    }
 
    // извлекаем из очереди 3 элемента
    for ( int i = 1; i <= 3; ++i )
    {
        myQueue.get();
        myQueue.printBuffer();
        myQueue.printQueue();
        std::cout << "______________________________\n";
 
    }
 
    // помещаем в очередь 3 элемента
    for ( int i = 1; i <= 3; ++i )
    {
        myQueue.put( i * 3 );
        myQueue.printBuffer();
        myQueue.printQueue();
        std::cout << "______________________________\n";
    }
 
    // извлекаем из очереди 6 элементов (1 лишний)
    for ( int i = 1; i <= 6; ++i )
    {
        myQueue.get();
        myQueue.printBuffer();
        myQueue.printQueue();
        std::cout << "______________________________\n";
 
    }
 
    system ("pause");
    return 0;
}

* На обнуление элементов буфера при удалении не обращайте внимание -
сделал просто для наглядности и проверки корректности.

@Vladimir. · 05.04.2011, 07:34

Ввёл дополнительный параметр - длина очереди (для проверок на пустоту/переполнение), как красиво без него обойтись - не придумал.

Судя по результату программы Вы используете push_allocator и pop_allocator (либо аналогичную реализацию). Изначально оба указывают на array[0]. Причем для любого из них, после array[4] идет array[0]. Если после добавления элемента выполняется условие push_allocator == pop_allocator - то очередь полна. Так же, если после изъятия элемента выполняется условие pop_allocator == push_allocator, то очередь пуста;

@dihlofos · 05.04.2011, 07:49 **[ТС]**

Да, так оно и есть. Но в том то и дело, что это условие можно проверить после добавления/удаления. Мне же нужно проверить перед этим. Банальная замена условий на:

C++
1
if ( tail == head )

ни к чему хорошему не приведёт. Условие изначально удовлетворится, и буфер будет будто бы переполнен.

Новые блоги и статьи Все статьи Все блоги /
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .