有一道LC题找不到了，关于O(1)实现queue的，求助！

LC上题目本身不是关于queue的，好像是用BFS在层遍历树的过程当中的一个问题，因为BFS肯定用到queue嘛。在看这道题的答案的时候看过一个关于用（doubly？）linked list来替代queue本身，从而实现好像是O(1)的space complexity的方法。可惜刷过忘了，找不着是哪一道题了，也没有搜到。求高人指点！

对了，我是c++，那道题的那个答案不是c++就是java。

补充内容 (2018-11-17 13:34):
那个答案里有自己implement的方法叫dequeue和enqueue，好像还有tail和head指针。

你这个描述也太水了，实在看不明白你在写什么。

我试着总结一下你的关键字:
1） 似乎有O1 space complexity 的queue， 或者说实现的queue。
2） 似乎是用了doubly linked list， 而没有用queue
3） 似乎是在level order traversal 的时候用到了
4） doubly linked list的implementation 里面还写了 deque 和 enque， 还有tail 和head
5） queue是FIFO的性质， 所以doubly linked list很类似
6） 我写的是c++， 答案不是c++就是java

请根据以上条件， 猜是哪道lc题目。

是陆贰贰 design circular queue么？

sudalvbulv 发表于 2018-11-17 17:41
是陆贰贰 design circular queue么？

可惜不是……题目本身不是问queue的，是tree bfs traverse过程中要用到queue，某个答案把queue以linked list方式实现了，还是中国人写的答案，提到了queue的FIFO性质用doubly linked list很类似之类的话。

肥宅快乐水 发表于 2018-11-17 23:41
你这个描述也太水了，实在看不明白你在写什么。

我试着总结一下你的关键字:

66666， 差不多是这个意思

补充内容 (2018-11-18 03:13):
补充一下，我记得那个答案里，deque的function那个人定义为dequeue，enque的function，那个人定义为enqueue

肥宅快乐水 发表于 2018-11-17 23:41
你这个描述也太水了，实在看不明白你在写什么。

我试着总结一下你的关键字:

有点儿像这个：
Implementation of Deque using doubly linked list
不太确定是不是完全一样。我问这个问题是因为在考虑这个面经的第一题怎么做：