Assume you have infinite memory. Design an algorithm using stacks that can find the minimum and maximum at any point while reading an infinite sequence of numbers in least possible time. Eg. 5, 9, 2, 35, 23, 1, ... After 3rd element, the algorithm would tell min = 2, max = 9 After 6th element, algorithm would tell min = 1, max = 35 Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: There is an unlimited space. Hints: Use 3 stacks. Click again for solution. Solution: 1. 1st stack will be the main stack in which we are pushing all elements 2. 2nd stack will contain maximum elements up to that point 3. 3rd stack will contain minimum elements up to that point. So range can also be found in O(1) time, by popping from 2nd stack & 3rd stack and taking their difference. Complexities : Time : O(1) Space : Unlimited Code : template <class T> class range_stack<T> { private : stack<T> main, min, max; public : int push(T value){ main.push(value); if(main.empty()){ min.push(value); max.push(value); } else { if(min.top() > value) min.push(value); else min.push(min.top()); if(max.top() < value) max.push(value); else max.push(max.top()); } } T pop(){ T tmp = main.top(); main.pop(); min.pop(); max.pop(); return tmp; } T range(){ return max.top() - min.top(); } }

For beginners :

Implement Stack and Queue by yourself. Many of you have not done it yet. Implement all the primitive operations on Stack and Queue. Try to implement it without using an Array.

For others:

1. Implement a Stack using 2 Queues.
2. Implement a Queue using 2 Stacks. [Implementing any structure means all the primitive operations have to be performed].

Code it.


P.S. - Its not bad to be a beginner :)



Solution :


Basically in this problem, You need not to be efficient in terms of time and space complexity. You just need to think how this goal will be achieved. 
For Stack using 2 Queues basic idea is, 
For PUSH operation:
ENQUEUE all the elements in only one of the Queue [after first PUSH, insert into non-empty Queue] (using flag is an option or you may check this as a condition of emptiness).
For POP operation:
DEQUEUE all the elements except one from the non-empty Queue and ENQUEUE all of these De-queued elements of first Queue into the second one making first Queue empty.

Similarly for Queue using 2 Stacks. 

Reverse a stack, using just push(), pop(), top() operations, in its place itself.
You can not assign any known memory address.

Solution: 

Simple methodology for this problem is, take last element from the stack i.e. you need to empty the stack [do it recursively, keeping other elements in memory].
Push the last element in the stack again.
Now while pushing each of earlier elements, first empty whole stack and then push them.
This will ultimately turn into reversed stack.

Code: 
Code is pretty much intuitive and not exactly executable in the current condition, so make yourself do some work and write something on your own. :)

void reverse(Stack st)
{
  int m = (int)st.Pop();
  if (st.Count != 1)//checking for last element
  reverse(st);//popping out all the elements for reversing
  Push(st , m);//now the last element popped out i.e. the bottom element will be pushed to stack, which is now empty
}


void Push(Stack st , int a)
{
  int m = (int)st.Pop(); // if stack has already some elements then pop them out
  if (st.Count != 0)
    Push(st , a); // new items will be pushed to the bottom-most position.
  else
    st.Push(a); 
  st.Push(m); //now atlast push the item popped out first i.e. the last element from original stack
}