Review request: Thread safe queue (parallel push pop)

Question

Here is an implementation of a thread safe queue. The push and pop won't block each other. However, pop will wait until an item is pushed, if the queue is empty. Multiple producers and consumers can use the queue. Please tell me if you see any problems.

Update: Edited as per answers 1)Resolved the issue of "Queue Full" situation. 2) There is BlockingCollection<T> and ConcurrentQueue<T> in .NET4. So there is no need to reinvent the wheel(for .NET4)

public class CustomQueue<T> where T: class
{
    class Node
    {
        public Node()
        {
            Value = null;
            NextNode = null;
        }

        public Node(T value)
        {
            Value = value;
            NextNode = null;
        }

        public T Value;
        public Node NextNode;
    }

    object PushLocker = new object();
    object PopLocker = new object();
    Semaphore QueueSemaphore;
    volatile int PushIncrement;
    volatile int PopIncrement;
    int MaxItems;
    Node FirstNode;
    Node LastNode;

    public CustomQueue(int maxItems)
    {
        QueueSemaphore = new Semaphore(0, maxItems);
        MaxItems = maxItems;
        FirstNode = LastNode = new Node();
        PushIncrement = 0;
        PopIncrement = 0;
    }

    public int Size()
    {
        return PushIncrement - PopIncrement;
    }

    public bool Push(T value)
    {
        lock(PushLocker)
        {
            if((Size()) >= MaxItems)
            {
                lock(PopLocker)
                {
                    PushIncrement = PushIncrement - PopIncrement;
                    PopIncrement = 0;
                    return false;
                }
            }
            Node newNode = new Node(value);                
            LastNode.NextNode = newNode;
            LastNode = newNode;
            PushIncrement++;
            QueueSemaphore.Release();
            return true;
        }            
    }

    public T Pop()
    {
        QueueSemaphore.WaitOne();
        lock(PopLocker)
        {
            Node tempFirst = FirstNode;
            Node tempNext = FirstNode.NextNode;
            T value = tempNext.Value;
            tempNext.Value = null;
            FirstNode = tempNext;
            PopIncrement++;
            return value;
        }
    }
}

Answer 1

It looks like a good implementation at a glance. Using different locks is always a red flag to me so I took a good hard look at some of the edge cases involving simultaneously calls to Pop and Push and it appears safe. I suspect you probably educated yourself on the linked list implemenation of a blocking queue huh? The reason why this is safe is because you only ever reference LastNode from Push and FirstNode from Pop otherwise the whole trick would fall apart.

The only thing that is sticking out at me right now is that when you try to release a count from a Semaphore it will throw an exception if it is already full so you might want to guard against that.¹ Otherwise you will end up with extra nodes in the linked list and the queue will 1) have more than the maximum number of items and 2) it will get live-locked.

Update:

I gave this some more thought. That Release call in the Push method is going to be very problematic. I see only one possible solution. Remove the maxItems parameter from the constructor and allow the semaphore to count up to Int.MaxValue. Otherwise, you are going to have to radically change your approach resulting in an implementation that is no where close to what you currently have.

¹_{I think you will find that this will be more difficult than what you might immediately realize.}