用两个栈实现队列

题目链接

维护两个栈stackIn和stackOut;stackIn支持插入操作,stackOut支持删除操作
根据栈先进后出的特性,我们每次往stackIn里插入元素时,stackIn的底部元素就是最后插入的元素;顶部就是下一次待删除的元素.
再执行删除操作时,我们先检查一下stackOut和stackIn是否全部为空.如果为空我们就return -1;如果不为空单独判断stackOut是否为空,不为空直接弹出元素即可;如果为空我们将stackIn里面的元素一个个弹出插入到stackOut里面,这样stackOut元素就是待删除元素的顺序(相当于duistackIn做了一次反转);删除的时候直接弹出stackOut的元素便可

class CQueue {
    Stack stackIn;
    Stack stackOut;

    public CQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

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

    public int deleteHead() {
        if (stackIn.isEmpty() && stackOut.isEmpty()) {
            return -1;
        }
        if (!stackOut.isEmpty()) {
            return stackOut.pop();
        }
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
        return stackOut.pop();
    }
}

type CQueue struct {
	stackIn, stackOut *list.List
}

func Constructor() CQueue {
	return CQueue{
		stackIn:  list.New(),
		stackOut: list.New(),
	}
}

func (this *CQueue) AppendTail(value int) {
	this.stackIn.PushBack(value)
}

func (this *CQueue) DeleteHead() int {
	if this.stackOut.Len() == 0 && this.stackIn.Len() == 0 {
		return -1
	}
	if this.stackOut.Len() == 0 {
		for this.stackIn.Len() > 0 {
			this.stackOut.PushBack(this.stackIn.Remove(this.stackIn.Back()))
		}
	}
	res := this.stackOut.Back()
	this.stackOut.Remove(res)
	return res.Value.(int)
}