title: How to solve the stock spans problem using a stack?
body: <p>I am looking at <a href="https://practice.geeksforgeeks.org/problems/stock-span-problem-1587115621/1" rel="nofollow noreferrer">this stock span problem</a>:</p>
  <blockquote>
  <p>The stock span problem is a financial problem where we have a series of <strong>n</strong> daily price quotes for a stock and we need to calculate the span of stock’s price for all <strong>n</strong> days.</p>
  <p>The span <strong>S<sub>i</sub></strong> of the stock’s price on a given day <strong>i</strong> is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.</p>
  </blockquote>
  <p>In <a href="https://slideplayer.com/slide/16508278/96/images/4/Computing+Spans+with+a+Stack.jpg" rel="nofollow noreferrer">this description</a> an algorithm is explained:</p>
  <blockquote>
  <h3>Computing Spans with a Stack</h3>
  <ul>
  <li>We keep in a stack the indices of the last element that is taller when &quot;looking back&quot;</li>
  <li>We scan the array from left to right
  <ul>
  <li>Let  be the current index</li>
  <li>We pop indices from the stack until we find index  such that [] &lt; []</li>
  <li>We set [] &lt;=  − </li>
  <li>We push  onto the stack
  <a href="https://i.stack.imgur.com/qLalY.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/qLalY.png" alt="enter image description here" /></a></li>
  </ul>
  </li>
  </ul>
  </blockquote>
  <p>The output for the example is supposed to be {1,1,2,1,2,3,6,1}, but my code outputs {1,1,2,2,2,3,6,7}</p>
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  
  #define SIZE 8
  
  typedef int element;
  typedef struct StackType {
      element elem[SIZE];
      int top;
  } StackType;
  
  void init(StackType *A) {
      A-&gt;top = -1;
  }
  
  int isEmpty(StackType *A) {
      return A-&gt;top == -1;
  }
  
  int isFull(StackType *A) {
      return A-&gt;top == SIZE - 1;
  }
  
  void push(StackType *A, element i) {
      if (isFull(A)) {
          printf(&quot;FULL\n&quot;);
          return;
      }
      A-&gt;top++;
      A-&gt;elem[A-&gt;top] = i;
  }
  
  element pop(StackType *A) {
      if (isEmpty(A)) {
          printf(&quot;Empty\n&quot;);
          return 0;
      }
      element temp = A-&gt;elem[A-&gt;top];
      A-&gt;top--;
      return temp;    
  }
  
  void spans(StackType *A, int X[], int S[]) {
      for (int i = 0; i &lt; SIZE; i++) {
          while (!isEmpty(A) &amp;&amp; (X[A-&gt;top] &lt;= X[i]))
              pop(A);
          if (isEmpty(A))
              S[i] = i + 1;
          else
              S[i] = i - (A-&gt;top);
          push(A, i);
      }
      while (!isEmpty(A))
          pop(A);
      return;
  }
  
  int main() {
      StackType A;
      init(&amp;A);
      int X[SIZE] = { 60, 30, 40, 10, 20, 30, 50, 40 };
      int S[SIZE];
      spans(&amp;A, X, S);
      for (int i = 0; i &lt; SIZE; i++)
          printf(&quot;[%d] &quot;, S[i]);  
      printf(&quot;\n&quot;);
      return 0;
  }
  </code></pre>
  <p>I debugged the function <code>void spans</code>, and I saw <code>A-&gt;top</code> doesn't change in the right way. For example, when <code>i = 2</code>, <code>A-&gt;top</code> should be <code>2</code>, but in reality, <code>A-&gt;top</code> is <code>1</code>. There seems something wrong with function <code>pop</code> and <code>push</code>, but I couldn't find the problem.</p>