class MyStack
{
private Queue q1;
private Queue q2;
public MyStack(int size)
{
this.q1 = new Queue(size);
this.q2 = new Queue(size);
}
public boolean isFull()
{
return q1.isFull();
}
public boolean isEmpty()
{
return q1.isEmpty();
}
//时间复杂度: O(n)
public void push(int k) throws Exception
{
if(this.isFull())
throw new Exception("Overflow.");
else
{
while(!this.q1.isEmpty())
this.q2.EnQueue(this.q1.DeQueue());
this.q1.EnQueue(k);
while(!this.q2.isEmpty())
this.q1.EnQueue(this.q2.DeQueue());
}
}
//时间复杂度: O(1)
public int pop() throws Exception
{
if(this.isEmpty())
throw new Exception("Underflow");
else
return this.q1.DeQueue();
}
}
class Queue
{
private int front;
private int rear;
private int[] a;
public Queue(int size)
{
this.front = this.rear = 0;
this.a = new int[size];
}
public boolean isFull()
{
return (this.rear + 1) % this.a.length == this.front;
}
public boolean isEmpty()
{
return this.rear == this.front;
}
public void EnQueue(int k) throws Exception
{
//该判断是冗余的
/*if(this.isFull())
*
throw new Exception("Overflow.");*/
//else
{
this.a[this.rear] = k;
this.rear = (this.rear + 1) % this.a.length;
}
}
public int DeQueue() throws Exception
{
//该判断是冗余的
/*if(this.isEmpty())
throw new Exception("Underflow.");*/
//else
{
int key = this.a[front];
this.front = (this.front + 1) % this.a.length;
return key;
}
}
public int getLength()
{
return (this.rear - this.front + this.a.length) % this.a.length;
}
}