个人博客

两个栈实现队列和两个队列实现栈

2021/4/20 算法

作者：duktig

博客：http://duktig.cn/ (opens new window)

优秀还努力。愿你付出甘之如饴，所得归于欢喜。

源码：https://github.com/duktig666/algorithm (opens new window)

# 用两个栈实现队列

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。

源码参看：https://github.com/duktig666/algorithm/blob/main/src/datastructure/queue/impl/StackQueue.java (opens new window)

# 思路

新元素进栈1

弹出元素时，分为两种情况：

  1. 当stack2栈为空时，我们把stack1栈的元素逐个弹出并压入stack2栈，此时我们会发现最先进入的元素已经在stack2栈顶，可以直接弹出；
  2. 当stack2栈不为空，在stack2中的栈顶元素就是最先进入队列的元素，可以弹出。

用两个栈模拟队列操作

# 代码实现

队列接口

public interface Queue<E> {

    /**
     * @return 是否队空
     */
    boolean isEmpty();


    /**
     * @return 队列元素个数
     */
    int getSize();

    /**
     * 队尾入队
     *
     * @param e 入队元素
     */
    void add(E e);

    /**
     * 队首出队
     *
     * @return 出队元素
     */
    E poll();

    /**
     * 获取队首元素
     *
     * @return 队首元素
     */
    E getHead();

}
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

实现

public class StackQueue<E> implements Queue<E> {

    private Stack<E> stack1;
    private Stack<E> stack2;

    public StackQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /**
     * @return 是否队空
     */
    @Override
    public boolean isEmpty() {
        return stack1.empty() && stack2.empty();
    }

    /**
     * @return 队列元素个数
     */
    @Override
    public int getSize() {
        return stack1.size() + stack2.size();
    }

    /**
     * 入队：只考虑将元素添加至stack1
     *
     * @param e 入队元素
     */
    @Override
    public void add(E e) {
        stack1.push(e);
    }

    /**
     * 出队：
     * 若stack2为空，将stack1元素依次出栈，并压栈进stack2；stack2弹出栈顶元素
     * 若stack2不为空，直接弹出栈顶元素
     *
     * @return 出队元素
     */
    @Override
    public E poll() {
        if (stack1.empty() && stack2.empty()) {
            throw new RuntimeException("Queue is null.Don't delete!");
        }
        if (stack2.empty()) {
            while (! stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    /**
     * 获取队首元素
     *
     * @return 队首元素
     */
    @Override
    public E getHead() {
        if (stack1.empty() && stack2.empty()) {
            throw new RuntimeException("Queue is null.Don't delete!");
        }
        if (stack2.empty()) {
            while (! stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    /**
     * 先输出stack2再输出stack1
     * 顺序stack2+逆序stack1即为队列元素顺序
     */
    public String toStringForStack() {
        StringBuilder sb = new StringBuilder();
        sb.append("Stack2 TOP:");
        for (E value : stack2) {
            sb.append(value).append(" ");
        }
        sb.append("\nStack1 TOP:");
        for (E value : stack1) {
            sb.append(value).append(" ");
        }
        return sb.toString();
    }

    /**
     * 输出队列的元素
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Queue TOP:");
        for (E value : stack2) {
            sb.append(value).append(" ");
        }
        Stack<E> stackTemp = new Stack<>();
        for (E value : stack1) {
            stackTemp.push(value);
        }
        for (E value : stackTemp) {
            sb.append(value).append(" ");
        }
        return sb.toString();
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        StackQueue<Integer> queue = new StackQueue<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);

        System.out.println(queue.toStringForStack());
        System.out.println("出队：" + queue.poll());
        System.out.println(queue.toStringForStack());

        queue.add(4);

        System.out.println(queue.toStringForStack());
        System.out.println("出队：" + queue.poll());
        System.out.println(queue.toStringForStack());

        System.out.println(queue);
    }

}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

测试结果：

Stack2 TOP:
Stack1 TOP:1 2 3 
出队：1
Stack2 TOP:3 2 
Stack1 TOP:
Stack2 TOP:3 2 
Stack1 TOP:4 
出队：2
Stack2 TOP:3 
Stack1 TOP:4 
Queue TOP:3 4
1
2
3
4
5
6
7
8
9
10
11

# 两个队列实现栈

源码参看：https://github.com/duktig666/algorithm/blob/main/src/datastructure/stack/impl/QueueStack.java (opens new window)

# 思路

  • 插入时，插入有元素的队列尾端
  • 出栈时，将不为空的队列元素，依次出栈到另一个为空的队列，直至不为空的队列只剩下一个元素，将这个元素出栈即可。

用两个队列模拟一个栈的操作

# 实现

栈接口

public interface Stack<E> {

    /**
     * @return 获取栈的大小
     */
    int getSize();

    /**
     * @return 判断栈是否为空
     */
    boolean isEmpty();

    /**
     * 向栈中添加一个元素(入栈)
     *
     * @param e 添加的元素
     */
    void push(E e);

    /**
     * 在栈中删除一个元素（出栈）
     *
     * @return 出栈的元素
     */
    E pop();

    /**
     * @return 返回栈最顶层的元素
     */
    E peek();
}
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

实现

public class QueueStack<E> implements Stack<E> {

    private Queue<E> queue1;
    private Queue<E> queue2;

    public QueueStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /**
     * @return 获取栈的大小
     */
    @Override
    public int getSize() {
        return queue1.size() + queue2.size();
    }

    /**
     * @return 判断栈是否为空
     */
    @Override
    public boolean isEmpty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }

    /**
     * 入队：元素添加至不是空的队列当中，两个都是null无所谓
     *
     * @param e 入队元素
     */
    @Override
    public void push(E e) {
        if (queue2.isEmpty()) {
            queue1.add(e);
        } else {
            queue2.add(e);
        }
    }

    /**
     * 出队：将不为null的队列元素出队，并入队到另一个队列当中，最后剩下的那个即为该出队的元素
     *
     * @return 出队元素
     */
    @Override
    public E pop() {
        if (queue1.isEmpty() && queue2.isEmpty()) {
            throw new IllegalArgumentException("Remove failed. Stack is empty!");
        } else if (queue1.isEmpty()) {
            while (queue2.size() > 1) {
                queue1.add(queue2.poll());
            }
            return queue2.poll();
        } else {
            while (queue1.size() > 1) {
                queue2.add(queue1.poll());
            }
            return queue1.poll();
        }
    }

    /**
     * @return 返回栈最顶层的元素
     */
    @Override
    public E peek() {
        if (queue1.isEmpty() && queue2.isEmpty()) {
            throw new IllegalArgumentException("Remove failed. Stack is empty!");
        }
        Queue<E> queueTemp = new LinkedList<>();
        if (! queue1.isEmpty()) {
            copy(queueTemp, queue1);
        } else {
            copy(queueTemp, queue2);
        }
        while (queueTemp.size() > 1) {
            queueTemp.poll();
        }
        return queueTemp.poll();
    }

    /**
     * 队列拷贝
     *
     * @param target 目标队列
     * @param src    源队列
     */
    private void copy(Queue<E> target, Queue<E> src) {
        while (! src.isEmpty()) {
            target.add(src.poll());
        }
    }

    /**
     * 输出两个栈的情况
     */
    public String toStringForQueue() {
        StringBuilder sb = new StringBuilder();
        sb.append("Queue1 TOP:");
        for (E value : queue1) {
            sb.append(value).append(" ");
        }
        sb.append("\nQueue2 TOP:");
        for (E value : queue2) {
            sb.append(value).append(" ");
        }
        return sb.toString();
    }

    /**
     * 输出栈的元素
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        for (E value : queue1) {
            sb.append(value).append(" ");
        }
        for (E value : queue2) {
            sb.append(value).append(" ");
        }
        sb.append("] Stack TOP");
        return sb.toString();
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        QueueStack<Integer> stack = new QueueStack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.toStringForQueue());
        System.out.println("出栈：" + stack.pop());
        System.out.println(stack.toStringForQueue());

        System.out.println("添加元素");
        stack.push(4);

        System.out.println(stack.toStringForQueue());
        System.out.println("出栈：" + stack.pop());
        System.out.println(stack.toStringForQueue());

        System.out.println(stack);

        System.out.println("栈顶：" + stack.peek());

    }

}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

测试结果

Queue1 TOP:1 2 3 
Queue2 TOP:
出栈：3
Queue1 TOP:
Queue2 TOP:1 2 
添加元素
Queue1 TOP:
Queue2 TOP:1 2 4 
出栈：4
Queue1 TOP:1 2 
Queue2 TOP:
[ 1 2 ] Stack TOP
栈顶：2
1
2
3
4
5
6
7
8
9
10
11
12
13