题目描述

题解

栈

Java底层是用vector实现栈结构的, 但是而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。

栈结构的特点是先入后出, 而队列结构特点是先入先出, 这里提示使用两个栈结构实现队列, 很明显要通过其中一个栈来起到逆序的作用.

在脑海中简单模拟一下, 将不同的整数放入第一个栈, 如果要删除头节点, 肯定要把栈1中的所有元素都弹入到栈2中, 此时的栈2就是逆序的, 依次弹出栈顶即可.

所以整个算法流程为:

appendTail:

把新的元素压入栈1中.

deleteHead:

如果当前栈2不为空, 则弹出当前栈2的栈顶元素
如果栈2为空:
- 如果栈1也为空, 说明队列中没有元素, 直接返回-1
- 如果栈1不为空, 将栈1中的所有元素全部弹入栈2, 并弹出栈2的栈顶元素

class CQueue {
    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;

    public CQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

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

    public int deleteHead() {
        if (stack2.isEmpty()){
            if (stack1.isEmpty()){
                return -1;
            }else {
                while (!stack1.isEmpty()){
                    stack2.addLast(stack1.removeLast());
                }
                return stack2.removeLast();
            }
        }else {
            return stack2.removeLast();
        }
}