## Microsoft Interview Question

Software Engineer / Developersvoid enqueue(int i)

{

push(i);

}

int dequeue()

{

int temp1,temp2;

if (!count()) return ***;//TBD

if (count()==1) temp2=pop();

else {

temp1=pop();

temp2=dequeue();

enqueue(temp1);

}

return temp2;

}

```
#define QUEUE_EMPTY -9999
int dequeue()
{
int temp,result;
if (!count())
return QUEUE_EMPTY ;//Or call pop again its return
//value finally returned
if (count()==1)
{
temp=pop();
return temp;
}
temp=pop();
result=dequeue();
push(temp);
return result;
}
```

doesnt a queue add from the bottom ,the above solution seems to be opposite of what needs to be done

Please comment on the statement

temp2=dequeue();

should it not just be dequeue();

why do we need to return the value of dequeue every time in temp2?

Update my algorithm above.

For enqueue(),

1) if S.count() = 0 and T.count() != 0, then pop each item in T and push it into S one by one

2) Invoke S.push() to enqueue the new item

For dequeue(),

1) if S.count() > 0, then pop each item in S and push it into T

2) Invoke T.pop() to dequeue an item

A Java implementation using only one stack. Use recursion to implement dequeue.

```
public class ID64863
{
// Use only one stack. Use recursion to implement dequeue.
StackWithCount stack=new StackWithCount();
public void enqueue(int element)
{
stack.push(element);
}
public int dequeue()
{
if (stack.count()<=1)
return stack.pop();
int top=stack.pop();
int result=dequeue();
stack.push(top);
return result;
}
public static void main(String[] args)
{
ID64863 queue=new ID64863();
queue.enqueue(0);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
}
public class StackWithCount extends Stack<Integer>
{
public int count()
{
return elementCount;
}
}
}
```

ah sorry! the question was to implement enqueue(int i) and dequeue() using stack ADT

- zaya November 11, 2008