Microsoft Interview Question
Software Engineer / DevelopersTake 2 stacks
S1 and S2
Initially both point to null when you push an element make both point to that element
pushing an element push on s1 popping an element pop it from s2
example
elements
5,7,8,9
push(s1,5)
s2.top=s1.top
push(s1,7)
push(s1,8)
push(s1,9)
pop(s2); //this will pop 5
meke the next of 5 as the top of s2
assumption pointers used for maintaining stacks
class Queue
{
stack<int> s1;
stack<int> s2;
int size;
enqueue(int);
int dequeue();
};
Queue::enqueue(int num)
{
while(!s1.empty())
s2.push(s1.pop());
s1.push(num);
size++;
while(!s2.empty())
s1.push(s2.pop());
}
int Queue::dequeue()
{
if(size<=0) return -1;
while(!s1.empty())
s2.push(s1.pop());
int num=s2.pop();
size--;
while(!s2.empty())
s1.push(s2.pop());
return num;
}
public class QueueBasedOnTwoStaks
{
private Stack<int> inStack;
private Stack<int> outStack;
private int capacity;
private int count;
public QueueBasedOnTwoStaks(int capacity)
{
this.inStack = new Stack<int>(capacity);
this.outStack = new Stack<int>(capacity); ;
this.capacity = capacity;
this.count = 0;
}
public int Count
{
get { return count; }
}
public void Enqueue(int value)
{
if (this.count == this.capacity)
{
throw new InvalidOperationException("queue is full");
}
this.inStack.Push(value);
this.count++;
}
public int Dequeue()
{
if (this.count == 0)
{
throw new InvalidOperationException("queue is empty");
}
if (this.outStack.Count == 0)
{
while (this.inStack.Count > 0)
{
this.outStack.Push(this.inStack.Pop());
}
}
int result = this.outStack.Pop();
this.count--;
return result;
}
}
<pre lang="" line="1" title="CodeMonkey45501" class="run-this"> public class QueueBasedOnTwoStaks
{
private Stack<int> inStack;
private Stack<int> outStack;
private int capacity;
private int count;
public QueueBasedOnTwoStaks(int capacity)
{
this.inStack = new Stack<int>(capacity);
this.outStack = new Stack<int>(capacity); ;
this.capacity = capacity;
this.count = 0;
}
public int Count
{
get { return count; }
}
public void Enqueue(int value)
{
if (this.count == this.capacity)
{
throw new InvalidOperationException("queue is full");
}
this.inStack.Push(value);
this.count++;
}
public int Dequeue()
{
if (this.count == 0)
{
throw new InvalidOperationException("queue is empty");
}
if (this.outStack.Count == 0)
{
while (this.inStack.Count > 0)
{
this.outStack.Push(this.inStack.Pop());
}
}
int result = this.outStack.Pop();
this.count--;
return result;
}
}
</pre><pre title="CodeMonkey45501" input="yes">
</pre>
Take stacks S1 and S2.
- Sadineni November 29, 2006a. All the elements are maintained in S1.
b. Whenever you want to EnQueue an element, pop all the elements of S1 and Push to S2
c. Push the new element to S1 and then Pop all the elements of S2 to S1
d. When you want to DeQueue an element, Pop the element from S1.
TestCases:
1. Checking for the lower size limits like: Queue is empty and try DeQueue
2. Queue is full and try EnQueue