Randomised Queue implementation - ideas for randomness

I am taking the Algorithms course in coursera. One of the assignments is the following:

Randomized queue. A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random among items in the data structure.

I am trying to find a way to implement dequeue (randomly removing an item) in a constant amount of time. I have thought of an idea to do this recquiring a deque (which supports removing and adding an item from the front and back in constant time). My idea is as follows:

• Use a deque as an underlying data structure inside the randomized queue
• Enqueue - use a library function to generate an integer between 0 and 1 inclusive. If the integer is 0, add the item to the front of the deque. Otherwise, add it to the back.
• Dequeue - any direction would be fine.

The reason why the randomness happens in enqueue rather than in dequeue is because I find it to be not exactly random (E.G. n calls to enqueue will have dequeue only return either the first or nth item). So to be sure the items are being removed randomly, I decided to enqueue them randomly.

This idea seems good to me because I cannot find holes in it, but the problem is I cannot prove that my idea would really work. I don't know much about randomness. In fact, this is only the 5th time I am working with random data structures.

Is my idea correct? Will it generate a data structure that removes items at random?