1

I am a student studying basic algorithm. I wrote a code to get the sum of all the elements by stl:stack.

#include <bits/stdc++.h>
using namespace std;

   

     int main(void)
        {
            ios::sync_with_stdio(0);
            cin.tie(0);
            int k; cin >> k;
            stack<int> s;
            int answer=0;
            while (k--)
            {
                int n; cin >> n;
                if (n == 0)
                {
                    s.pop();
                }
                else 
                {
                    s.push(n);
                }
            }
            for (int i = 0; i < s.size(); i++)
            {
                answer = answer + s.top();
                s.pop();
            }
            cout << answer;
        }

Input:

5 5 4 3 2 1

Output:

6

As I intended, the result should be 15 but there is an error. But if I replace for (int i = 0; i < s.size(); i++) with while(!s.empty()), get normal results. Is there a problem with i <size()? I'd appreciate it if you could answer.

zeon1123
  • 13
  • 3
  • 1
    Please study this too: [Why should I **not** `#include `?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) and [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) TL;DR; `bits/stdc++.h` is not a standard header file. I can't compile your program. – Ted Lyngmo Aug 31 '21 at 17:50
  • 2
    consider what happens to `s.size()` as you pop elements, try using a debugger – Alan Birtles Aug 31 '21 at 17:51
  • Unrelated: `int main(void)` - You don't need `void` there. That's a `C` thing. – Ted Lyngmo Aug 31 '21 at 17:52
  • Size changes everytime there's a pop. – QuentinUK Aug 31 '21 at 18:01
  • Thank you. I learned a lot. – zeon1123 Aug 31 '21 at 18:11

2 Answers2

2

There is a problem with the for loop terminating condition.

for (int i = 0; i < s.size(); i++)

  • Before the 1st iteration: i = 0 and s.size() is 5 so i < s.size() is true
  • Before the 2nd iteration: i = 1 and s.size() is 4 so i < s.size() is true
  • Before the 3rd iteration: i = 2 and s.size() is 3 so i < s.size() is true
  • Before the 4th iteration: i = 3 and s.size() is 2 so i < s.size() is false and the 4th and 5th iteration never happens.

Because the i is being incremented while the size() is being decremented on every iteration (because of the pop() operation) this is effectively doing about half the necessary iterations which results in answer = 1 + 2 + 3 (i.e., answer = 6).

This answer shows a way to fix the for loop implementation but the while(!s.empty()) loop you have in your question would be my preference.

James Adkison
  • 9,412
  • 2
  • 29
  • 43
1

Store size of stack in another variable before using in loop because when you use directly s.size() in loop . At each pop operation , it will change the size of stack every time ,therefore s.size() changes everytime

int size=s.size();

for (int i = 0; i < size; i++)
        {
            answer = answer + s.top();
            s.pop();
        }
        cout << answer;
Rishabh Jain
  • 174
  • 1
  • 7