- 1 package Solution;
- 2 3 import java.util.LinkedList;
- 4 import java.util.Queue;
- 5 6
- /**
- 7 * 剑指offer面试题7相关题目:用两个队列实现一个栈
- 8 * 解题思路:根据栈的先入后出和队列的先入先出的特点
- 9 * 在push的时候,把元素向非空的队列内添加
- 10 * 在pop的时候,把不为空的队列中的size()-1份元素poll出来,添加到另为一个为空的队列中,再把队列中最后的元素poll出来
- 11 * 两个队列在栈不为空的情况下始终是有一个为空,另一个不为空的。push添加元素到非空的队列中,pop把非空队列的元素转移到另一个空的队列中,
- 12 * 直到剩下最后一个元素,这个元素就是要出栈的元素(最后添加到队列中的元素)。
- 13 * @author GL
- 14 *
- 15 */
- 16 public class No7StackWithTwoQueues {
- 17 18 public static void main(String[] args) {
- 19 push(1);
- 20 push(2);
- 21 push(3);
- 22 pop();
- 23 push(4);
- 24 pop();
- 25 pop();
- 26 pop();
- 27 pop();
- 28 29
- }
- 30 31 private static Queue queue1 = new LinkedList();
- 32 private static Queue queue2 = new LinkedList();
- 33 34
- /*
- 35 * 向队列中执行入栈操作时,把元素添加到非空的队列中
- 36 */
- 37 public static void push(Object item) {
- 38
- if (!queue1.isEmpty()) 39 queue1.offer(item);
- 40
- else 41 queue2.offer(item);
- 42 System.out.println("入栈元素为:" + item);
- 43
- }
- 44 45 public static void pop() {
- 46
- if (!isEmpty()) {
- 47
- if (queue1.isEmpty()) {
- 48
- while (queue2.size() > 1) {
- 49 queue1.offer(queue2.poll());
- 50
- }
- 51 System.out.println("出栈元素为:" + queue2.poll());
- 52
- } else {
- 53
- while (queue1.size() > 1) {
- 54 queue2.offer(queue1.poll());
- 55
- }
- 56 System.out.println("出栈元素为:" + queue1.poll());
- 57
- }
- 58
- }
- 59
- else 60
- throw new RuntimeException("栈为空,无法执行出栈操作");
- 61
- }
- 62 63
- /*
- 64 * 检查栈是否为空
- 65 */
- 66 private static boolean isEmpty() {
- 67
- return queue1.isEmpty() && queue2.isEmpty();
- 68
- }
- 69
- }
来源: http://www.bubuko.com/infodetail-1960859.html