队列如何在买入/看跌期权上提供 O(1) 性能?

Question

我假设接受/看跌期权的恒定时间性能是通过允许消费者和生产者访问队列的尾部/头部而不相互锁定来实现的。 如何为内存中队列实现此目的？持久队列的答案是否会更改(可能(？ 在对生产者和消费者各限制为1的系统中如何解决这个问题？ 当系统允许并发访问时怎么样？

Answer 1

Queue使用双向链表作为数据结构。事实上，Java 中的队列是这样声明的：

Queue<SomeClass> q = new LinkedList<>();

默认情况下，Java 中的LinkedList是双向链表。

现在，头部的offer()或插入始终是O(1)，因为您不需要遍历整个列表，并且与删除尾巴并返回poll()相同。

现在就并发访问而言，它应该不会对代码的时间复杂度产生任何影响。