算法练习(15) - 两个队列实现栈

题目

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

思路

队列(FIFO) , 先进先出,那么只要使用一个空的 临时队列 offer()最新的元素,然后将 原队列的数据 offer()到临时队列,这样,临时队列中的顺序就是最后进来的反而成了最先进来的,也就是说临时队列 pop() 出去的就是最新的元素,那么再互换 临时队列 和原队列的指针,就得到了正确的队列;

题解

import java.util.LinkedList;

class MyStack {

    LinkedList<Integer> data ;
    LinkedList<Integer> revers ;
    LinkedList<Integer> temp ;

    /** Initialize your data structure here. */
    public MyStack() {
         data = new LinkedList<>();
        revers = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        if (data.isEmpty()){
            data.offer(x);
        }else{
            if(!data.isEmpty()){
                revers.offer(x);
            }
            while(!data.isEmpty()){
                revers.offer(data.pop());
            }
            temp = revers;
            revers = data;
            data = temp;
        }
        System.out.println(data);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return data.pop();
    }
    
    /** Get the top element. */
    public int top() {
        return  data.getFirst();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return   data.isEmpty();
    }
}