力扣labuladong——一刷day95

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

两种数据结构底层其实都是数组或者链表实现的，只是 API 限定了它们的特性，那么今天就来看看如何使用「栈」的特性来实现一个「队列」，如何用「队列」实现一个「栈」

一、力扣225. 用队列实现栈

class MyStack {
    Deque<Integer> deq1;
    Deque<Integer> deq2;

    public MyStack() {
        deq1 = new LinkedList<>();
        deq2 = new LinkedList<>();
    }
    
    public void push(int x) {
        deq1.offerLast(x);
    }
    
    public int pop() {
        while(deq1.size()>1){
            deq2.offerLast(deq1.pollFirst());
        }
        int res = deq1.pollFirst();
        while(!deq2.isEmpty()){
            deq1.offerLast(deq2.pollFirst());
        }
        return res;
    }
    
    public int top() {
        while(deq1.size() > 1){
            deq2.offerLast(deq1.pollFirst());
        }
        int res = deq1.pollFirst();
        deq2.offerLast(res);
        while(!deq2.isEmpty()){
            deq1.offerLast(deq2.pollFirst());
        }
        return res;
    }
    
    public boolean empty() {
        return deq1.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();
 */

二、力扣232. 用栈实现队列

class MyQueue {
    Deque<Integer> deq1;
    Deque<Integer> deq2;
    public MyQueue() {
        deq1 = new LinkedList<>();
        deq2 = new LinkedList<>();
    }
    
    public void push(int x) {
        deq1.offerLast(x);
    }
    
    public int pop() {
        while(deq1.size() > 1){
            deq2.offerLast(deq1.pollLast());
        }
        int res = deq1.pollLast();
        while(!deq2.isEmpty()){
            deq1.offerLast(deq2.pollLast());
        }
        return res;
    }
    
    public int peek() {
        while(deq1.size() > 1){
            deq2.offerLast(deq1.pollLast());
        }
        int res = deq1.pollLast();
        deq2.offerLast(res);
        while(!deq2.isEmpty()){
            deq1.offerLast(deq2.pollLast());
        }
        return res;
    }
    
    public boolean empty() {
        return deq1.isEmpty();
    }
}

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