С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.93
dihlofos
Бродяга
303 / 257 / 17
Регистрация: 27.08.2010
Сообщений: 553
#1

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

05.04.2011, 07:01. Просмотров 4505. Ответов 2
Метки нет (Все метки)

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

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

Задача по кольцевым спискам - C++
Необходимо решить задачу: Составить программу, которая в кольцевой список из n элементов добавляет m новых элементов так, чтобы новый...

Очередь (сделать очередь, чтобы добавляло, удаляло, читало. Не STL.) - C++
Помогите пожалуйста написать очередь. Есть Температура double и ее тип int ну и нужно сделать очередь, чтобы добавляло, удаляло, читало....

Сформировать очередь по файлу целых чисел. Промоделировать очередь в супермаркете - C++
Сформировать очередь по файлу целых чисел. Промоделировать очередь в супермаркете. В каждый момент времени происходит одно из событий:...

Задача на очередь (вывод сообщения, что очередь пуста) - C++
Доброго дня! Есть задачка на очередь, которая работает нормально, только надо добавить код, чтобы выводил сообщение, что очередь пуста.....

Очередь, теория. Очередь на шести стеках - C++
Здравствуйте, пытаюсь побольше найти информации про очереди и их применение в программировании. Из того что я нашел, все описывается лишь...

Работа с буфером обмена - C++
В общем нужна программа, которая по клавише активации(например F10) считывала кол-во символов в буфере обмена и заменяла их другими...

2
Vladimir.
158 / 158 / 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, то очередь пуста;
1
dihlofos
Бродяга
303 / 257 / 17
Регистрация: 27.08.2010
Сообщений: 553
05.04.2011, 07:49  [ТС] #3
Да, так оно и есть. Но в том то и дело, что это условие можно проверить после добавления/удаления. Мне же нужно проверить перед этим. Банальная замена условий на:
C++
1
if ( tail == head )
ни к чему хорошему не приведёт. Условие изначально удовлетворится, и буфер будет будто бы переполнен.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.04.2011, 07:49
Привет! Вот еще темы с ответами:

Терпеливая сортировка с обычным буфером - C++
Доброе время суток ! Объясните принцип работы терпеливой сортировки, желательно на русском, проще и в этой теме.

Интернет радио, как осуществить работу с буфером? - C++
по заданию, мне нужно реализовать работу интернет радио. собираю информацию как хочу сделать: есть сервер (windows), на нем запущена...

Реализация 2х потоков, работа с буфером, механизм семафоров - C++
Год не было С++, а теперь по смежному предмету задали вот такое : Написать программу, содержащую два потока. Первый поток генерирует...

Создать очередь. Добавить элемент в очередь. Удалить элемент из очереди - C++
Нужно создать очередь. Добавить элемент в очередь. Удалить элемент из очереди. Вот моё &quot;творение&quot;. int main() { int...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.