Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.87
TheMachinist
244 / 176 / 47
Регистрация: 14.06.2010
Сообщений: 422
#1

Очередь - C++

04.09.2010, 16:19. Просмотров 4530. Ответов 40
Метки нет (Все метки)

Привет всем.
Я тут решаю в общем то простое упражнение - нужно проверить переполнение и опустошение очереди.
Есть у меня небольшая трудность:
как выйти из функции Decueue() (англ.вывести из очереди ) если Очередь пуста(tail == 0)???
Я пробовал exit(1) и return(0), но это все не то.

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


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

tail = (tail+1)%5;

Кто-нибудь????
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.09.2010, 16:19
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Очередь (C++):

Сформировать очередь по файлу целых чисел. Промоделировать очередь в супермаркете
Сформировать очередь по файлу целых чисел. Промоделировать очередь в...

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

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

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

Создать очередь. Добавить элемент в очередь. Удалить элемент из очереди
Нужно создать очередь. Добавить элемент в очередь. Удалить элемент из очереди. ...

Очередь
Задача проги сделать очередь, по сути прога написана по лекции, но выдает...

40
easybudda
Модератор
Эксперт CЭксперт С++
10021 / 5944 / 1483
Регистрация: 25.07.2009
Сообщений: 11,230
05.09.2010, 01:53 #21
Цитата Сообщение от Lavroff Посмотреть сообщение
Дык я как бэ ничего не менял.
Ну у Вас просто код понятнее написан.

NikolaWhite, Вы уж определитесь - Вам стек, очередь, или объяснить, чем они отличаются?
Стек работает по принципу "последним вошёл - первым вышел". Очередь - "Первым вошёл - первым вышел". У Вас Dequeue() возвращает последний помещённый элемент, а должна бы первый...
0
ForEveR
В астрале
Эксперт С++
7994 / 4753 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 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++];
}
0
easybudda
Модератор
Эксперт CЭксперт С++
10021 / 5944 / 1483
Регистрация: 25.07.2009
Сообщений: 11,230
05.09.2010, 02:17 #23
Lavroff, и всё бы ничего, но при таком подходе очередь только один раз заполнится и очистится, повторно объект такого класса использовать не получится. Мало того, элементы должны добавляться и удаляться из очереди в произвольной последовательности (с учётом ограничения размера очереди). Попробуйте не пытаться туда сразу 10 объектов запихнуть, а 5, потом их из очереди извлечь и 5 других записать...
0
ForEveR
В астрале
Эксперт С++
7994 / 4753 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
05.09.2010, 02:22 #24
easybudda, Добавляться да, в произвольной. А удаляться насколько я понимаю в зависимости от того как заполнились, ибо FIFO по идее.
0
easybudda
Модератор
Эксперт CЭксперт С++
10021 / 5944 / 1483
Регистрация: 25.07.2009
Сообщений: 11,230
05.09.2010, 02:33 #25
Lavroff, не, я не про это... Вот в моём примере можно записать 3 элемента, потом прочитать 2, записать 4, прочитать все 5, потом записать ещё пару и прочитать их, а вот с Вашим кодом так не получится...
0
ForEveR
05.09.2010, 02:36
  #26

Не по теме:

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

0
fasked
Эксперт С++
4976 / 2556 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 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");
}
0
Nameless One
Эксперт С++
5785 / 3434 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
05.09.2010, 11:29 #28
Цитата Сообщение от NikolaWhite Посмотреть сообщение
А у меня это не работает почему то, так же как и exit(1)
Это помому, что:
  1. код, который может возбуждать исключения, нужно помещать внутри блока try;
  2. выброшенное исключение нужно обработать внутри соответсвующего блока catch.
0
easybudda
Модератор
Эксперт CЭксперт С++
10021 / 5944 / 1483
Регистрация: 25.07.2009
Сообщений: 11,230
05.09.2010, 12:13 #29
Nameless One, если выполнение дойдёт до строки
C++
1
throw std::runtime_error("bla bla bla");
то программа и без всяких try/catch грохнется...
1
Nameless One
Эксперт С++
5785 / 3434 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
05.09.2010, 12:20 #30
Спасибо. Жаль, что в книжке, которую я читал, про это не было написано.
0
TheMachinist
244 / 176 / 47
Регистрация: 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();
}
0
ForEveR
В астрале
Эксперт С++
7994 / 4753 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 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;
}
1
TheMachinist
244 / 176 / 47
Регистрация: 14.06.2010
Сообщений: 422
05.09.2010, 17:48  [ТС] #33
Извиняюсь пропустил
C++
1
throw
, но все равно ошибка. Попробуй(те) запустить в VS.
0
easybudda
Модератор
Эксперт CЭксперт С++
10021 / 5944 / 1483
Регистрация: 25.07.2009
Сообщений: 11,230
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();
}
и должно бы работать. Да, выдаёт параноидальное предупреждение во время компиляции, но на него можно забить...
Очередь
1
TheMachinist
244 / 176 / 47
Регистрация: 14.06.2010
Сообщений: 422
05.09.2010, 18:53  [ТС] #35
Чего я добиваюсь это чтоб при попытке ввести в очередь ,скажем 10 элементов, вводилось только
5(размер массива).
А при попытке извлечь оттуда больше элементов чем вместимость(больше пяти) извлекалось только то
что там в очереди содержится. То есть контролировать чтобы tail никогда не был больше 5, а head не была
меньше 0.
0
easybudda
Модератор
Эксперт CЭксперт С++
10021 / 5944 / 1483
Регистрация: 25.07.2009
Сообщений: 11,230
05.09.2010, 19:41 #36
Цитата Сообщение от NikolaWhite Посмотреть сообщение
Чего я добиваюсь это чтоб при попытке ввести в очередь ,скажем 10 элементов, вводилось только
5(размер массива).
А при попытке извлечь оттуда больше элементов чем вместимость(больше пяти) извлекалось только то
что там в очереди содержится. То есть контролировать чтобы tail никогда не был больше 5, а head не была
меньше 0.
Проблема в том, что если программа передаёт функции какое-то значение, а функция его игнорирует потому, что очередь уже заполнена - это очень неправильно, но на работе программы не отразится. А вот если программа ждёт от функции какое-то значение, а функция его не может вернуть - что при этом должно происходить?
0
TheMachinist
244 / 176 / 47
Регистрация: 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();
}
0
easybudda
Модератор
Эксперт CЭксперт С++
10021 / 5944 / 1483
Регистрация: 25.07.2009
Сообщений: 11,230
05.09.2010, 21:28 #38
Цитата Сообщение от NikolaWhite Посмотреть сообщение
if(head == tail & count == 0)
правильнее
C++
1
if(head == tail && count == 0)
но и так должно отработать, а вот
Цитата Сообщение от NikolaWhite Посмотреть сообщение
return(0);
занчит - значения 0 в очереди быть не может?
0
bobromet
24 / 24 / 3
Регистрация: 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;
}
1
TheMachinist
244 / 176 / 47
Регистрация: 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");
}
0
06.09.2010, 19:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.09.2010, 19:19
Привет! Вот еще темы с решениями:

Очередь
Здравствуйте, Уважаемые форумчане :) Вот есть такая задача: Используя...

Очередь
Всем привет! Вопрос: целесообразно ли перегружать для очереди операторы...

Очередь C++
всем доброе утро) вот такое задание:все отрицательные элементы сдвинуть в...

Очередь
В чем проблема? не хочет запускаться код? Ошибки следующие: #include...


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

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

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