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

Очередь - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.87
TheMachinist
 Аватар для TheMachinist
242 / 174 / 15
Регистрация: 14.06.2010
Сообщений: 422
04.09.2010, 16:19     Очередь #1
Привет всем.
Я тут решаю в общем то простое упражнение - нужно проверить переполнение и опустошение очереди.
Есть у меня небольшая трудность:
как выйти из функции Decueue() (англ.вывести из очереди ) если Очередь пуста(tail == 0)???
Я пробовал exit(1) и return(0), но это все не то.

А главная трудность - по заданию упражнения проверку надо реализовать при помощи оператора %


Я только понимаю что с помощью % можно сделать процесс постановки в очередь бесконечным
(ставя первый элемент выталкивать последний) :

tail = (tail+1)%5;

Кто-нибудь????
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
05.09.2010, 01:53     Очередь #21
Цитата Сообщение от Lavroff Посмотреть сообщение
Дык я как бэ ничего не менял.
Ну у Вас просто код понятнее написан.

NikolaWhite, Вы уж определитесь - Вам стек, очередь, или объяснить, чем они отличаются?
Стек работает по принципу "последним вошёл - первым вышел". Очередь - "Первым вошёл - первым вышел". У Вас Dequeue() возвращает последний помещённый элемент, а должна бы первый...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
05.09.2010, 02:05     Очередь #22
Если я что-то еще понимаю то как-то так...

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
#include <iostream>
#include <stdexcept>
 
class Queue
{
        int head; int tail;
        int q[5];
 
public:
        Queue() : head(0), tail(0) {}
        void Enqueue(int var);
        int GetNum();
int Dequeue();
};
 
void Queue::Enqueue(int var)
{
        if(tail < 5)
        {
        q[tail] = var;
        tail++;
        }
}
 
int Queue::GetNum()
{
        return tail;
}
 
int Queue::Dequeue()
{
    int l=0;
        if(head < 5)
        {
                l=q[head];
                head++;
                return l;
        }
        else
           throw std::runtime_error("Queue is empty!");
}
 
int main()
{
        Queue q1;
setlocale(LC_ALL,"Rus");
 
std::cout << "Вместимость очереди: 5" << std::endl;
std::cout << "Кол-во элементов в очереди после попытки вместить туда 10 элементов: ";
 
        for(int i = 0;i < 10;i++)
                q1.Enqueue(i);
 
        std::cout << q1.GetNum() << std::endl;
 
        std::cout << "Попытка извлечь из очереди 10 элементов: " << std::endl;
        for(int i = 0;i < 10;i++)
        {
                std::cout <<    q1.Dequeue();
        }
 
        std::cin.get();
}
А может и так логичнее...

C++
1
2
3
4
5
6
int Queue::Dequeue()
{
        if(head>4)
           throw std::runtime_error("Queue is empty!");
        return q[head++];
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
05.09.2010, 02:17     Очередь #23
Lavroff, и всё бы ничего, но при таком подходе очередь только один раз заполнится и очистится, повторно объект такого класса использовать не получится. Мало того, элементы должны добавляться и удаляться из очереди в произвольной последовательности (с учётом ограничения размера очереди). Попробуйте не пытаться туда сразу 10 объектов запихнуть, а 5, потом их из очереди извлечь и 5 других записать...
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
05.09.2010, 02:22     Очередь #24
easybudda, Добавляться да, в произвольной. А удаляться насколько я понимаю в зависимости от того как заполнились, ибо FIFO по идее.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
05.09.2010, 02:33     Очередь #25
Lavroff, не, я не про это... Вот в моём примере можно записать 3 элемента, потом прочитать 2, записать 4, прочитать все 5, потом записать ещё пару и прочитать их, а вот с Вашим кодом так не получится...
ForEveR
05.09.2010, 02:36
  #26

Не по теме:

easybudda, Если бы ТС внятно сказал, что он хочет)
А так. Я и не пытался сделать что-то особое)

fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
05.09.2010, 09:08     Очередь #27
Цитата Сообщение от easybudda Посмотреть сообщение
При извлечении первого элемента все остальные прийдётся на шаг влево смещать, а это очень накладно, каким бы образом ни было реализовано.
Именно, поэтому реализация очереди и стека на основе массива отличается именно этим моментом.
Вот пример реализации очереди на основе массива. Как видно в функции pop существует цикл для перемещения элементов, это не страшно для маленьких очередей, но для большого количества элементов просто ужас
Правда код на Си. Но суть должна быть ясна.
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
#include <stdio.h>
 
#define MAX_QUEUE_SIZE 0xF
 
typedef struct QUEUE {
    int array[MAX_QUEUE_SIZE];
    int rear;
} queue_t;
 
void erase(queue_t *q) {
    q->rear = MAX_QUEUE_SIZE;
}
 
int is_empty(queue_t *q) {
    return q->rear == MAX_QUEUE_SIZE;
}
 
void push(queue_t *q, int value) {
    if(q->rear == 0)
        fprintf(stderr, "queue is full\n");
    else
        q->array[--(q->rear)] = value;
}
 
int front(queue_t *q) {
    if(is_empty(q)) {
        fprintf(stderr, "queue is empty\n");
        return 0;
    }
    
    return q->array[MAX_QUEUE_SIZE - 1];
}
 
void pop(queue_t *q) {
    int i;
    
    if(is_empty(q)) {
        fprintf(stderr, "queue is empty\n");
        return;
    }
    
    for(i = MAX_QUEUE_SIZE - 1; i > q->rear; --i)
        q->array[i] = q->array[i-1];
    
    ++(q->rear);
}
 
int main()
{
    int i;
    queue_t q;
    
    erase(&q);
    for(i = 0; i < 10; ++i)
        push(&q, i + 1);
        
    while(!is_empty(&q)) {
        printf("%d -> ", front(&q));
        pop(&q);
    }
    printf("\b\b\b   \n");
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
05.09.2010, 11:29     Очередь #28
Цитата Сообщение от NikolaWhite Посмотреть сообщение
А у меня это не работает почему то, так же как и exit(1)
Это помому, что:
  1. код, который может возбуждать исключения, нужно помещать внутри блока try;
  2. выброшенное исключение нужно обработать внутри соответсвующего блока catch.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
05.09.2010, 12:13     Очередь #29
Nameless One, если выполнение дойдёт до строки
C++
1
throw std::runtime_error("bla bla bla");
то программа и без всяких try/catch грохнется...
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
05.09.2010, 12:20     Очередь #30
Спасибо. Жаль, что в книжке, которую я читал, про это не было написано.
TheMachinist
 Аватар для TheMachinist
242 / 174 / 15
Регистрация: 14.06.2010
Сообщений: 422
05.09.2010, 17:20  [ТС]     Очередь #31
NikolaWhite, Вы уж определитесь - Вам стек, очередь, или объяснить, чем они отличаются?
Извините парни я вчера пересидел за компом - перестал различать стек и очередь.

код, который может возбуждать исключения, нужно помещать внутри блока try;
выброшенное исключение нужно обработать внутри соответсвующего блока catch.
если выполнение дойдёт до строки
Код C++
1
throw std::runtime_error("bla bla bla");
то программа и без всяких try/catch грохнется
Я и так и сяк пробую - не получается.

Если кому не трудно поправьте что не так.
Вот мой код:

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
#include <iostream>
#include <conio.h>
#include <stdexcept>
 
class Queue
{
    int head; int tail;
    int q[5];
 
public:
    Queue() : head(0), tail(0) {}
    void Enqueue(int var);
    int Dequeue();
    int GetNum();
};
 
int Queue::Dequeue()
{
    if(head == tail)
        std::runtime_error("Empty queue.");
    int temp = q[head];
    head++;
    return temp;
}
 
void Queue::Enqueue(int var)
{
    if(tail < 5)
    {
    q[tail] = var;
    tail++;
    }
}
 
int Queue::GetNum()
{
    return tail - head;
}
 
int main()
{
    setlocale(LC_ALL,"Rus");
    Queue q1;
    for(int i = 0;i < 10;i++)
        q1.Enqueue(i);
    std::cout << "Вместимость очереди: 5" << std::endl;
    std::cout <<"Кол-во элементов после попытки вместить 10 элементов: ";
    std::cout << q1.GetNum() << std::endl;
    std::cout << "Попробуем вывести оттуда 10 элементов: " << std::endl;
 
    for(int i = 0;i < 10;i++)
        std::cout << q1.Dequeue() << " ";
    
    _getch();
}
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
05.09.2010, 17:34     Очередь #32
э..
C++
1
2
3
4
5
6
7
8
int Queue::Dequeue()
{
        if(head == tail)
                throw std::runtime_error("Empty queue.");
        int temp = q[head];
        head++;
        return temp;
}
TheMachinist
 Аватар для TheMachinist
242 / 174 / 15
Регистрация: 14.06.2010
Сообщений: 422
05.09.2010, 17:48  [ТС]     Очередь #33
Извиняюсь пропустил
C++
1
throw
, но все равно ошибка. Попробуй(те) запустить в VS.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
05.09.2010, 18:16     Очередь #34
Цитата Сообщение от NikolaWhite Посмотреть сообщение
но все равно ошибка.
Какая? У меня скомпилировалось и запустилось. Выдало ошибку, так оно так и задумано было. Переделайте main()
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
        setlocale(LC_ALL,"Rus");
        Queue q1;
        for(int i = 0;i < 5;i++)
                q1.Enqueue(i);
        std::cout << "Вместимость очереди: 5" << std::endl;
        std::cout <<"Кол-во элементов после попытки вместить 5 элементов: ";
        std::cout << q1.GetNum() << std::endl;
        std::cout << "Попробуем вывести оттуда 5 элементов: " << std::endl;
 
        for(int i = 0;i < 5;i++)
                std::cout << q1.Dequeue() << " ";
        
        _getch();
}
и должно бы работать. Да, выдаёт параноидальное предупреждение во время компиляции, но на него можно забить...
Очередь
TheMachinist
 Аватар для TheMachinist
242 / 174 / 15
Регистрация: 14.06.2010
Сообщений: 422
05.09.2010, 18:53  [ТС]     Очередь #35
Чего я добиваюсь это чтоб при попытке ввести в очередь ,скажем 10 элементов, вводилось только
5(размер массива).
А при попытке извлечь оттуда больше элементов чем вместимость(больше пяти) извлекалось только то
что там в очереди содержится. То есть контролировать чтобы tail никогда не был больше 5, а head не была
меньше 0.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
05.09.2010, 19:41     Очередь #36
Цитата Сообщение от NikolaWhite Посмотреть сообщение
Чего я добиваюсь это чтоб при попытке ввести в очередь ,скажем 10 элементов, вводилось только
5(размер массива).
А при попытке извлечь оттуда больше элементов чем вместимость(больше пяти) извлекалось только то
что там в очереди содержится. То есть контролировать чтобы tail никогда не был больше 5, а head не была
меньше 0.
Проблема в том, что если программа передаёт функции какое-то значение, а функция его игнорирует потому, что очередь уже заполнена - это очень неправильно, но на работе программы не отразится. А вот если программа ждёт от функции какое-то значение, а функция его не может вернуть - что при этом должно происходить?
TheMachinist
 Аватар для TheMachinist
242 / 174 / 15
Регистрация: 14.06.2010
Сообщений: 422
05.09.2010, 20:53  [ТС]     Очередь #37
Я сдаюсь.
Вот все чего я добился:

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
#include <iostream>
#include <conio.h>
using namespace std;
 
class Queue
{
    int head; int tail; int count;
    int q[5];
 
public:
    Queue() : head(0), tail(0), count(0) {}
    int Enqueue(int var);
    int Dequeue();
    int GetNum();
};
 
int Queue::Enqueue(int var)
{
if(tail == 0 & count == 5)
return(0);
 
    count++;
    q[tail] = var;
    tail = (tail+1)%5;
}
 
int Queue::Dequeue()
{
if(head == tail & count == 0)
return(0);
 
count--;
    int temp = q[head];
   head = (head+1)%5;
   return temp;
}
 
int Queue::GetNum()
{
    return count;
}
 
int main()
{
    Queue q1;
    setlocale(LC_ALL,"Rus");
 
    cout << "Вместимость очереди: 5" << endl;
    
for(int i = 0;i < 10;i++)
q1.Enqueue(i);
cout << "Кол-во элементов в очереди после попытки ввести в нее 10 элементов: ";
    cout << q1.GetNum() << endl;
 
cout << "Попробуем вывести 10 элементов из очереди которая содержит 5 элементов: " << endl;
for(int i = 0;i < 10;i++)
cout << q1.Dequeue() << " ";
cout << endl;
 
cout << "Кол-во элементов в очереди после извлечения: " << q1.GetNum() << endl;
 
    _getch();
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
05.09.2010, 21:28     Очередь #38
Цитата Сообщение от NikolaWhite Посмотреть сообщение
if(head == tail & count == 0)
правильнее
C++
1
if(head == tail && count == 0)
но и так должно отработать, а вот
Цитата Сообщение от NikolaWhite Посмотреть сообщение
return(0);
занчит - значения 0 в очереди быть не может?
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
05.09.2010, 23:44     Очередь #39
C++
1
2
3
4
5
6
7
8
9
int Queue::Enqueue(int var)
{
if(tail == 0 & count == 5)
return(0);
 
        count++;
        q[tail] = var;
        tail = (tail+1)%5;
}
Зачем возвращает int?

По правилам игры, если места в очереди нет, удаляй первый элемент, сдвигай, в макушку новое число.
Если правила упростить, пусть функция возвращает bool, пусть процесс "засовывания" прерывается. Какой смысл пытатся засунуть седьмое число если уже для шестого места нет?? А если массив размером 5 а попыток засунуть 1000000000? Будешь каждый раз пытатся засунуть пока числа не кончатся? За такой перфоманс тебя с работы уволят.)

Добавлено через 2 часа 5 минут
Вот, максимально упростил. Способ реализовать очередь через массив не сдвигая индексы к началу. Понаблюдай за поведением проги, понажимай 1 и 2 , 3 - выход. Тут уже столько сказали что добавлять в принципе нечего.
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
#include <iostream>
#include <string>
using namespace std;
 
static int *arr; 
static int head, tail, 
        n,             //  граница очереди
        nmax,       //  граница массива
    tmp;         //  число которое пихаем в массив, всегда возрасает для наглядности
 
static void view()
{
    system("CLS");
    if (n > 0)  
    {
        int pos = head;
        cout  << "\nqueue:";
        while (pos != tail)
        {
            cout << " " <<arr[pos];
            pos = (pos % nmax) + 1;
        }
        cout << " "<<arr[tail] <<endl;
        
        if (n == nmax)
            cout <<"Array забита\n";
    }
    else
        cout <<"Array пуста\n";
}
 
static void enqueue()
{
    system("CLS");
    if (n != nmax)
    {
        tmp++;
        tail = (tail % nmax) + 1; 
        arr[tail] = tmp;
        n++;
    }
}
 
static void dequeue()
{
    system("CLS");
    if (n != 0)
    {
        head = (head % nmax) + 1;
        n--;
    }
}
 
int main()
{
    setlocale(LC_ALL,"Rus");
    
    cout << "размер array: ";
        cin >> nmax;
 
    arr = new int[nmax];
    n = 0;
    head = 1;
    tail = n;
    int enter; 
    bool ok = true;
 
    view();
    
    while (ok)
    {
        cout << " \nзасунуть 1\n удалить 2\n    exit 3\n";
        cin >> enter;
        if (enter == 1)     enqueue();
        else if(enter == 2) dequeue();
        else if(enter == 3) ok = false;         
        
        view();
    }
    delete[] arr;
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.09.2010, 19:19     Очередь
Еще ссылки по теме:

Создать очередь. Добавить элемент в очередь. Удалить элемент из очереди C++
Очередь, теория. Очередь на шести стеках C++

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

Или воспользуйтесь поиском по форуму:
TheMachinist
 Аватар для TheMachinist
242 / 174 / 15
Регистрация: 14.06.2010
Сообщений: 422
06.09.2010, 19:19  [ТС]     Очередь #40
Новое задание все с той же очередью, я пару часов просидел над ним и никак не могу одну трудность
преодолеть.Помогите плиз:

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

Меня на этом форуме хорошие люди научили этому, только вот в той же Enqueue() производится
деление по модулю на размер массива/очереди - tail = (tail+1)%Size и у меня не получается этот Size
вписать в функцию.
Создаю очередь q1 вместимостью 10 , помещаю туда 20 элементов и извлекаю опять 20.
Вобщем переполнение и опустошение очереди не контролируется .

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
#include <iostream>
using namespace std;
 
class Queue
{
    int head; int tail; int count; 
    int* q;
 
public:
    int Size;
    Queue(int Size) : head(0), tail(0), count(0)
    {
        q = new int[Size];
    }
    int Enqueue(int var);
    int Dequeue();
};
 
int Queue::Dequeue()
{
    if(head == tail )
        return 0;
    int temp = q[head];
    head = (head+1)%Size;
    count--;
    return temp;
}
 
int Queue::Enqueue(int var)
{
    if(tail == 0 && count == Size)
return 0;
    q[tail] = var;
    tail = (tail+1)%Size;
    count++;
}
 
int main()
{
Queue q1(10);
Queue q2(5);
Queue q3(20);
 
for(int i = 0;i < 20;i++)
q1.Enqueue(1);
 
for(int i = 0;i < 20;i++)
cout << q1.Dequeue() << " ";
 
cout << endl;
 
    system("pause");
}
Yandex
Объявления
06.09.2010, 19:19     Очередь
Ответ Создать тему
Опции темы

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