1 class MyStack  2 {  3     private Queue q1;  4     private Queue q2;  5       6     public MyStack(int size)  7     {  8         this.q1 = new Queue(size);  9         this.q2 = new Queue(size); 10     } 11      12     public boolean isFull() 13     { 14         return q1.isFull(); 15     } 16      17     public boolean isEmpty() 18     { 19         return q1.isEmpty(); 20     } 21      22     //时间复杂度: O(1) 23     public void push(int k) throws Exception 24     { 25         if(this.q1.isFull()) 26             throw new Exception("Overflow."); 27         else 28             this.q1.EnQueue(k); 29     } 30      31     //时间复杂度: O(n) 32     public int pop() throws Exception 33     { 34         if(this.q1.isEmpty()) 35             throw new Exception("Underflow."); 36         else 37         { 38             for(int i = this.q1.getLength(); i > 1; i--) 39                 this.q2.EnQueue(this.q1.DeQueue()); 40             int key = this.q1.DeQueue(); 41             while(!this.q2.isEmpty()) 42                 this.q1.EnQueue(this.q2.DeQueue()); 43             return key; 44         } 45     } 46 } 47  48 class Queue 49 { 50     private int front; 51     private int rear; 52     private int[] a; 53      54     public Queue(int size) 55     { 56         this.front = this.rear = 0; 57         this.a = new int[size]; 58     } 59      60     public boolean isFull() 61     { 62         return (this.rear + 1) % this.a.length == this.front; 63     } 64      65     public boolean isEmpty() 66     { 67         return this.rear == this.front; 68     } 69      70     public void EnQueue(int k) throws Exception 71     { 72         //该判断是冗余的 73         /*if(this.isFull()) 74          *  75             throw new Exception("Overflow.");*/ 76         //else 77         { 78             this.a[this.rear] = k; 79             this.rear = (this.rear + 1) % this.a.length; 80         } 81              82     } 83      84     public int DeQueue() throws Exception 85     { 86         //该判断是冗余的 87         /*if(this.isEmpty()) 88             throw new Exception("Underflow.");*/ 89         //else 90         { 91             int key = this.a[front]; 92             this.front = (this.front + 1) % this.a.length; 93             return key; 94         } 95     } 96      97     public int getLength() 98     { 99         return (this.rear - this.front + this.a.length) % this.a.length;100     }101 }