栈与队列

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型.

思路

假设两个栈为A和B。

1. 入队列的时候，只需要向A栈中入栈即可。
2. 出队列的时候，要先检查B栈是否为空。如果B为空，把A栈中的元素全部放入B栈中。如果B不为空，就从B栈顶弹出一个元素。
   这样就实现了一个队列先进先出的功能。

代码实现

/**
 * 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 
 * <分析>： 
 * 入队：将元素进栈A
 * 出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈； 如果不为空，栈B直接出栈。
 * 
 * @author XIAO
 *
 */
import java.util.Stack;

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

	public void push(int node) {
		stack1.push(node);
	}

	public int pop() {
		int a;
		if (!stack2.isEmpty()) {
			a = stack2.pop();
		} else {
			while (!stack1.isEmpty()) {
				stack2.push(stack1.pop());
			}
			a = stack2.pop();
		}
		return a;
	}
}

题目描述

用两个队列实现栈的功能。

思路

把B当做一个中转站
入栈：将元素进队列A
出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素出队列并放入队列B，直到队列A中的元素留下一个，然
后队列A出队列，再把队列B中的元素出队列以此放入队列A中。

代码

/**
 * 用两个队列实现栈的功能； 思路 <分析>：把B当做一个中转站 入栈：将元素进队列A
 * 出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素出队列并放入队列B，直到队列A中的元素留下一
 * 个，然后队列A出队列，再把 队列B中的元素出队列以此放入队列A中。
 * 
 * @author XIAO
 *
 */
public class QueueStack {
	Queue<Integer> queue1 = new ArrayDeque<>();
	Queue<Integer> queue2 = new ArrayDeque<>();

	public void push(int node) {
		// 两个栈都为空时，优先考虑queue1
		if (queue1.isEmpty() && queue2.isEmpty()) {
			queue1.add(node);
			return;
		}

		// 如果queue1为空，queue2有元素，直接放入queue2
		if (queue1.isEmpty()) {
			queue2.add(node);
			return;
		}

		if (queue2.isEmpty()) {
			queue1.add(node);
			return;
		}

	}

	public int pop() {
		// 两个栈都为空时，没有元素可以弹出
		if (queue1.isEmpty() && queue2.isEmpty()) {
			try {
				throw new Exception("stack is empty");
			} catch (Exception e) {
			}
		}
		// 如果queue1为空，queue2有元素， 将queue2的元素依次放入queue1中，直到最后一个元素，我们弹出。
		if (queue1.isEmpty()) {
			while (queue2.size() > 1) {
				queue1.add(queue2.poll());
			}
			return queue2.poll();
		}

		if (queue2.isEmpty()) {
			while (queue1.size() > 1) {
				queue2.add(queue1.poll());
			}
			return queue1.poll();
		}

		return (Integer) null;
	}
}