Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.93
dihlofos
Бродяга
 Аватар для dihlofos
302 / 256 / 17
Регистрация: 27.08.2010
Сообщений: 553
05.04.2011, 07:01     Очередь с кольцевым буфером #1
Добрый день. Решаю вобщем одну задачку, но сомневаюсь в правильности и оптимальности кода.

Собственно задача: организовать очередь (по принципу 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;
}
* На обнуление элементов буфера при удалении не обращайте внимание -
сделал просто для наглядности и проверки корректности.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2011, 07:01     Очередь с кольцевым буфером
Посмотрите здесь:

C++ Задача по кольцевым спискам
C++ Реализация 2х потоков, работа с буфером, механизм семафоров
C++ Терпеливая сортировка с обычным буфером
C++ Очередь
C++ Очередь
C++ C++ Очередь
C++ Интернет радио, как осуществить работу с буфером?
Очередь, теория. Очередь на шести стеках C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
05.04.2011, 07:34     Очередь с кольцевым буфером #2
Ввёл дополнительный параметр - длина очереди (для проверок на пустоту/переполнение), как красиво без него обойтись - не придумал.
Судя по результату программы Вы используете push_allocator и pop_allocator (либо аналогичную реализацию). Изначально оба указывают на array[0]. Причем для любого из них, после array[4] идет array[0]. Если после добавления элемента выполняется условие push_allocator == pop_allocator - то очередь полна. Так же, если после изъятия элемента выполняется условие pop_allocator == push_allocator, то очередь пуста;
dihlofos
Бродяга
 Аватар для dihlofos
302 / 256 / 17
Регистрация: 27.08.2010
Сообщений: 553
05.04.2011, 07:49  [ТС]     Очередь с кольцевым буфером #3
Да, так оно и есть. Но в том то и дело, что это условие можно проверить после добавления/удаления. Мне же нужно проверить перед этим. Банальная замена условий на:
C++
1
if ( tail == head )
ни к чему хорошему не приведёт. Условие изначально удовлетворится, и буфер будет будто бы переполнен.
Yandex
Объявления
05.04.2011, 07:49     Очередь с кольцевым буфером
Ответ Создать тему
Опции темы

Текущее время: 09:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru