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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.87
TheMachinist
243 / 175 / 15
Регистрация: 14.06.2010
Сообщений: 422
#1

Очередь - C++

04.09.2010, 16:19. Просмотров 4378. Ответов 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.) - C++
Помогите пожалуйста написать очередь. Есть Температура double и ее тип int ну и нужно сделать очередь, чтобы добавляло, удаляло, читало....

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

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

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

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

Очередь - C++
Описать структуру с именем TRAIN, содержащую следующие поля: - название пункта назначения - номер поезда - время отправления ...

40
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;
    }
}
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
04.09.2010, 17:22 #3

Не по теме:

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



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

Не по теме:

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

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

0
TheMachinist
243 / 175 / 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 //  выйди из функции....
Подскажите пожалуйста
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
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;
}
1
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;
}
выводится содержание массива - физическое "состояние", ниже логическое, то есть сама очередь.
после ввода кол-ва клиентов нужно также вбить их номера.
1
easybudda
Модератор
Эксперт CЭксперт С++
9664 / 5614 / 952
Регистрация: 25.07.2009
Сообщений: 10,778
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;
}
1
TheMachinist
243 / 175 / 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 элементов каким бы ни был цикл.
Это вопрос начинающего
0
easybudda
Модератор
Эксперт CЭксперт С++
9664 / 5614 / 952
Регистрация: 25.07.2009
Сообщений: 10,778
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;
}
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. или все таки туплю.)

0
easybudda
Модератор
Эксперт CЭксперт С++
9664 / 5614 / 952
Регистрация: 25.07.2009
Сообщений: 10,778
04.09.2010, 23:37 #12
bobromet, ничего не делать в случае ошибки - это, конечно, совсем неправильное решение. Верный путь к зацикливанию. У меня в случае попытки запихнуть элемент в заполненную очередь сработает
C++
1
throw std::runtime_error("Full queue!");
а при попытке извлечь элемент из пустой очереди
C++
1
throw std::runtime_error("Empty queue!");
0
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
04.09.2010, 23:47 #13
easybudda, я не совсем это имел ввиду, хотел сказать что раз void то функция сделает "свои дела": выбросит exception или выйдет из программы, или все сотрет - не важно, просто непонятно
что значит "как выйти из функции". Если имеется ввиду "как правильно выходить из очереди в такой ситуации" , тогда да.
0
TheMachinist
243 / 175 / 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 минут

Я то нуб, но думал для вас этот вопрос пустяк.
0
easybudda
Модератор
Эксперт CЭксперт С++
9664 / 5614 / 952
Регистрация: 25.07.2009
Сообщений: 10,778
05.09.2010, 00:35 #15
Цитата Сообщение от NikolaWhite Посмотреть сообщение
А у меня это не работает почему то, так же как и exit(1)
Видимо, потому, что runtime_roor объявлен в stdexcept, а exit() в stdlib.h (в варианте С++ - cstdlib), а у Вас ни того, ни другого не включено. Кстати, exit() в С++ программе вообще лучше не использовать. Почему - поищите на форуме, не так давно обсуждалось. Да и вообще в программе на С++ функции С без крайней надобности лучше не использовать.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2010, 00:35
Привет! Вот еще темы с ответами:

Очередь - C++
Всем приветики! Если кто нибудь знает помогите пожалуйста вот с такой задачкой. Есть какая-то очередь с элементами, нужно найти все...

с++ очередь - C++
Ребят создал очередь. Ввод и удаление. есть проблемы с выводом. скину шапку и код на удаление using namespace std; const int N=6; ...

Очередь - C++
Реализуйте структуру данных &quot;очередь&quot; на основе циклического массива или другим способом. Входные данные В каждой строке входных...

Очередь С++ - C++
Дан текстовый файл Вводятся с клавы числа А и В Надо вывести НА ЭКРАН СНАЧАЛА ВСЕ ЧИСЛА меньше А затем между А и В а затем больш В ...


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
05.09.2010, 00:35
Ответ Создать тему
Опции темы

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