Java实现用两个栈实现队列

Java实现用两个栈实现队列

思路：使用stack1来直接存放数据，只有当需要删除数据时才将数据逆序移动到stack2，stack2进行删除。

使用Deque的实现类linkedList，底层是链表，相对于Stack底层是数组来进行添删速度快很多，利用空间换时间。

class CQueue {
    private Deque stack1;
    private Deque stack2;
    public CQueue() {
        stack1 = new linkedList<>();
        stack2 = new linkedList<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        //stack2不为空直接pop出
        if (!stack2.isEmpty()){
            return stack2.pop();
        }else {
            //将stack1的所有元素逆序移动到stack2
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.isEmpty() ? -1 : stack2.pop();
    }
}

测试类：

public class Test {
    public static void main(String[] args) {
        CQueue queue = new CQueue();
        queue.appendTail(1);
        queue.appendTail(2);
        queue.appendTail(3);
        queue.appendTail(5);
        int i = queue.deleteHead();
        System.out.println(i);
    }
}

结果：