Очередь

@TheMachinist · Регистрация: 14.06.2010

Author24 — интернет-сервис помощи студентам

Привет всем.
Я тут решаю в общем то простое упражнение - нужно проверить переполнение и опустошение очереди.
Есть у меня небольшая трудность:
как выйти из функции Decueue() (англ.вывести из очереди

) если Очередь пуста(tail == 0)???
Я пробовал exit(1) и return(0), но это все не то.

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

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

tail = (tail+1)%5;

Кто-нибудь????

@bobromet · 04.09.2010, 16:42

Вот кусок, вырвано из контекста но ты разберешся, я знаю .)

C++

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 · 04.09.2010, 17:22

Не по теме:

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

Добавлено через 10 минут

Сообщение от NikolaWhite

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

Сделать-то можно, только это противоречит ожидаемому поведению очереди и может привести к непониманию и ошибкам гипотетического программиста, который будет использовать твой класс. При "проталкивании" (добавлению элемента в конец очереди) все остальные элементы очереди должны сохраняться, ведь никто не знает, когда может понадобиться тот элемент очереди, который ты хочешь "вытолкнуть" про проталкивании нового элемента. Иначе от твоей очереди будет мало толку.
Если ты хочешь сделать "бесконечную" очередь, я бы посоветовал посмотреть в сторону связных списков

@bobromet · 04.09.2010, 17:32

Не по теме:

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

проверку надо реализовать при помощи оператора %

а увидел только

как выйти из функции Decueue() если Очередь пуста???

и сразу ctrl+v
NikolaWhite , извини!

@TheMachinist · 04.09.2010, 18:45 **[ТС]**

Я тут написал кое-что на основе вчерашнего, но хотелось бы попроще решение найти.

C++

#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++

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++

int Decueue()
if(tail > 0)
{
tail++;
return q[tail];
}
else //  выйди из функции....

Подскажите пожалуйста

@Nameless One · 04.09.2010, 19:10

C++

#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 · 04.09.2010, 19:49

Кажется я понял в чем фишка. Это видимо задание по алгоритмам - симуляция очереди. Дается массив фиксированной величины, например 5 потом он заполняется "клиентами". Клиентов можно убирать и засовывать. С помощью модуля определяется логическое положение счетчика. Я могу ошибатся

. Вообщем вот прожка, там лутьше видно что я имею ввиду. Первый индекс выбрасывается, то есть массив начинается с [1]. Заранее извиняюсь за этот неорганизованный поток сознания.

C++

#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 · 04.09.2010, 20:27

Не по заданию, но для разнообразия

C++

#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 · 04.09.2010, 22:43 **[ТС]**

Спасибо конечно, но это все не совсем то что нужно.Я вообще то 3 недели назад начал С++ изучать.

Повторюсь:

C++

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 · 04.09.2010, 23:01

Сообщение от NikolaWhite

Я просто хочу чтоб в очередь вводилось и выводилось только 5 элементов каким бы ни был цикл.

Дело в том, что если для стека массив ещё можно использовать, то для очереди массив - самое неудачное решение. При извлечении первого элемента все остальные прийдётся на шаг влево смещать, а это очень накладно, каким бы образом ни было реализовано. Вот немного совсем класс переделал - теперь размер очереди ограничивается. Можно (и, наверное, правильнее) делать шаблонный класс, но суть от этого не изменится, а писанины немного больше...

C++

#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 · 04.09.2010, 23:05

Наверно я туплю но я не понимаю что значит выйти.
int Dequeue() по любому int после else должна вернуть потому что она int,
void Enqueue(int ) может просто свои дела сделать и все, можно дальше.)
Чем они держат то?

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

Не по теме:

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

@easybudda · 04.09.2010, 23:37

bobromet, ничего не делать в случае ошибки - это, конечно, совсем неправильное решение. Верный путь к зацикливанию. У меня в случае попытки запихнуть элемент в заполненную очередь сработает

C++

1	throw std::runtime_error("Full queue!");

а при попытке извлечь элемент из пустой очереди

C++

1	throw std::runtime_error("Empty queue!");

@bobromet · 04.09.2010, 23:47

easybudda, я не совсем это имел ввиду, хотел сказать что раз void то функция сделает "свои дела": выбросит exception или выйдет из программы, или все сотрет - не важно, просто непонятно
что значит "как выйти из функции". Если имеется ввиду "как правильно выходить из очереди в такой ситуации" , тогда да.

@TheMachinist · 05.09.2010, 00: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++

#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 · 05.09.2010, 00:35

Сообщение от NikolaWhite

А у меня это не работает почему то, так же как и exit(1)

Видимо, потому, что runtime_roor объявлен в stdexcept, а exit() в stdlib.h (в варианте С++ - cstdlib), а у Вас ни того, ни другого не включено. Кстати, exit() в С++ программе вообще лучше не использовать. Почему - поищите на форуме, не так давно обсуждалось. Да и вообще в программе на С++ функции С без крайней надобности лучше не использовать.

@ForEveR · 05.09.2010, 00:35

А вот так уже лучше.

C++

#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 · 05.09.2010, 00:38

Сообщение от NikolaWhite

думал для вас этот вопрос пустяк.

Так Вам же целых три примера привели... Ну не будет оно так, как у Вас написано, нормально работать. Лучше разберитесь с тем, что мы Вам тут насоветовали...

@bobromet · 05.09.2010, 01:07

NikolaWhite, скопировал твой последний код, вставил exit(1) в Dequeue() - все работает.
цифры 4 3 2 1 0 - выводит, просто потом чепухой забивается, ничего удивительного. Исключение тоже выбрасывает. Попробуй утром еще раз. А я тут алгоритмы.)

@easybudda · 05.09.2010, 01:19

Сообщение от Lavroff

return q[tail];

Минуточку! Это ж стек получится, а нужно очередь...

@ForEveR · 05.09.2010, 01:21

easybudda, Дык я как бэ ничего не менял.

@bobromet 25 / 25 / 3 Регистрация: 06.03.2010 Сообщений: 59
	04.09.2010, 23:05	11
	Наверно я туплю но я не понимаю что значит выйти. int Dequeue() по любому int после else должна вернуть потому что она int, void Enqueue(int ) может просто свои дела сделать и все, можно дальше.) Чем они держат то? ps. и модуль там не спроста, я все больше уверен что дело в алгоритме. У нас была такая задачка, тоже массив, тоже модуль, одного в конец засовываешь - первый вылетает. Дело даже не программировании Не по теме: pss. или все таки туплю.) 0

@bobromet 25 / 25 / 3 Регистрация: 06.03.2010 Сообщений: 59
	04.09.2010, 23:47	13
	easybudda, я не совсем это имел ввиду, хотел сказать что раз void то функция сделает "свои дела": выбросит exception или выйдет из программы, или все сотрет - не важно, просто непонятно что значит "как выйти из функции". Если имеется ввиду "как правильно выходить из очереди в такой ситуации" , тогда да. 0

@TheMachinist 246 / 178 / 47 Регистрация: 14.06.2010 Сообщений: 422
		1
	Очередь 04.09.2010, 16:19. Показов 7432. Ответов 40 Метки нет (Все метки) Привет всем. Я тут решаю в общем то простое упражнение - нужно проверить переполнение и опустошение очереди. Есть у меня небольшая трудность: как выйти из функции Decueue() (англ.вывести из очереди ) если Очередь пуста(tail == 0)??? Я пробовал exit(1) и return(0), но это все не то. А главная трудность - по заданию упражнения проверку надо реализовать при помощи оператора % Я только понимаю что с помощью % можно сделать процесс постановки в очередь бесконечным (ставя первый элемент выталкивать последний) : tail = (tail+1)%5; Кто-нибудь???? 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	04.09.2010, 17:22	3
	Не по теме: У ТС вроде очередь реализуется на основе массива. Я прав? Добавлено через 10 минут Сообщение от NikolaWhite Я только понимаю что с помощью % можно сделать процесс постановки в очередь бесконечным (ставя первый элемент выталкивать последний) : Сделать-то можно, только это противоречит ожидаемому поведению очереди и может привести к непониманию и ошибкам гипотетического программиста, который будет использовать твой класс. При "проталкивании" (добавлению элемента в конец очереди) все остальные элементы очереди должны сохраняться, ведь никто не знает, когда может понадобиться тот элемент очереди, который ты хочешь "вытолкнуть" про проталкивании нового элемента. Иначе от твоей очереди будет мало толку. Если ты хочешь сделать "бесконечную" очередь, я бы посоветовал посмотреть в сторону связных списков 0

@bobromet
	04.09.2010, 17:32 #4
	Не по теме: Nameless One да, возможно.. дело даже не в этом - я это не увидел :wall: проверку надо реализовать при помощи оператора % а увидел только как выйти из функции Decueue() если Очередь пуста??? и сразу ctrl+v NikolaWhite , извини! 0

@easybudda Модератор 12454 / 7479 / 1752 Регистрация: 25.07.2009 Сообщений: 13,748
	05.09.2010, 00:35	15
	Сообщение от NikolaWhite А у меня это не работает почему то, так же как и exit(1) Видимо, потому, что runtime_roor объявлен в stdexcept, а exit() в stdlib.h (в варианте С++ - cstdlib), а у Вас ни того, ни другого не включено. Кстати, exit() в С++ программе вообще лучше не использовать. Почему - поищите на форуме, не так давно обсуждалось. Да и вообще в программе на С++ функции С без крайней надобности лучше не использовать. 0

@easybudda Модератор 12454 / 7479 / 1752 Регистрация: 25.07.2009 Сообщений: 13,748
	05.09.2010, 00:38	17
	Сообщение от NikolaWhite думал для вас этот вопрос пустяк. Так Вам же целых три примера привели... Ну не будет оно так, как у Вас написано, нормально работать. Лучше разберитесь с тем, что мы Вам тут насоветовали... 0

@bobromet 25 / 25 / 3 Регистрация: 06.03.2010 Сообщений: 59
	05.09.2010, 01:07	18
	NikolaWhite, скопировал твой последний код, вставил exit(1) в Dequeue() - все работает. цифры 4 3 2 1 0 - выводит, просто потом чепухой забивается, ничего удивительного. Исключение тоже выбрасывает. Попробуй утром еще раз. А я тут алгоритмы.) 0

@easybudda Модератор 12454 / 7479 / 1752 Регистрация: 25.07.2009 Сообщений: 13,748
	05.09.2010, 01:19	19
	Сообщение от Lavroff return q[tail]; Минуточку! Это ж стек получится, а нужно очередь... 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	05.09.2010, 01:21	20
	easybudda, Дык я как бэ ничего не менял. 0