代码随想录算法训练营（JAVA） | 第五章 栈与队列part01

      今日任务 

力扣 232. 用栈实现队列，   225. 用队列实现栈

无论是栈实现队列还是队列实现栈都是用两个

而队列由于其特性能达到只使用一个实现，由于其还有Deque接口更是能做到只是用单个解决问题

题目 ：232. 用栈实现队列

思路

先搞清楚我要什么  FIFO 实现 FILO

题解

需要注意的是：当push和pop前先要去考虑 辅助的stack中是否还有值？怎么处理？

class MyQueue {
    Stack<Integer> stack1 ;
    Stack<Integer> stack2 ;
 
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        dumpstackIn();
        return stack2.pop();
    }
    
    public int peek() {
        dumpstackIn();
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
 
    private void dumpstackIn() {
        if (!stack2.isEmpty()) return;
 
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    } 
}
 
/**
 * 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();
 */

题目 ：225. 用队列实现栈

思路

  

题解

1. 使用两个Queue  LinedList实现

class MyStack {
    Queue<Integer> que1;
    Queue<Integer> que2;
 
    public MyStack() {
        que1 = new LinkedList<>();
        que2 = new LinkedList<>();
    }
    
    public void push(int x) {
        que2.offer(x);
        while (!que1.isEmpty()) {
            que2.offer(que1.poll());
        }
 
        Queue<Integer> tempQue;
        tempQue = que1;
        que1 = que2;
        que2 = tempQue;
    }
    
    public int pop() {
        return que1.poll();
    }
    
    public int top() {
        return que1.peek();
    }
    
    public boolean empty() {
        return que1.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();
 */

2. Queue   ArrayDeque 处理push。将que1队列中剩余的数+新数导到que2再执行一遍反转即栈的逻辑

class MyStack {
    Queue<Integer> que1;
    Queue<Integer> que2;
 
    public MyStack() {
        que1 = new ArrayDeque<>();
        que2 = new ArrayDeque<>();
    }
    
    public void push(int x) {
        while (que1.size() > 0) {
            que2.add(que1.poll());
        }
        que1.add(x);
        while (que2.size() > 0) {
            que1.add(que2.poll());
        }
    }
    
    public int pop() {
        return que1.poll();
    }
    
    public int top() {
        return que1.peek();
    }
    
    public boolean empty() {
        return que1.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();
 */

3.使用双端队列解决。为了实现单头需要将数据从左边导出到右边（或者从右到左，只要逻辑顺序没错就行）

class MyStack {
    Deque<Integer> deq;
    public MyStack() {
        deq = new ArrayDeque<>();
    }
    
    public void push(int x) {
        deq.addFirst(x);
    }
    
    public int pop() {
        int size = deq.size();
        while (size-- > 0) {
            deq.addFirst(deq.peekLast());
            deq.pollLast();
        }
        return deq.pollFirst();
    }
    
    public int top() {
        return deq.peekFirst();
    }
    
    public boolean empty() {
        return deq.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();
 */

 4.使用一个Queue  LinkedList实现。对于push每次都把新的数翻转到最后。

class MyStack {
    Queue<Integer> que;
 
    public MyStack() {
        que = new LinkedList<>();
    }
    
    public void push(int x) {
        que.offer(x);
        int size = que.size();
        while (size-- > 1) {
            que.offer(que.poll());
        }
    }
    
    public int pop() {
        return que.poll();
    }
    
    public int top() {
        return que.peek();
    }
    
    public boolean empty() {
        return que.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();
 */