剑指offer09. 用两个栈实现队列

题目描述

传送门
https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

解题思路

这里还是不建议使用stack，使用LinkedList代替，由于Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。 可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。 但是我的意思不是像100%代码那样直接使用一个LinkedList当做队列，那确实是快，但是不符题意。加上LinkedList本身作为双链表，可以使用addFirst()、addLast()等操作在不同位置上进行添加和删除操作。这里使用两个栈，一个用来接受的，在后面去除元素的时候，将第一个栈的元素压入第二个中，然后再从顶端进行返回。

代码

class CQueue {
    LinkedList<Integer> stack1;
     LinkedList<Integer> stack2;
    public CQueue() {
        stack1=new LinkedList<Integer>();
        stack2=new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.addLast(value);
    }
    
    public int deleteHead() {
        if(stack2.isEmpty()){
            if(stack1.isEmpty()){
                return -1;
            }
            while(!stack1.isEmpty()){
                stack2.addLast(stack1.removeLast());
            }
            return stack2.removeLast();//注意这里要添加返回值，if-else中很容易出现这种漏掉返回值的问题
        }
        else 
             return stack2.removeLast();
    }

}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */