数据机构与算法|剑指offer.09.用两个栈实现队列链表|算法|java|队列|数据结构

用两个栈实现队列

前言
一、链表中size的问题
- 1、代码问题
- 2、思想优化
- 3、优化后的代码
- 4、总结

【数据机构与算法|剑指offer.09.用两个栈实现队列】
前言

在for循环中使用链表的size()，而在循环体中对链表进行增加和删除，这是会动态的影响for循环中size()的大小。

一、链表中size的问题 1、代码问题

class CQueue {LinkedList l1; LinkedList l2; public CQueue() {l1 = new LinkedList<>(); l2 = new LinkedList<>(); }public void appendTail(int value) {l1.push(value); }public int deleteHead() {if(l1.size() == 0) return -1; for(int i = 0; i < l1.size() - 1; i++){l2.push(l1.pop()); } int param = l1.pop(); for(int i = 0; i < l2.size(); i++){l1.push(l2.pop()); } return param; } }

其中的for(int i = 0; i < l1.size() - 1; i++)语句中，由于循环体中不断在pop()操作，所以l1.size()并不是一个固定的值。这会导致程序得到错误的结果。

2、思想优化

上面除了for循环的代码有错，其实思想也是不高效的。对于两个栈，就有两栈头可以操作，刚好对应两端受限的线性表—队列的队尾和队首。
更新后的思想：
把栈1的顶端拿来作为队列的队尾，有入队的功能；把栈2的顶端拿来作为队列的队首，有出队的功能。
1）看栈1和栈2是否同时为空，若为空，则返回-1。
2）若1）不成立，则考虑栈2是否为空，若为空，则将栈1的值push到栈2中；若不为空，则将栈2的顶端元素出栈。

3、优化后的代码

class CQueue {LinkedList l1; LinkedList l2; public CQueue() {l1 = new LinkedList<>(); l2 = new LinkedList<>(); }public void appendTail(int value) {l1.push(value); }public int deleteHead() {if (l1.isEmpty() && l2.isEmpty()) return -1; if(l2.isEmpty()){while(!l1.isEmpty()){l2.push(l1.pop()); } } return l2.pop(); } }