剑指offer第一题

剑指offer第一题

用两个栈实现队列

---

文章目录

• 剑指offer第一题
• 前言
• 一、自己的解法
• • • 代码
• 二、评论解法
• 总结

---

前言

再次开始刷题

一、自己的解法

执行用时：667 ms, 在所有 Java 提交中击败了8.43%的用户
内存消耗：49.4 MB, 在所有 Java 提交中击败了9.24%的用户
思路就是创建栈s1和s2，插入时数据全放到s1中，删除是数据全放到s2中。

代码

class CQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;

    public CQueue() {
        s1 = new Stack();
        s2 = new Stack();
    }
    
    public void appendTail(int value) {
        if(s2.empty()){
            s1.push(value);
        } else {
            while(!s2.empty()){
                int num = s2.pop();
                s1.push(num);
            }
            s1.push(value);
        }
    }
    
    public int deleteHead() {
        if(!s2.empty()){
            return s2.pop();
        }
        if(s2.empty() && !s1.empty()){
            while(!s1.empty()){
                int num = s1.pop();
                s2.push(num);
            }
            return s2.pop();
        }
        return -1;
        
    }
}

二、评论解法

//使用LinkedList，因为LinkedList实现了Deque接口，
//所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。
//使用Stack的方式来做这道题，会造成速度较慢； 原因的话是Stack继承了
//Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了
    LinkedList<Integer> stack1;
	LinkedList<Integer> 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();
	}

总结

对Deque和Vector可能还得再了解下