LeetCode.225 用队列实现栈

1题目

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

2.代码实现

方法一：用两个队列实现

class MyStack {
    Queue<Integer> queue1 ;//和栈中保持一样元素的队列
    Queue<Integer> queue2 ;//辅助队列

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();

    }
    
    public void push(int x) {
        queue2.offer(x);//首先先把元素放到辅助队列中
        //循环判断队列1，把里面的元素全部放到辅助队列2中，此时放进去之后里面元素的顺序已经倒过来了
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        //借助另一个队列进行队列中数据的交换，把辅助队列的数据放到队列1中，此时数据与原来队列1的是相反的，最后输出的时候就实现了栈的效果
         Queue<Integer> queuetemp;
         queuetemp = queue1;
         queue1 = queue2;
         queue2 = queuetemp;

    }
    //注意下面的操作都是对队列1 进行的，队列2只是一个辅助队列
    
    //出队列，移除并返回栈顶元素。
    public int pop() {
        return queue1.poll();

    }
    
    //返回栈顶元素
    public int top() {
        return queue1.peek();

    }
    
    // 如果栈是空的，返回 true ；否则，返回 false 。
    public boolean empty() {
        return queue1.isEmpty();

    }
}




/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

方法二：用一个队列实现

class MyStack {
    Queue<Integer> queue;//只用一个队列实现栈

    public MyStack() {
    queue = new LinkedList<>();


    }
   // 每 offer 一个数（A）进来，都重新排列，把这个数x放到队列的队首
    public void push(int x) {
        //先获取此时的队列里的元素的长度，决定了循环的次数
        int size = queue.size();
        queue.offer(x);//然后把这个元素添加进去
        for(int i=0; i<size; i++){
            queue.offer(queue.poll());//把原来的元素都出队列再入队列
        }

    }
    
    public int pop() {
        return queue.poll();

    }
    
    public int top() {
        return queue.peek();

    }
    
    public boolean empty() {
        return queue.isEmpty();

    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */