一、题目
需要实现一个类，使用两个栈实现队列的基本操作，包括add、poll、peek。
二、分析
栈的特性是先入后出，队列的特点是先入先出。所以设计的时候两个栈中，一个负责数据压入，一个负责数据弹出。当数据弹出的时候必须从弹出堆栈中进行统一弹出，同时在数据弹出之前，必须将数据压入堆栈中的数据全部压入弹出堆栈中。因为如果不是全部压入的话，在弹出的过程中就会破坏队列要求的先入先出的顺序。同时当弹出堆栈存在数据的时候不能进行数据压入操作，因为弹出堆栈中已经是上一次数据的压入顺序，如果在此时进行数据的压入也会破坏弹出顺序。
三、代码实现
package com.algorithm; import java.util.Stack; import com.exception.ProgramException; /** * @author taomeng * @Date 2018年9月8日 * @Discription:两个栈实现队列功能 */ public class NewQueue { /** * 数据压入 */ private Stack<Integer> stack1; /** * 数据弹出 */ private Stack<Integer> stack2; public NewQueue() { this.stack1 = new Stack<Integer>(); this.stack2 = new Stack<Integer>(); } /** * * 函数功能描述：队列添加数据 * @date 2018年9月8日下午3:54:18 * @param data void * @author taomeng */ public void add(Integer data) { stack1.push(data); } /** * * 函数功能描述：返回头部元素并移除 * @date 2018年9月8日下午4:21:12 * @return int * @author taomeng */ public int poll() { if (stack1.isEmpty() && stack2.isEmpty()) { throw new ProgramException("queue is empty."); } else if (stack2.isEmpty()) { while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } /** * * 函数功能描述：数据弹出，返回头部元素 * @date 2018年9月8日下午4:44:12 * @return int * @author taomeng */ public int peek() { if (stack1.isEmpty() && stack2.isEmpty()) { throw new ProgramException("queue is empty."); } else if (stack2.isEmpty()) { while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.peek(); } }
