CareerCup

PUSHBOTTOM()
1.pop all the elements from stack A into stack B.
2.push the element in to stack A.
3. Push back all the elements one by one in to statck A from stack B

POPBOTTOM()
1.pop all the elements from stack A into Stack B except the last element.
2.Now pop the bottom element .
3.push back similarly from stack B to stack A.

I think push will be the same , push the element in stack A , Now for pop , first pop all the elements from stack A and push them to stack B, and return first element of the stack B.

public class ReverseStack
    {
        private Stack _stackA = new Stack();
        private Stack _stackB = new Stack();

        public void PushBottom(object value)
        {
            while(!_stackA.IsEmpty())
            {
                _stackB.Push(_stackA.Pop());
            }
            _stackA.Push(value);
            while(!_stackB.IsEmpty())
            {
                _stackA.Push(_stackB.Pop());
            }
        }

        public Node PopBottom()
        {
            while (!_stackA.IsEmpty())
            {
                _stackB.Push(_stackA.Pop());
            }
            var node = _stackB.Pop();
            while (!_stackB.IsEmpty())
            {
                _stackA.Push(_stackB.Pop());
            }
            return node;
        }
    }

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
node *next;
};

void push(struct node **top, int data) {
//struct node *t = top;
struct node *newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = data;
newnode->next = *top;
*top = newnode;
}

int IsEmpty(struct node *top) {
return top == NULL;
}

int pop(struct node **topA,struct node **topB) {
struct node *t = NULL;
while(!IsEmpty(*topA)) {
t = *topA;
//t = t->next;
push(&*topB,t->data);
*topA = t->next;
}
return t->data;
}

void pushbottom(struct node **topA,struct node **topB,int data) {
pop(&*topA,&*topB);
push(&*topA,data);
pop(&*topB,&*topA);
}

int popbottom(struct node **topA,struct node **topB) {
pop(&*topA,&*topB);
struct node *t = *topB;
*topB = t ->next;
pop(&*topB,&*topA);
return t->data;
}

int main() {
struct node *topA = NULL;
struct node *topB = NULL;
push(&topA,1);
push(&topA,2);
push(&topA,3);
//pop(&topA,&topB);
pushbottom(&topA,&topB,0);
printf("%d\n",popbottom(&topA,&topB));
while(topA!=NULL) {
printf("%d\n",topA->data);
topA = topA->next;
}
}

i guess we don need to empty any stack..aur transfer element just take two flags :insertion flag and another deletion flag...all will happen alternately..thats it 1 for stack a and one for stack b

template<typename T>
void pushBottom(T x)
{
         if (s.empty()) s.push(x);
         else {
                  Top t = s.top(); s.pop();
                   pushBottom(x);
                   s.push(t);
         }
}

template<typename T>
T popBottom()
{
        T top = s.top(); s.pop();
         if (s.empty()) return T;
         T ans = popBottom();
          s.push(top);
          return ans;
}