两个栈实现队列

例题：https://leetcode-cn.com/problems/implement-queue-using-stacks/

创建一个入队栈enQueue，一个出队栈deQueue。入队时，让元素入 入队栈；出队时，入队栈元素先出栈到出队栈，在将出队栈元素出栈，从而实现出队。相当于是队首元素 先入 到入队栈，然后从入队栈后出且后入到出队栈，在从出队栈 先出 出栈（出队），从而实现先入先出的队列。

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 MyQueue {
    Stack<Integer> enQueue; //入队栈
    Stack<Integer> deQueue; //出队栈
    int front; // 出队栈为空时的队首

    public MyQueue() {
        enQueue = new Stack<>();
        deQueue = new Stack<>();
    }
    
    public void push(int x) {
        // 入队栈为空时入队，标记此时的入队元素（栈底，不一定是队首，要看出队栈是否有元素）
        if(enQueue.empty()){
            front = x;
        }
        enQueue.push(x);
    }
    
    public int pop() {
        // 只能在出队栈实现出队
        if(deQueue.empty()){
            while(!enQueue.empty()){
                deQueue.push(enQueue.pop());
            }
        }
        return deQueue.pop();
    }
    
    public int peek() {
       // 出队栈为空时，队首为标记的入队栈栈底front；否则队首为出队栈栈首
        if(deQueue.empty()){
            return front;
        }
        return deQueue.peek();
    }
    
    public boolean empty() {
        if(deQueue.empty() && enQueue.empty()){
            return true;
        }
        return false;
    }
}
我最初的实现

想法： 入队栈和出队栈始终有一个栈为空，另一个栈存放着队内所有元素。易懂一些，但最坏情况下比题解多走两个循环

多走的两个循环如下

  1. 入栈时若入队栈为空，则会把出队栈的元素全部出栈到入队栈再入队。
  2. 取队首元素时，若出队栈为空，则会把入队栈元素全部出栈到出队栈再取队首元素。

优化后的实现与我最初的实现差别如下（从优化后的角度来比较）

  1. 相同处：出队时，出队栈不能为空，若为空要把入队栈出栈到出队栈。
  2. 不同处：入队时，入队栈可以为空。
    • 若出队栈内有元素时，把出队栈栈首当成队首即可，入队时直接把元素放进入队栈，若入队栈空则标记此时入队栈的栈首front（为了让出队栈全部出栈后，能获取此时入队栈的栈底元素。出队栈有元素时，front不是队首）
    • 获取队首元素时，出队栈有元素则获取出队栈栈首；出队栈无元素时，则获取之前在入队栈标记的front（栈底、队首）。
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 {
    Stack<Integer> enQueue; //入队栈
    Stack<Integer> deQueue; //出队栈

    public MyQueue() {
        enQueue = new Stack<>();
        deQueue = new Stack<>();
    }
    
    public void push(int x) {
        //确保元素在入队栈，再入队
        if(enQueue.empty()){
            while(!deQueue.empty()){
                enQueue.push(deQueue.pop());
            }
        }
        enQueue.push(x);
    }
    
    public int pop() {
        //确保元素在出队栈，再出队
        if(deQueue.empty()){
            while(!enQueue.empty()){
                deQueue.push(enQueue.pop());
            }
        }
        return deQueue.pop();
    }
    
    public int peek() {
        //确保元素在出队栈，在取队首元素
        if(deQueue.empty()){
            while(!enQueue.empty()){
                deQueue.push(enQueue.pop());
            }
        }
        return deQueue.peek();
    }
    
    public boolean empty() {
        if(deQueue.empty() && enQueue.empty()){
            return true;
        }
        return false;
    }
}

队列实现栈

例题：https://leetcode-cn.com/problems/implement-stack-using-queues/

一个队列

思路： 每次入队后，循环队内元素，让刚入队之前的元素全都移到该元素之后。此时队首到队尾即为栈顶到栈底

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
class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new ArrayDeque<>();
    }
    
    public void push(int x) {
        queue.offer(x);
        int size = queue.size();
        for(int i = 0; i < size - 1; i++){
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        if(queue.isEmpty()){
            return true;
        }
        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

class MyStack {
    Queue<Integer> queue1; //最终存放着栈元素的队列
    Queue<Integer> queue2; //辅助队列

    public MyStack() {
        queue1 = new ArrayDeque<>();
        queue2 = new ArrayDeque<>();
    }
    
    public void push(int x) {
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> tmp = queue1;
        queue1 = queue2;
        queue2 = tmp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();

    }
    
    public boolean empty() {
        if(queue1.isEmpty()){
            return true;
        }
        return false;

    }
}