代码随想录算法训练营二十四期第十天|LeetCode232. 用栈实现队列、LeetCode225. 用队列实现栈

一、LeetCode232. 用栈实现队列

题目链接：232. 用栈实现队列
在构造函数中实例化两个栈对象。然后用栈1来存储队列的元素，插入时需要用到栈2。
栈1的栈顶当作队列的对头，栈底当作队列的尾。
由于栈先进后出的原则，如果实现队列插入元素到队尾的功能，就要先将栈1的元素依次通过栈顶弹出然后插入到栈2里面，这时栈2的栈顶相当于队列的队为，栈底相当于队列的队头。
然后将要插入的元素放到栈1的底部，再从栈2依次弹出元素放到栈1里面。
队列的peek、pop、empty则不需要用到栈2了，因为他们都不需要对队为进行处理，而对头就相当于栈1栈顶，peek只需要返回栈顶元素，pop在返回栈顶元素的同时删除栈顶元素，empty判断栈1是否为空。
代码如下：

class MyQueue {
    private Stack<Integer>stack1;
    private Stack<Integer>stack2;

    public MyQueue() {//通过无参构造，实例化两个栈对象
        stack1 = new Stack();
        stack2 = new Stack();

    }
    
    public void push(int x) {//先将栈1里面的内容依次弹出放到栈2里面，然后将x放到栈1底部，再从栈2里面弹出数放回栈1
        while(!stack1.empty()) {
            stack2.push(stack1.pop());
        }
        stack1.push(x);
        while(!stack2.empty()) {
            stack1.push(stack2.pop());
        }

    }
    
    public int pop() {//如果栈1为空说明队列也为空，否则栈1的栈顶元素就是队列的头元素，返回栈1的顶部元素
        if(stack1.empty()) {
            return -1;
        }else {
            return stack1.pop();
        }

    }
    
    public int peek() {//同理
        if(this.empty()) return -1;
        return stack1.peek();

    }
    
    public boolean empty() {同理
        if(stack1.empty()) return true;
        else return false;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

二、LeetCode225. 用队列实现栈

题目链接：225. 用队列实现栈
构造函数创建两个队列，队1当作栈，队2用来辅助插入元素。
根据栈先进后出原则和队列先进先出原则，将要插入的元素先插入辅助队列2中，然后将队列1的元素依次弹出插入队列2，此时队列2的顺序就是栈的顺序，不过方便因后边操作，将队1和队2交换一下。
代码如下：

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.peek() != null) {
            que2.offer(que1.remove());
        }
        Queue<Integer>newque = que1;
        que1 = que2;
        que2 = newque;

    }
    
    public int pop() {
        if(que1.isEmpty()) return -1;
        return que1.poll();

    }
    
    public int top() {
        if(que1.isEmpty()) return -1;
        return que1.element();

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

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

总结

熟悉栈和队列的底层实现。