问题
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路
将入队的元素，加入stack1，如果有出队操作，则将stack1中的元素依次压入stack2，从stack2中弹出元素就等于出队操作，直到从stack2中弹出所有元素，则才又从stack1中加入元素。
package offer007; import java.util.Stack; /** * @Title: CQueue.java * @Package: offer007 * @Description 两个栈实现一个队列 * @author Han * @date 2016-4-17 上午11:24:17 * @version V1.0 * @param <T> */ public class CQueue<T> { /** * 第一个栈：用于存放输入队列的元素 */ private Stack<T> stack1; /** * 第二个栈：用于存放输出队列的元素 */ private Stack<T> stack2; public CQueue() { stack1 = new Stack<T>(); stack2 = new Stack<T>(); } /** * @Description 输入队列 * @author Han * @param item * @return */ public T push(T item){ stack1.push(item); return item; } /** * @Description 输出对头元素 * @author Han * @return */ public T pop(){ /** * 堆栈2中没有元素 */ if (stack2.size() <= 0){ /** * 将堆栈1中的元素压入堆栈2 */ while(stack1.size() > 0){ stack2.push(stack1.pop()); } } if(stack2.size() <= 0){ throw new RuntimeException("The Queue Is Empty!!"); } /** * 弹出堆栈2的头元素 */ return stack2.pop(); } }
测试
@Test public void testCQueue() throws Exception { CQueue<Integer> queue = new CQueue<Integer>(); try { queue.push(3); queue.push(4); System.out.println(queue.pop()); System.out.println(queue.pop()); System.out.println(queue.pop()); queue.push(4); queue.push(5); System.out.println(queue.pop()); System.out.println(queue.pop()); } catch (Exception e) { System.out.println(e.getMessage()); } }
结果
扩展
用两个队列来实现栈
思路
入栈操作时，哪个队列为空，则将哪个元素加入空队列，出栈操作时，将queue1中的元素（除了队尾元素）依次加入queue2中，并将queue1队尾元素当成栈顶元素弹出，下次出栈，又将queue2中的元素（除了队尾元素）依次加入queue1中，并将queue2队尾元素当成栈顶元素弹出。
package offer007; import java.util.LinkedList; import java.util.Queue; /** * @Title: CStack.java * @Package: offer007 * @Description 使用两个队列实现栈 * @author Han * @date 2016-4-17 下午2:35:38 * @version V1.0 */ public class CStack<T> { /** * 队列一 */ private Queue<T> queue1; /** * 队列二 */ private Queue<T> queue2; public CStack() { queue1 = new LinkedList<T>(); queue2 = new LinkedList<T>(); } /** * @Description 向栈内压入元素 * @author Han * @param item * @return */ public T push(T item){ /** * 如果队列一为空，则向队列二中添加元素 */ if(queue1.size() == 0){ queue2.offer(item); }else{ queue1.offer(item); } return item; } /** * @Description 将栈顶元素弹出 * @author Han * @return */ public T pop(){ /** * 哪个队列不为空，则把哪个队列中作为output队列，另一个作为input队列 */ if(queue1.size() != 0){ return getTop(queue1, queue2); }else if(queue2.size() != 0){ return getTop(queue2, queue1); } throw new RuntimeException("栈顶无元素！！"); } /** * @Description 得到栈顶元素 * @author Han * @param output * @param input * @return */ private T getTop(Queue<T> output, Queue<T> input) { /** * 将output队列（除队尾元素）依次加入input队列，并将队尾元素当成栈顶元素返回 */ while(output.size() != 1){ input.offer(output.poll()); } return output.poll(); } }
测试
@Test public void testCStack() throws Exception { CStack<Integer> queue = new CStack<Integer>(); try { queue.push(3); queue.push(4); System.out.println(queue.pop()); System.out.println(queue.pop()); queue.push(4); queue.push(5); System.out.println(queue.pop()); System.out.println(queue.pop()); System.out.println(queue.pop()); } catch (Exception e) { System.out.println(e.getMessage()); } }
结果
总结
清楚知道关于队列（FIFO）和栈（LIFO）的相关特点。