一、题目

　　1、审题

　　

　　2、分析

　　　　使用栈来实现队列的功能。

 

二、解答

　　1、思路

　　　　方法一、

　　　　　　只修改 Pop 方法，使得栈中元素排序为队列的规则。

1 public class MyQueue { 2      3     Stack
     
       stack; 4     /** Initialize your data structure here. */ 5     public MyQueue() { 6         stack = new Stack<>(); 7     } 8      9     /** Push element x to the back of queue. */10     public void push(int x) {11         if(stack.isEmpty()) {12             stack.push(x);13         }14         else {15             Stack
      
        tmp = new Stack<>();16             while(!stack.isEmpty())17                 tmp.push(stack.pop());18             stack.push(x);19             while(!tmp.isEmpty())20                 stack.push(tmp.pop());21         }22     }23     24     /** Removes the element from in front of queue and returns that element. */25     public int pop() {26         return stack.pop();27     }28     29     /** Get the front element. */30     public int peek() {31         return stack.peek();32     }33     34     /** Returns whether the queue is empty. */35     public boolean empty() {36         return stack.isEmpty();37     }38 }
      
     

 

　　方法二、

　　　　使用两个 Stack，input、output。

　　　　push： 压入 input 栈。

　　　　pop、peek： 若 output 不为空，则对 output 操作； 若 output 为空，则将 input 元素全部压入 output，在对 output 操作。

　　　　empty： 当 output、input 全为空时才返回 true。

1 class MyQueue { 2  3     Stack
     
       input = new Stack<>(); 4     Stack
      
        output = new Stack<>(); 5      6     public void push(int x) { 7         input.push(x); 8     } 9     10     public int pop() {11         peek();12         return output.pop();13     }14     15     public int peek() {16         if(output.isEmpty()) {17             while(!input.isEmpty())18                 output.push(input.pop());19         }20         return output.peek();21     }22     23     public boolean empty() {24         return input.empty() && output.empty();25     }26 }