使用堆栈作为底层数据结构的具有队列和脱队列的并发队列

Question

这是一个混合数据结构和多线程概念的问题。(这只是为了理解和学习的目的)解决方案的语言: Java

具有FIFO行为的队列需要通过底层数据结构作为堆栈来实现。Enqueue和Dequeue需要是并行的，不需要彼此阻塞，也就是说，队列线程不能等待去队列线程。

在我的搜索过程中(基于java的解决方案)，我只能找到这个问题的阻塞版本，其中enqueue和dequeue是相互阻塞的。

下面是我的尝试，如果我错了，请纠正我，以防我漏掉了什么。

1. 两个堆栈:带有单独锁对象的addStack和removeStack、addLock和removeLock
2. Enqueue操作:在addLock上的同步块中排队，一旦添加了项，就在addLock上调用notifyAll
3. Dequeue操作:如果removeStack为空，则检查addStack是否为空，如果不为空，则弹出来自addStack的所有元素并将其推送到removeStack
4. 从removeStack弹出元素并返回

下面是java代码：

import java.util.Stack;

/**
 * Queue Implementation with Stack as underlying data-structure and with
 * parallel (almost) enqueue and dequeue
 * 
 * @author krishna_k
 *
 */
public class Queue {

    private Stack addStack = new Stack<>();
    private Stack removeStack = new Stack<>();
    private final Object addLock = new Object();
    private final Object removeLock = new Object();

    public void enqueue(int item) {
        synchronized (addLock) {
            addStack.push(item);
            addLock.notifyAll();
        }
    }

    public int dequeue(){
        int value = 0;
        synchronized (removeLock) {
            if (removeStack.isEmpty()) {
                try {
                    synchronized (addLock) {
                        while (addStack.isEmpty()) {
                            addLock.wait();
                        }
                        while (!addStack.isEmpty()) {
                            removeStack.push(addStack.pop());
                        }
                    }
                }catch(InterruptedException e) {
                    //code to log the exception e
                }
            }
            value = removeStack.pop();
        }
        return value;
    }
}

Answer 1