用栈实现队列

link：232. 用栈实现队列 - 力扣（LeetCode）

思路分析

首先理清楚栈和队列的异同.
队列是先进先出 栈先进后出【两者都能存储元素】
再来看peek()和poll().
栈和队列都有peek() 可以称之为“瞄一眼”只是看一下当前栈顶/队头元素是什么.
栈中的pop()直接返回栈顶元素（出栈）
队列中的poll()在某种层面上就等效于pop()了.

先用栈1存储所有元素 再逐个pop到栈2中
最后pop栈2全部元素.
注意判断栈满（是否需要扩容）

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
43
44
45
46
class MyQueue {
  private Stack<Integer> stack1;
  private Stack<Integer> stack2;
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    //数据全部存在stack1中
    public void push(int x) {
            stack1.push(x);
    }
    
    public int pop() {
        //特殊 两者都为空
        if(empty()){
            return -1;
        }
   //先判断空 stack2不为空直接pop 统一从stack2出
     if(stack2.empty()){
      while(!stack1.empty()){
            //将stack1中的元素传到stack2中
            stack2.push(stack1.pop());
        }
     }
     return stack2.pop();
    }
    
    public int peek() {
         //特殊 两者都为空
        if(empty()){
            return -1;
        }
   //先判断空 stack2不为空直接pop 统一从stack2出
     if(stack2.empty()){
      while(!stack1.empty()){
            //将stack1中的元素传到stack2中
            stack2.push(stack1.pop());
        }
     }
     return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.empty() && stack2.empty();
    }
}
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
43
44
45
46
47
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() {
        dumpstackIn();
        return stackOut.pop();
    }
    
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
    private void dumpstackIn() {
        if(!stackOut.isEmpty()) {
            return;
        }
        while(!stackIn.isEmpty()) {
            stackOut.push(stackIn.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();
 */

用队列实现栈

link：225. 用队列实现栈 - 力扣（LeetCode）

思路分析

由于队列是先进先出 想要模拟栈第二个队列就是起到备份的作用.
我们要获取q1最后入列的元素 那么就需要q2中间搭桥：
image-20241025222720745

双队列解决
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
class MyStack {
      Queue<Integer> queue1;
      Queue<Integer> queue2;

    public MyStack() {
      queue1 = new LinkedList<>();
      queue2 = new LinkedList<>();  
    }
    
    public void push(int x) {
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.add(queue1.poll());
            //其实在无容量限制的情况下保持一致使用offer或者add
        }
            Queue<Integer> temp = new LinkedList<>();
            temp = queue1;
            queue1 = queue2;
            queue2 = temp; 
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
      return queue1.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();
 */
Question

在 push 方法中，使用 offer 和 add 都可以将元素插入到 queue2 中，但这两者有细微的区别。下面是解释为什么这里使用了 add 和 offer：

区别

  • **offer(E e)**：用于将元素插入到队列的尾部。如果队列有容量限制（如在阻塞队列中），而队列已满，offer 会返回 false，表示添加失败。
  • **add(E e)**：同样将元素插入到队列的尾部，但如果队列已满（有容量限制时），add 会抛出 IllegalStateException。

在 MyStack 实现中，因为使用的是 LinkedList 作为队列的底层实现，LinkedList 本身没有容量限制，所以在实际操作中 add 和 offer 的行为是相同的。

为什么 push 中既使用了 offer 又使用了 add

  1. offer 用于将新元素 x 加入 queue2。这是因为这个元素是新插入的，并且它是我们希望最终在栈顶部的元素。
  2. add 用于将 queue1 中剩余的所有元素移动到 queue2。在这个上下文中，queue1.poll() 会将 queue1 的元素逐个取出并添加到 queue2。这里使用 add 或 offer 都没有影响，因为 LinkedList 没有容量限制。
单队列解决

其实最开始思考用队列实现栈把末尾入队的元素放到队头即可 但是没有对知识点进行清晰的掌握 下附妙招.
Deque继承了Queue接口
Queue 中的 add、poll、peek等效于 Deque 中的 addLast、pollFirst、peekFirst

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
43
class MyStack {
    Deque<Integer> que1;
 
    public MyStack() {
        que1 = new ArrayDeque<>();
 
    }
    
    public void push(int x) {
        que1.addLast(x);
 
    }
    
    public int pop() {
        int tmp = que1.size()-1;
        while(tmp>0)
        {
            que1.addLast(que1.peekFirst());
            que1.pollFirst();
            tmp--;
        }
        return que1.pollFirst();
 
    }
    
    public int top() {
        return que1.peekLast();
 
    }
    
    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();
 */