Microsoft Interview Question
Software Engineer in TestsTeam: MSIT
Country: United States
I think the 3rd step can be avoided, most of the times, in both the method, as transferring elements again and agains etween stack for every operation is a costly affair. Rather one can avoid it, by putting condition like...
Void PushBottom()
{
if (!A.isEmpty()) --> transfer those elements to B, if B has capacity to accomodate
If ( A.isEmpty() ) -> push the new element at bottom
}
int PopBottom()
{
if( ! A.isEmpty() ) --> Return the only element present, which is BootomMost in A
else if (B is not Empty) --> return the topmost element from B; (as it will become bottom most if you transfer it to A);
}
This way one can avoid transfers of elements between 2 stacks and do it only when it is necessary.
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;
}
}
PUSHBOTTOM()
- Dinesh March 03, 20121.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.