Stack and queue are probably the mostly commonly used data structures, for example, a stack is required in the depth first search and a queue is required in a breath first search. However, when it comes to the explicit implementation, one usually settle with the old friend – list, since it is so powerful and have native operations micmic both structures behavior. Here is a quick post about the performance comparison.

Stack

the stack data structure should support Last In First Out (LIFO), and basic operations should include quick put and get. Both list and deque are good for a stack given their performance are very comparable. However, each of them has their own advantages over the other in an obvious way, so pick wisely based on the use case.

Here is a performance comparison demonstrating both list and deque can be used for stack, both constant O(1) for one side put and get.

This is another performance test that shows deque’s random access O(n) is much slower (300x slower) than a list O(1).

Queue

the queue data structure should support the concept of First In First Out (FIFO), and basic operations include put and get too, but the put and get should happen at different ends.

You can use list append to push objects which is fast, but in order to get the first element, you will need to use the pop(index=0) which requires shifting all rest of elements.

You can find that using the deque data structure achieves the best performance of 152ms to add 1M objects and only 120ms to retrieve all those objects. For the queue.Queue, it took 2.118s (14x slower) to store and 2.214s (18x slower) to get all objects. Last for the list, it is pretty quick to add all the objects 162ms but the pop(0) took close to 3 minutes (1450x slower)!

Lesson learned, use deque if you need a queue.