Форум программистов, компьютерный форум 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;

Кто-нибудь????
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
04.09.2010, 16:42     Очередь #2
Вот кусок, вырвано из контекста но ты разберешся, я знаю .)
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
template <class T> 
bool Queue<T>::dequeue()
{    
    node* help;
 
    if ( head == NULL )       // пусто
        return false;   
    else if ( head == tail )  // только один узел
    { 
        delete head;
        head = NULL;
        tail = NULL;
        return true;
    } 
    else                      // больше чем один узел
    {  
        help = head;          
 
        // новый head-pointer:
        head = head->next;
 
        // старый head удаляем:
        delete help;
        return true;
    }
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
04.09.2010, 17:22     Очередь #3

Не по теме:

У ТС вроде очередь реализуется на основе массива. Я прав?



Добавлено через 10 минут
Цитата Сообщение от NikolaWhite Посмотреть сообщение
Я только понимаю что с помощью % можно сделать процесс постановки в очередь бесконечным
(ставя первый элемент выталкивать последний) :
Сделать-то можно, только это противоречит ожидаемому поведению очереди и может привести к непониманию и ошибкам гипотетического программиста, который будет использовать твой класс. При "проталкивании" (добавлению элемента в конец очереди) все остальные элементы очереди должны сохраняться, ведь никто не знает, когда может понадобиться тот элемент очереди, который ты хочешь "вытолкнуть" про проталкивании нового элемента. Иначе от твоей очереди будет мало толку.
Если ты хочешь сделать "бесконечную" очередь, я бы посоветовал посмотреть в сторону связных списков
bobromet
04.09.2010, 17:32
  #4

Не по теме:

Nameless One да, возможно.. дело даже не в этом - я это не увидел

проверку надо реализовать при помощи оператора %
а увидел только
как выйти из функции Decueue() если Очередь пуста???
и сразу ctrl+v
NikolaWhite , извини!

TheMachinist
 Аватар для TheMachinist
242 / 174 / 15
Регистрация: 14.06.2010
Сообщений: 422
04.09.2010, 18:45  [ТС]     Очередь #5
Я тут написал кое-что на основе вчерашнего, но хотелось бы попроще решение найти.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <conio.h>
#include "queue.h"
using namespace std;
 
 
 
int main()
{
    Queue <int> obj1;
 
int i = 1;
while(obj1.Enqueu(i))
i++;
 
while(obj1.Dequeue(i))
cout << i << " ";
 
 
    _getch();
}
// queue.h:

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
template <class T>
class Queue
{
    int head; int tail;
    T *q;
 
public:
    Queue();
    bool Enqueu(T);
    bool Dequeue(T& data);
};
 
template <class T>
Queue <T> ::Queue()   // Constructor.
{
    q = new T[5];
    head = NULL;
    tail = NULL;
}
 
template <class T>
bool Queue <T> ::Enqueu(T data)
{
    if(tail < 5)
    {
        q[tail] = data;
        tail++;
        return true;
    }
    else return false;
}
 
template<class T>
bool Queue <T> ::Dequeue(T &data)
{
    if(tail > 0)
    {
        tail--;
        data = q[tail];
        return true;
    }
    return false;
}
Добавлено через 9 минут
Nameless One я хочу сделать не бесконечную очередь, а выйти из функции Decueue() когда
tail == 0

А вопрос как реализовать проверку опустошения/переполнения очереди с помощью % я пожалуй
адресую автору упражнения.

Добавлено через 40 минут
И все таки как же выйти из функции когда tail == 0 ???

C++
1
2
3
4
5
6
7
int Decueue()
if(tail > 0)
{
tail++;
return q[tail];
}
else //  выйди из функции....
Подскажите пожалуйста
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
04.09.2010, 19:10     Очередь #6
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
#include <iostream>
#include <stdexcept>
 
template<class T>
class queue
{
    
public:
    
    queue(size_t reservedSize = DEFAULT_SZ);
    ~queue();
    void enqueue(const T& rhs);
    T dequeue();
    bool empty();
    size_t maxSize();
    size_t currSize();
    
private:
 
    const static size_t DEFAULT_SZ = 15;
    size_t tail;
    size_t size;
    T*  arr;
};
 
template<class T>
queue<T>::queue(size_t reservedSize)
    : tail(0), size(reservedSize)
{
    arr = new T[size]();
}
 
template<class T>
queue<T>::~queue()
{
    delete[] arr;
}
 
template<class T>
void queue<T>::enqueue(const T& rhs)
{
    if(tail == size)
        throw(std::runtime_error("The queue is full"));
    arr[tail++] = rhs;
}
 
template<class T>
T queue<T>::dequeue()
{
    if(!tail)
        throw(std::runtime_error("The queue is empty"));
    T retval = arr[0];
    for(size_t i = 0; i < tail; ++i)
        arr[i] = arr[i + 1];
    --tail; 
    return retval;
}
 
template<class T>
bool queue<T>::empty()
{
    return !tail;
}
 
template<class T>
size_t queue<T>::maxSize()
{
    return size;
}
 
template<class T>
size_t queue<T>::currSize()
{
    return tail;
}
 
int main(int argc, char* argv[])
{
    try
    {
        queue<int> iq;
        for(size_t i = 0; i < iq.maxSize(); ++i)
        {
            std::cout << "Pushing to queue: " << i << std::endl;
            iq.enqueue(i);
        }
        while(!iq.empty())
            std::cout << "Poping from queue: " << iq.dequeue() << std::endl;
    }
    catch(std::exception& e)
    {
        std::cerr << e.what() << std::endl;
        return 1;
    }
    return 0;
}
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
04.09.2010, 19:49     Очередь #7
Кажется я понял в чем фишка. Это видимо задание по алгоритмам - симуляция очереди. Дается массив фиксированной величины, например 5 потом он заполняется "клиентами". Клиентов можно убирать и засовывать. С помощью модуля определяется логическое положение счетчика. Я могу ошибатся . Вообщем вот прожка, там лутьше видно что я имею ввиду. Первый индекс выбрасывается, то есть массив начинается с [1]. Заранее извиняюсь за этот неорганизованный поток сознания.

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
#include <iostream>
#include <string>
using namespace std;
 
const int MAX = 5;
static int arr[MAX + 1]; // [0] индекс пропускаем
static int head, tail, n;
 
void view()
{
    cout << "\nArray  ";
    for (int i = 1; i <= MAX; i++)
        {
        cout << arr[i] << " ";
        }
 
    if (n > 0)   //состояние очереди
    {
        int pos = head;
        cout <<"\nQueue:";
        while (pos != tail)
        {
            cout << " " <<arr[pos];
            pos = (pos % MAX) + 1;
        }
        cout << " "<<arr[tail] <<endl;
    }
    else cout <<"\nwse ubiti :(";
 
}
 
static void enqueu()
{
    if (n == MAX)
    {
        cout <<"net mesta\n";
    }
    else
    {
        tail = (tail % MAX) + 1; //присваиваем счетчику следующее значение
        cin >> arr[tail];
        cout << "klient " << arr[tail]<< " prishol\n";
        n++;
    }
}
 
static void dequeue()
{
    if (n == 0)
        cout <<"net node\n";
    else
    {
        cout <<"klient " <<arr[head]<< "  ubit\n";
        head = (head % MAX) + 1;
        n--;
    }
}
 
int main()
{
    for(int i = 0; i < MAX ; i++)
        arr[i]=0;
 
    int k; // клиент
    cout << "Skolko klientov: "; cin >> n;
 
    for (int i = 1; i <= n; i++)
       cin >> arr[i];
   
    head = 1;
    tail = n;
 
    view();
 
    
    do
    {
        cout << " \ninsert[1] or delete[2]";
        cin >> k;
        cout << endl;
        if (k != 1 ) dequeue();//убиваем клиента
        else enqueu();
        view();
    }
    while (n != 0);
 
    //system("pause");
    return 0;
}
выводится содержание массива - физическое "состояние", ниже логическое, то есть сама очередь.
после ввода кол-ва клиентов нужно также вбить их номера.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
04.09.2010, 20:27     Очередь #8
Не по заданию, но для разнообразия
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
#include <iostream>
#include <stdexcept>
 
class Queue {
    struct Node {
        Node * next;
        int data;
        Node(int d) : next(NULL), data(d) {}
    };
    Node * first;
    Node * last;
    Queue(const Queue & q);
public:
    Queue() : first(NULL), last(NULL) {}
    ~Queue() {
        while ( first ){
            last = first->next;
            delete first;
            first = last;
        }
    }
    bool empty() const { return first == NULL; }
    void enqueue(int val){
        Node * n = new Node(val);
        if ( empty() ){
            first = n;
            last = first;
        }
        else {
            last->next = n;
            last = n;
        }
    }
    int dequeue(){
        Node * n;
        int d;
 
        if ( empty() )
            throw std::runtime_error("Empty queue!");
 
        n = first;
        d = n->data;
        first = first->next;
        delete n;
        return d;
    }
};
 
int main(){
    Queue q;
 
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
 
    while ( ! q.empty() )
        std::cout << q.dequeue() << std::endl;
 
    return 0;
}
TheMachinist
 Аватар для TheMachinist
242 / 174 / 15
Регистрация: 14.06.2010
Сообщений: 422
04.09.2010, 22:43  [ТС]     Очередь #9
Спасибо конечно, но это все не совсем то что нужно.Я вообще то 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
int q[5];
  //.......................
 //......................
int Queue::Dequeue()
{
   if(tail > 0)  // очередь не пуста
   {
      tail--;
       return q[tail]:
    }
   else // ????????? просто выйди из функции и ничего не делай
}
 
void Queue::Enqueue(int var)
{
if(tail < 5)
{
q[tail] = var;
tail++;
}
else // ????? выйди из функции.
}
 
int main()
{
Queue q1;
for(int i = 0;i < 100;i++)
q1.Enqueue(i);
 
for(int i = 0;i < 100;i++)
cout << q1.Dequeue() << " ";
 
}
Я просто хочу чтоб в очередь вводилось и выводилось только 5 элементов каким бы ни был цикл.
Это вопрос начинающего
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
04.09.2010, 23:01     Очередь #10
Цитата Сообщение от NikolaWhite Посмотреть сообщение
Я просто хочу чтоб в очередь вводилось и выводилось только 5 элементов каким бы ни был цикл.
Дело в том, что если для стека массив ещё можно использовать, то для очереди массив - самое неудачное решение. При извлечении первого элемента все остальные прийдётся на шаг влево смещать, а это очень накладно, каким бы образом ни было реализовано. Вот немного совсем класс переделал - теперь размер очереди ограничивается. Можно (и, наверное, правильнее) делать шаблонный класс, но суть от этого не изменится, а писанины немного больше...
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
#include <iostream>
#include <stdexcept>
 
class Queue {
    struct Node {
        Node * next;
        int data;
        Node(int d) : next(NULL), data(d) {}
    };
    Node * first;
    Node * last;
    int max_elements;
    int count;
    Queue(const Queue & q);
public:
    Queue(int m) : first(NULL), last(NULL), max_elements(m), count(0) {}
    ~Queue() {
        while ( first ){
            last = first->next;
            delete first;
            first = last;
        }
    }
    bool empty() const { return count == 0; }
    bool full() const { return count >= max_elements; }
    void enqueue(int val){
        if ( full() )
            throw std::runtime_error("Full queue!");
 
        Node * n = new Node(val);
        if ( empty() ){
            first = n;
            last = first;
        }
        else {
            last->next = n;
            last = n;
        }
        ++count;
    }
    int dequeue(){
        Node * n;
        int d;
 
        if ( empty() )
            throw std::runtime_error("Empty queue!");
 
        n = first;
        d = n->data;
        first = first->next;
        delete n;
        --count;
        return d;
    }
};
 
int main(){
    Queue q(5);
 
    int i = 0;
    while ( ! q.full() )
        q.enqueue(++i);
 
    while ( ! q.empty() )
        std::cout << q.dequeue() << std::endl;
 
    return 0;
}
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
04.09.2010, 23:05     Очередь #11
Наверно я туплю но я не понимаю что значит выйти.
int Dequeue() по любому int после else должна вернуть потому что она int,
void Enqueue(int ) может просто свои дела сделать и все, можно дальше.)
Чем они держат то?

ps. и модуль там не спроста, я все больше уверен что дело в алгоритме. У нас была такая задачка, тоже массив, тоже модуль, одного в конец засовываешь - первый вылетает. Дело даже не программировании

Не по теме:

pss. или все таки туплю.)

easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
04.09.2010, 23:37     Очередь #12
bobromet, ничего не делать в случае ошибки - это, конечно, совсем неправильное решение. Верный путь к зацикливанию. У меня в случае попытки запихнуть элемент в заполненную очередь сработает
C++
1
throw std::runtime_error("Full queue!");
а при попытке извлечь элемент из пустой очереди
C++
1
throw std::runtime_error("Empty queue!");
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
04.09.2010, 23:47     Очередь #13
easybudda, я не совсем это имел ввиду, хотел сказать что раз void то функция сделает "свои дела": выбросит exception или выйдет из программы, или все сотрет - не важно, просто непонятно
что значит "как выйти из функции". Если имеется ввиду "как правильно выходить из очереди в такой ситуации" , тогда да.
TheMachinist
 Аватар для TheMachinist
242 / 174 / 15
Регистрация: 14.06.2010
Сообщений: 422
05.09.2010, 00:14  [ТС]     Очередь #14
bobromet, ничего не делать в случае ошибки - это, конечно, совсем неправильное решение. Верный путь к зацикливанию. У меня в случае попытки запихнуть элемент в заполненную очередь сработаетКод C++
1
C++
1
throw std::runtime_error("Full queue!");
а при попытке извлечь элемент из пустой очередиКод C++
1
C++
1
throw std::runtime_error("Empty queue!");
А у меня это не работает почему то, так же как и exit(1)

Enqueue() работает нормально , а Dequeue() выдает кучу лишних цифр вместо 0 1 2 3 4

Добавлено через 1 минуту
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
#include <iostream>
#include <conio.h>
//using namespace std;
 
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()
{
    if(tail > 0)
    {
        tail--;
        return q[tail];
    }
    //else throw std::runtime_error("empty queue");
}
 
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();
 
    _getch();
}
Добавлено через 8 минут

Я то нуб, но думал для вас этот вопрос пустяк.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
05.09.2010, 00:35     Очередь #15
Цитата Сообщение от NikolaWhite Посмотреть сообщение
А у меня это не работает почему то, так же как и exit(1)
Видимо, потому, что runtime_roor объявлен в stdexcept, а exit() в stdlib.h (в варианте С++ - cstdlib), а у Вас ни того, ни другого не включено. Кстати, exit() в С++ программе вообще лучше не использовать. Почему - поищите на форуме, не так давно обсуждалось. Да и вообще в программе на С++ функции С без крайней надобности лучше не использовать.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
05.09.2010, 00:35     Очередь #16
А вот так уже лучше.

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
#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()
{
        if(tail > 0)
        {
                tail--;
                return q[tail];
        }
        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();
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
05.09.2010, 00:38     Очередь #17
Цитата Сообщение от NikolaWhite Посмотреть сообщение
думал для вас этот вопрос пустяк.
Так Вам же целых три примера привели... Ну не будет оно так, как у Вас написано, нормально работать. Лучше разберитесь с тем, что мы Вам тут насоветовали...
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
05.09.2010, 01:07     Очередь #18
NikolaWhite, скопировал твой последний код, вставил exit(1) в Dequeue() - все работает.
цифры 4 3 2 1 0 - выводит, просто потом чепухой забивается, ничего удивительного. Исключение тоже выбрасывает. Попробуй утром еще раз. А я тут алгоритмы.)
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
05.09.2010, 01:19     Очередь #19
Цитата Сообщение от Lavroff Посмотреть сообщение
return q[tail];
Минуточку! Это ж стек получится, а нужно очередь...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2010, 01:21     Очередь
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
05.09.2010, 01:21     Очередь #20
easybudda, Дык я как бэ ничего не менял.
Yandex
Объявления
05.09.2010, 01:21     Очередь
Ответ Создать тему
Опции темы

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