Stack Operations

Implement a STACK using a singly LINKED LIST

 Push()-Adding elemnt at start of linked list
 Pop()-Deleting element at start of the List

Track the Maximum Element in a Stack:
In a Stack, keep track of max­i­mum value in it. It might be the top ele­ment in the stack but once it is poped out, the max­i­mum value should be from the rest of the ele­ments in the stack.
http://algorithms.tutorialhorizon.com/track-the-maximum-element-in-a-stack/

Sort a Stack:
Given a stack S, write a C program to sort the stack (in the ascending
order).
We are not allowed to make any assumptions about how the stack is implemented.
The only functions to be used are:
Push Pop Top IsEmpty IsFull
Concept:
Use a temp variable to store the popped item in each recursive traversal.Then go on popping the stack until stack is empty and go on pushing the item in the recursion thereafter.O(n) stack space is used in this process.
Pseudo Code:

void recursive(Stack s)
{
if(s.isEmpty == true)
return ;
elem temp = s.pop();
recursive(s);
recur_push(temp, s);
return;
}
recur_push(elem t, stack s)
{
if(s.isEmpty == null || s.top() > t)
{
s.push(t);
return;
}
temp1= s.pop()
recur_push(t,s);
s.push(temp1);
}

Alternative:

We can use another stack to do the sorting. Suppose s1 is the original stack and s2 is the other stack. The algorithm will look like this,

- Pop from s1(e1) and peek s2(e2).
- if e2 < e1, then push e1 on s2,
- if e2 > e1, then keep popping from s2 into s1 till the next element is less than e1 and then push e1 on s2.

Keep doing it till s1 is empty. Now, s2 will be sorted in ascending order! This algorithm will have a time complexity of O(N^2).