Code Fragment: computeSpans



#include <iostream>
#include <vector>
#include "LinkedStack.h"

using namespace std;                            // make std stuff available

/**
 * A stock-quote class, which contains a day's stock price and span.
 */
class Quote { 
public:
  int day;					// which day
  int price;					// this day's price
  int span;					// this day's span
  Quote(int d = 0, int p = 0)			// constructor
    {  day = d;  price = p;  }
};
/**
 * Compute the span of the stock price on each day by means of a
 * stack, and store the information in the Quote array Q.
 */
void computeDailyHighSpan(vector<Quote>& Q) {
  int prevHigh;					// previous higher day
  LinkedStack<Quote> D;
  for (int i = 0 ; i < Q.size(); i++) {		// process the current day i
    while ( !D.isEmpty() &&			// if stack not empty and
            Q[i].price >= D.top().price ) {	// ... today's price is higher
      D.pop();
    }
    if (D.isEmpty()) prevHigh = -1;		// day i is a new high
    else prevHigh = D.top().day;		// else stack top is high

    Q[i].span = i - prevHigh;			// compute and store the span
    D.push(Q[i]);				// add current to the stack
  }
}