Finding min in stack

[alex067]

I need to find the minimum in a stack using constant time O(1).

So for example, my current stack contains elements: 20 7 10 5 15
I need to find the minimum, pop the stack, and re-find the minimum.

An example output:
Current min in stack: 5
Popped: 15
Current min in stack: 5
Popped: 5
Current min in stack: 7, since its the next lowest ele
Popped: 10
current min in stack: 7

I do not understand how this can be achieved using a constant runtime.

Also another question, what is the run time for a do-while loop? logn?

[LB]

Where does this O(1) restriction come from? Constant time algorithms are only possible in special cases.

[alex067]

It's an assignment specifying a O(1) runtime

[LB]

At this time I don't know how to answer your question - I don't even think there is and answer, but I am not so sure.

But, I can answer your second question:

alex067 wrote:

what is the run time for a do-while loop? logn?

It depends. No matter what looping structure you use - be it for, while, do-while, recursion, goto, etc. - you have to calculate the time complexity the same way. It depends.

[alex067]

Hm, ok well so far I have this code which finds the min whilst pushing elements to the stack

	stack<int> myS;
	stack<int> minS;
	int ele;
	int size = 0;
	int min = 100;
	cout << "Pushing 5 elements into the stack...  " << endl;
	do
	{
		cin >> ele;
		myS.push(ele);
		size++;
		if (myS.top() < min)
		{
			min = ele;
		}
	} while (size != 5);

I know this is definitely not O(1) right?

[Smac89]

What you have described sounds like a heap, a min heap to be exact. Look it up

Also sounds like a programming interview question I've seen before:
http://www.geeksforgeeks.org/design-and-implement-special-stack-data-structure/

I think the second one is more of what you are looking for

EDIT:
Decided to implement one myself, rather crude, but does the job
http://cpp.sh/8fel

[alex067]

Wow thank you for this! It's exactly what I was looking for

However, can someone please tell me what the runtime is for my code?

[Smac89]

Your code finds the min of all the elements in the stack and has the same timing as the special stack thing. But yours will suffer in terms of time when you pop an element and now try to determine the minimum.

There is an easy way to fix this by making use of that minS stack you have in your code which will now make everything O(1) - pop, push, min
http://cpp.sh/3ehh