数据结构和算法之两个栈实现队列

思路

第一个栈只负责写入。有新数据写入就一直写入第一个栈。当读取数据时候，判断第二个栈是否有数据，如果有直接弹出栈顶元素；如果没有数据，将第一个栈的数据依次弹出，然后按照顺序写入第二个栈，最终弹出第二个栈顶元素。

直接上Java代码：

import java.util.Stack; /** * 两个栈实现队列 * Author:BlueSky */ public class TwoStack4Queue { /** * 写入栈 */ private Stack<Integer> input = new Stack(); /** * 读取栈 */ private Stack<Integer> output = new Stack(); private void add(Integer data){ input.push(data); } private Integer pop(){ // 是空的 需要将 input 出栈写入 out if(output.empty()){ while (!input.empty()){ output.push(input.pop()); } } // 不为空时直接移除出栈就表示移除了头结点 return output.pop(); } public int getSize(){ return input.size() + output.size(); } }