题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：["CQueue","appendTail","deleteHead","deleteHead"][[],[3],[],[]]输出：[null,null,3,-1]示例 2：输入：["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"][[],[],[5],[2],[],[]]输出：[null,-1,null,null,5,2]提示：
  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

我的答案

class CQueue {    Stack stk1,stk2;    int  size;    public CQueue() {        //初始化         stk1 = new Stack();         stk2 = new Stack();         size =0;    }    public void appendTail(int value) {        //插入前先将栈1的全部移到栈2里面        while(!stk1.isEmpty()){            stk2.push(stk1.pop());        }        //插入元素放入到栈1        stk1.push(value);        //将插入的元素再从栈2移回去栈1        while(!stk2.isEmpty()){            stk1.push(stk2.pop());        }        size ++;    }    public int deleteHead() {        //直接弹出栈1        if(size==0) return -1;          int res = stk1.pop();        size --;        return res;    }}/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

  • 补充栈相关
    		Modifier and TypeMethod and Description
    booleanempty() Tests if this stack is empty.
    Epeek() Looks at the object at the top of this stack without removing it from the stack.
    Epop() Removes the object at the top of this stack and returns that object as the value of this function.
    Epush(E item) Pushes an item onto the top of this stack.
    intsearch(Object o) Returns the 1-based position where an object is on this stack.
    Modifier and TypeMethod and Description
    booleanempty() 测试此堆栈是否为空。
    Epeek() 查看此堆栈顶部的对象，而不从堆栈中删除它。
    Epop() 删除此堆栈顶部的对象，并将该对象作为此函数的值返回。
    Epush(E item) 将项目推送到此堆栈的顶部。
    intsearch(Object o) 返回一个对象在此堆栈上的基于1的位置。

精彩答案

使用java的同学请注意，如果你使用Stack的方式来做这道题，会造成速度较慢； 原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。 可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。 但是我的意思不是像100%代码那样直接使用一个LinkedList当做队列，那确实是快，但是不符题意。 贴上代码，这样的优化之后，效率提高了40%，超过97%。
class CQueue {        LinkedList stack1;    LinkedList stack2;    public CQueue() {        stack1 = new LinkedList<>();        stack2 = new LinkedList<>();    }    public void appendTail(int value) {        stack1.add(value);    }    public int deleteHead() {        if (stack2.isEmpty()) {            if (stack1.isEmpty()) return -1;            while (!stack1.isEmpty()) {                stack2.add(stack1.pop());            }            return stack2.pop();        } else return stack2.pop();    }}