[Problem1 SPOJ:STPAR] Stacks use case; Ad-hoc

Starting last weekend I have started picking up problems from the certification syllabus of the Codechef Certified Data Structure & Algorithms Programme: CCDSAP ( https://www.codechef.com/certification/prepare ). I would definitely recommend solving the practice material even if you are not willing to go for the certification.

I'll solve these in increasing order of difficulty and not necessarily sequentially while skipping the cake-walk ones and also probably the ones that I have done previously.
This way I can ensure this series of self-paced hackathon-cum-blogathon will eventually come to an end, with an end to the problems in this syllabus.

~
PROBLEM: http://www.spoj.com/problems/STPAR/

I had done this problem earlier so it was a good candidate for an ice-breaker. I first (sometime in 2010) solved this in Java. This time in C++ using an on-the-fly algorithm that doesn't store all inputs before processing them but processes each input as it comes in a single pass.


SOLUTION: https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-STPAR.cpp
Tested and accepted at : http://www.spoj.com/status/STPAR,chandniverma/

The time complexity is O(n).
Space needed is O(n) (actually only n).