in the below code just go to the statement "while (s.empty() == false && s.top() < arr[i]) "
and replace it with “while ( s.top() < arr[i] && s.empty() == false )”
the result should be the same right? but it’s not (in any compiler).
as i know (A && B) and (B && A) are same.
If you know about this please let me know.
// A Stack based C++ program to find next
// greater element for all array elements.
#include <bits/stdc++.h>
using namespace std;
/* prints element and NGE pair for all
elements of arr[] of size n */
void printNGE(int arr[], int n) {
stack < int > s;
/* push the first element to stack */
s.push(arr[0]);
// iterate for rest of the elements
for (int i = 1; i < n; i++) {
if (s.empty()) {
s.push(arr[i]);
continue;
}
/* if stack is not empty, then
pop an element from stack.
If the popped element is smaller
than next, then
a) print the pair
b) keep popping while elements are
smaller and stack is not empty */
while (s.empty() == false && s.top() < arr[i])
{
cout << s.top() << " --> " << arr[i] << endl;
s.pop();
}
/* push next to stack so that we can find
next greater for it */
s.push(arr[i]);
}
/* After iterating over the loop, the remaining
elements in stack do not have the next greater
element, so print -1 for them */
while (s.empty() == false) {
cout << s.top() << " --> " << -1 << endl;
s.pop();
}
}
/* Driver program to test above functions */
int main() {
int arr[] = {11, 13, 21, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printNGE(arr, n);
return 0;
}
In AND (&&) operator the compiler does not check the second condition if first condition comes out to be false, as whole condition would be false only.
Try with a basic condition like just comparing two numbers.
The problem here is that compiler doesn’t check your 2nd condition if 1st condition is wrong. If you replace s.empty()==false to s.top() < arr[i] as your first condition, you would get a runtime error when the stack is empty and your code executes s.top < arr[i]. So, its always better to check the availability of an element first.
the loop isn’t working that’s the point. as soon as the code hits s.empty()==false as false (meaning stack is empty ) then loop will not run. s.empty() == false gives you true when stack is not empty.
you are correct but try to understand my question.
this stack is initialised at compile time. so the input is same every time.
if the stack is empty then ofcourse the loop will not work. i agree.
since the stack is initialised at compile time. so if stack is empty then it is empty for both the cases -->
while(s.empty() == false && s.top()<arr[i])
while(s.top()<arr[i]&& s.empty() == false)
compile time input is = {11, 13, 21, 3}
then why results are different
i hope u understand what i am trying to say.
just copy the code and try it on compiler you will know what i am trying to say.
What do you mean by the result being different? Actually your code should break because consider this scenario , Assume your stack is empty and your code hits this line
while(s.top()<arr[i]&& s.empty() == false)
What would be checked first ? s.top() < arr[i] would be checked first but, how can your code access s.top() when the stack is empty. So, you should keep the check for emptiness first. Your code might run on some compilers without throwing a runtime exception, but ideally it should , as you are accessing s.top() supposedly when its empty.
@rashit If you swap the conditions in the while loop , it will give runtime error after one iteration because for 11 -> 13 is correct but now stack is empty and due to swapped conditions you are accessing stack.top() which is invalid , so it gives runtime error.
And depending on the compiler you may or may not be able to see the output processed till it hits the runtime error, so it is always better to check if element is available in the stack or not.
After printing 11 -> 13
If you use this - while(s.empty() == false && s.top()<arr[i]) the condition will be false and it can to next iteration of for loop but,
If you use this while(s.top()<arr[i]&& s.empty() == false) then since the stack is empty so accesing the stack top is invalid and will give RTE, and program will terminate.