how to check if queue is sorted using stl

Question

i would like your help with this question I have, I need to write a C++ function that inputs a queue as parameter and checks whether the contents in the queue are in sorted order (such that the front element is smallest). A BOOLEAN value should be returned accordingly. Assuming that there is no duplicated element in the queue.
I am trying to get my head around the concept of sorting, so any help would be appreciated, here is what I have tried so far:

#include "stdafx.h"
#include <iostream>
#include <queue>
using namespace std; 

bool is_Sorted(queue<int> q) {
    int my_front = q.front();
    int my_back = q.back();
    if (my_front==my_back) {
        return true;
    }
    if (my_front+1>my_front) {
        return true;
    }
}

int main()
{
    queue <int> q;
    q.push(3);
    q.push(4);
    q.push(5);
    q.push(6);
    q.push(7);
    is_Sorted(q);
    return 0;
}

What error do you get? Also, why are you only checking the front and back? You need to make sure every element is in order. — NathanOliver, Jun 26 '18 at 15:53
i tried the code again to check the error so i can write it , it didn't give me any errors , if i wanted to to make a loop so i can go through every element should it be something like this? for(int i=0;i — pi.ras, Jun 26 '18 at 15:59
You need to check all the elements of the list. Also in the current version, your functions never return `false`. You can go through the list and compare each element with the next one. — ZiGaelle, Jun 26 '18 at 16:00
to compare each element with the next one , i should do something like this?: for(int i=0;imy_front){return true;} else{return false;} } ?? — pi.ras, Jun 26 '18 at 16:06
Why are you using a queue and not a list ? If you want to iterate on a queue, you can do it as shown here: https://stackoverflow.com/questions/1259099/stdqueue-iteration (the second or third (simpler) answer) — ZiGaelle, Jun 26 '18 at 16:55
If you want to get your head around sorting, [start with this](https://en.wikipedia.org/wiki/Sorting_algorithm). And no, that for loop in your prior comment is incorrect. It just repeatedly checks the value at front, plus one, against itself without the addition, which will *always* be true. You need to check each element against its successive neighbor in the queue. Learn all the things you can do with a [queue](https://en.cppreference.com/w/cpp/container/queue), assuming you're pinned to that data structure for whatever reason. — WhozCraig, Jun 26 '18 at 16:58

Jonathan Mee · Answer 1 · 2018-06-27T12:17:32.807

2

Because a queue doesn't provide iterators you can't use: is_sorted

Thus comparison would require copying the queue or sequentially pop'ing and comparing elements of the queue, then push'ing them back onto the queue. I've chosen to simply copy the queue for this example:

template <typename T>
bool is_sorted(queue<T> q) {
    if(!empty(q)) {
        for(T i = q.front(); size(q) > 1U; i = q.front()) {
            q.pop();

            if(i > q.front()) {
                return false;
            }
        }
    }
    return true;
}

This example clearly incurs the cost of copying the queue which is clearly undesirable. This cost is incurred because a queue is the wrong tool for the job. Consider priority_queue or just a vector.

edited Jun 27 '18 at 12:17

answered Jun 26 '18 at 18:02

Jonathan Mee

37,899
23
129
288

1

`std::queue` doesn't provide iterators to the underlying container. – Blastfurnace Jun 26 '18 at 20:09
@Blastfurnace Ugh, how could I forget that, thank you. – Jonathan Mee Jun 27 '18 at 12:18

how to check if queue is sorted using stl

1 Answers1