So this got me thinking of trying to use some other linked list implementations. 

I've used a llist library - https://github.com/ajakubek/python-llist

Using their doubly linked list implementation:

    class DllistQueue(queue.Queue):
        def _init(self, maxsize):
            self.queue = dllist()

Results are:
>del_after_puts False del_after_gets True n_puts 20000000
>before run
>mem_pct 0.15% 
>------ put done  ----- qsize 20000000
>mem_pct 55.34% 
>------ gets done  ----- qsize 0
>mem_pct 0.15% 
>deleting queue after gets <__main__.DllistQueue object at 0x7f494ba91450>
>mem_pct 0.15% 
>time elapsed 0:02:17.642700

Using their singly listed list implementation:

    class SllistQueue(queue.Queue):
        def _init(self, maxsize):
            self.queue = sllist()

results are:
>del_after_puts False del_after_gets True n_puts 20000000
>before run
>mem_pct 0.15% 
>puting  0 qsize 0
>------ put done  ----- qsize 20000000
>mem_pct 55.34% 
>------ gets done  ----- qsize 0
>mem_pct 0.15% 
>deleting queue after gets <__main__.SllistQueue object at 0x7ff07bf484d0>
>mem_pct 0.15% 
>time elapsed 0:02:03.495047

I have not dived in how their C implementations differ from deque, but it seems to use more memory and it's slower, but it does not seem to leak at all. 

Thanks