经典面试题，两栈实现队列以及两队列实现栈

经典面试题，两个栈实现一个队列，以及两个队列实现一个栈。
1、两个栈实现一个队列
（1）思路：两个stack1，stack2，用stack1存放入队列的数据（入队操作）；stack2负责出队列的数据，若stack2中有数据就直接出栈，否则把stack1中的数据弹出到stack2中，这样stack1中底部的数就到了stack2中的顶部，这样再弹出stack2中的数据即可（出队操作）。
（2）示例图

（3）代码：

 public class Main {
    	Stack<Integer> stack1=new Stack<Integer>();
    	Stack<Integer> stack2=new Stack<Integer>();
    	/******************
        * 两栈实现一个队列，添加操作
        * 只向栈1中添加数据
        * @param data
        */
        public void offerqueue(int data) {
            stack1.push(data);
            return;
        }
        
        /****************
		 * 两栈实现一个队列，出队列操作
		 * 首先判断栈2是否为空，不为空直接出栈2
		 * 若栈2为空，栈1数据全部出栈到栈2，再出栈栈2
		 * @return
		 */
        public int pollqueue() throws Exception{
			if(stack1.isEmpty()&&stack2.isEmpty()) {
				throw new Exception("队列为空");
			}
			if(!stack2.isEmpty()) {
				return stack2.pop();
			}
			while(!stack1.isEmpty()) {
				stack2.push(stack1.pop());
			}
			return stack2.pop();
		}
}
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

2、两个队列实现一个栈
（1）思路：哪个队列不为空就往哪个队列里添加数据进行入栈操作，若都为空默认向queue1中加数据（入栈操作）；把不为空的队列中的数据出队列至另一队列中，直至该不为空的队列只剩下最后一个数时即为最后进来的数据，此时出队列此数据即可（出栈操作）。
（2）示例图

（3）代码：

public class Main {
	Queue<Integer> queue1=new LinkedList<Integer>();
	Queue<Integer> queue2=new LinkedList<Integer>();
	
	/***************
	 * 两队列实现栈，添加操作
	 * 向不为空的队列里添加数据，默认为队列1
	 * @param data
	 */
	public void pushStack(int data) {
		//默认放到queue1中
		if(queue1.isEmpty()&&queue2.isEmpty()) {
			queue1.offer(data);
			return;
		}
		else if(!queue1.isEmpty()) {
			queue1.offer(data);
			return;
		}
		else {
			queue2.offer(data);
			return;
		}
	}
	/***************
	 * 两队列实现栈，出栈操作
	 * 先把不为空的队列出队列到另一队列中直到只剩下一个元素时，执行该队出队列操作
	 * @return
	 */
	public int popStack() throws Exception{
		if(queue1.isEmpty()&&queue2.isEmpty()) {
			throw new Exception("栈为空");
		}
		if(!queue1.isEmpty()) {
			for(int i=0;i<queue1.size()-1;i++) {
				queue2.offer(queue1.poll());
			}
			return queue1.poll();
		}
		else {
			for(int i=0;i<queue2.size()-1;i++) {
				queue1.offer(queue2.poll());
			}
			return queue2.poll();
		}
	}
}
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