Check if queue is sorted in ascending order hanging

Question

I can't seem to figure out why the program below is not running as intended. After entering a negative integer value and breaking the first while loop in main, program control does not proceed. I tried flushing the output stream at various key points but the issue persists.

#include <iostream>
#include <queue>

bool checkValidity(const std::queue<int>& q) {

    for(auto i = q.front(); i != q.back(); ++i){
        if (q.empty() || q.size() <= 1){
            std::cout << "invalid entry, insufficient elements" << '\n';
            return false;
            break;
        }
        if (i > ++i) {
            std::cout << "invalid entry, not properly sorted" << '\n';
            return false;
            break;
        }                 
    }   
    std::cout << "valid entry, properly sorted" << '\n';
    return true;
}

const char* bool_cast(const bool b) {
    return b ? "true" : "false";
}        

int main () {
    std::queue<int> numbers;
    int temp;

    std::cout << "Pushing..." << '\n';
    while(temp >= 0){
        std::cout << "Enter numbers: ";
        std::cin >> temp;
        if(temp >= 0){
            numbers.push(temp);
        }
    }

    bool ck = checkValidity(numbers);
    std::cout << bool_cast(ck) << '\n';

    std::cout << "{ ";
    while(numbers.size() > 0){
        std::cout << numbers.front();
        numbers.pop();
        std::cout << " ";
    }
    std::cout << "}" << '\n';

    return 0;
}

This loop while(temp >= 0){ has undefined behavior because the variable temp was not initialized. — Vlad from Moscow, Apr 03 '20 at 16:16
You might want to learn about [the standard I/O manipulators](https://en.cppreference.com/w/cpp/io/manip), especially [`std::boolalpha`](https://en.cppreference.com/w/cpp/io/manip/boolalpha). — Some programmer dude, Apr 03 '20 at 16:17
@Darnoc Eloc This loop for(auto i = q.front(); i != q.back(); ++i){ does not make a sense — Vlad from Moscow, Apr 03 '20 at 16:20
This `if (i > ++i)` is certainly also undefined? You probably meant `if (*(i) > *(++i))`, but then the order of comparing something to itself `++` isn't guaranteed to evaluate in the order we want does it? but then you also have another problem where you're potentially incrementing your iterator twice in the same loop iteration which could cause you to iterate past `end()`, at which point you could iterate OVER `end()`. EDIT I didn't even realize it was `front` and `back` I thought it was `start` and `end`. — JohnFilleau, Apr 03 '20 at 16:20
`std::queue` doesn't allow you to iterate its elements, you want `begin` and `end` rather than `front` and `back`. If you want to access other elements you need to use a different container like `std::vector` or `std::deque` — Alan Birtles, Apr 03 '20 at 16:26

backdoor · Answer 1 · 2020-04-03T18:20:35.150

You cannot iterate through the queue, therefore to iterate you need to copy the queue to another queue and then traverse by poping the elements from the queue. and comparing the elements.

Inline comments added for better understanding of the code.

bool checkValidity(const std::queue<int>& q) {

    if (q.empty() || q.size() <= 1){ // This can be outside the loop and checked only onces
            std::cout << "invalid entry, insufficient elements" << '\n';
            return false;
    }
    std::queue<int> numbers=q; // a new queue to copy the queue
    int first=numbers.front(); // to compare we need to variable first and second
    numbers.pop();// pop the first value,as it is stored in first variable
    int second;
    while(!numbers.empty()){
        second=numbers.front();
        numbers.pop();
        if (first> second) { // compare the first and second variable
            std::cout << "invalid entry, not properly sorted" << '\n';
            return false;
            break;
        }
        first=second; // assign second to first and traverse the reamining queue
    }
    std::cout << "valid entry, properly sorted" << '\n';
    return true;
}

Hope this help.

score 0 · Accepted Answer · answered Apr 03 '20 at 18:30

Inherited from std::queue and use its protected member Container c; to access begin() and end() of the underlying container as previously done here std::queue iteration.

#include <iostream>
#include <queue>
#include <deque>
#include <iterator>

template<typename T, typename Container=std::deque<T> >
class iterable_queue : public std::queue<T,Container>
{
public:
    typedef typename Container::iterator iterator;
    typedef typename Container::const_iterator const_iterator;

    iterator begin() { return this->c.begin(); }
    iterator end() { return this->c.end(); }
    const_iterator begin() const { return this->c.begin(); }
    const_iterator end() const { return this->c.end(); }
};


bool checkValidity(iterable_queue<int>& q) {
    if (q.empty() || q.size() <= 1){
        std::cout << "invalid entry, insufficient elements" << '\n';
        return false;
    }
    while(q.size()){
        auto i = q.begin();
        auto j = ++q.begin();
        for(; i < q.end() && j < ++q.end();){
            std::cout << *i << " " << *j << '\n';
            if (*(i) > *(j)) {
                std::cout << "invalid entry, not properly sorted" << '\n';
                return false;
            }
            i++, j++;
        }   
        std::cout << "valid entry, properly sorted" << '\n';
        return true;
    }
    std::cout << "invalid entry, insufficient elements" << '\n';
    return false;
}

const char* bool_cast(const bool b) {
    return b ? "true" : "false";
}        

int main () {
    iterable_queue<int> numbers;
    int temp;

    std::cout << "Pushing..." << '\n';
    while(temp >= 0){
        std::cout << "Enter numbers: ";
        std::cin >> temp;
        if(temp >= 0){
            numbers.push(temp);
        }
    }

    bool ck = checkValidity(numbers);
    std::cout << bool_cast(ck) << '\n';

    std::cout << "{ ";
    while(numbers.size() > 0){
        std::cout << numbers.front();
        numbers.pop();
        std::cout << " ";
    }
    std::cout << "}" << '\n';

    return 0;
}

Check if queue is sorted in ascending order hanging

2 Answers2