海智算法训练营第十天 | 第五章 栈与队列part01 | 232用栈实现队列 225 用队列实现栈

学习目标：

1.用栈实现队列 ? ?

2.用队列实现栈

?

1.用栈实现队列 ? ?

原理：利用两个栈，一个用于入队，一个用于出队，当入队栈有数据出队栈没有的时候，就需要入队栈全部放进出队栈。这样出队栈出队的顺序就是队列出队的顺序。

题目：用栈实现队列

?

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    public void push(int x) {
        stackIn.push(x);
    }

    public int pop() {
        IntoOut();
        return stackOut.pop();
    }

    public int peek() {
        IntoOut();
        return stackOut.peek();
    }

    public boolean empty() {
        if(stackOut.isEmpty() && stackIn.isEmpty()) return true;
        return false;
    }

    public void IntoOut(){
        if(!stackOut.isEmpty()) return;
        while(!stackIn.isEmpty()){
            stackOut.push(stackIn.pop());
        }
    }
}

为了程序的简洁，把重复部分的代码总和成一个可以调用的框架。

2.用队列实现栈

题目：用队列实现栈

用两个队列实现栈跟上题一样的思想就不多说了，这里讲用一个队列实现栈，思想：弹出队首元素放到队尾。

卡哥的思想：添加元素的时候直接添加，弹出元素的时候弹出size-1个元素放到队尾。

class MyStack {
    Queue<Integer> queue;
    
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.add(x);
    }
    
    public int pop() {
        rePosition();
        return queue.poll();
    }
    
    public int top() {
        rePosition();
        int result = queue.poll();
        queue.add(result);
        return result;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }

    public void rePosition(){
        int size = queue.size();
        size--;
        while(size-->0)
            queue.add(queue.poll());
    }
}

而我更喜欢用这种，代码更简洁：在添加元素的时候就做好排序。

class MyStack {
    Queue<Integer> queue;

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

    public void push(int x) {
        queue.offer(x);
        int size = queue.size()-1;
        while(size -- >0){
            queue.offer(queue.poll());
        }
    }

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

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

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

学习时长：1h

总结：复习了队列和栈的相关知识，对它们的理解更加深刻。