05.用两个栈实现队列

一、题目

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail 和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。

二、解题思路

栈1用于存储元素,栈2用于弹出元素,负负得正。

说的通俗一点,现在把数据1、2、3分别入栈一,然后从栈一中出来(3、2、1),放到栈二中,那么,从栈二中出来的数据(1、2、3)就符合队列的规律了,即负负得正。

三、解题代码

public class Test {  
    public static class MList<T> {  
        // 插入栈,只用于插入的数据  
        private Stack<T> stack1 = new Stack<>();  
        // 弹出栈,只用于弹出数据  
        private Stack<T> stack2 = new Stack<>();  

        public MList() {  
        }  

        // 添加操作,成在队列尾部插入结点  
        public void appendTail(T t) {  
            stack1.add(t);  
        }  

        // 删除操作,在队列头部删除结点  
        public T deleteHead() {  

            // 先判断弹出栈是否为空,如果为空就将插入栈的所有数据弹出栈,  
            // 并且将弹出的数据压入弹出栈中  
            if (stack2.isEmpty()) {  
                while (!stack1.isEmpty()) {  
                    stack2.add(stack1.pop());  
                }  
            }  

            // 如果弹出栈中还没有数据就抛出异常  
            if (stack2.isEmpty()) {  
                throw new RuntimeException("No more element.");  
            }  

            // 返回弹出栈的栈顶元素,对应的就是队首元素。  
            return stack2.pop();  
        }  
    }  
}