What to use for Python stacks and queues (speed comparison of each data structure)

Introduction

This article is mainly about competitive programming.

There are multiple ways to implement stacks and queues in Python.

--Stack --Use list (ʻappend () , pop () ) --Use collections.deque (ʻappend () ,pop ()) --Queue --Use list (ʻappend () , pop (0) ) --Use collections.deque (ʻappend () ,popleft ()) --Use queue.Queue (put (), get ())

By the way, which of these is the best to use? This time, we will focus on the speed aspect.

Measurement method

Add and retrieve elements 10 times, 100 times, 1000 times, 10000 times, 100000 times for each data structure.

All code omits the import part below.

import part

from collections import deque
from queue import Queue
import time

stack

use list

# stack(list)
stack_list_append = []
stack_list_pop = []
for i in range(1, 6):
    start = time.time()

    stack_list = []
    for j in range(10 ** i):
        stack_list.append(j)

    stack_list_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        stack_list.pop()

    stack_list_pop.append(time.time() - start)

use deque

# stack(deque)
stack_deque_append = []
stack_deque_pop = []
for i in range(1, 6):
    start = time.time()

    stack_deque = deque([])
    for j in range(10 ** i):
        stack_deque.append(j)

    stack_deque_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        stack_deque.pop()

    stack_deque_pop.append(time.time() - start)

queue

use list

# queue(list)
queue_list_append = []
queue_list_pop = []
for i in range(1, 6):
    start = time.time()

    queue_list = []
    for j in range(10 ** i):
        queue_list.append(j)

    queue_list_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_list.pop(0)

    queue_list_pop.append(time.time() - start)

use deque

# queue(deque)
queue_deque_append = []
queue_deque_pop = []
for i in range(1, 6):
    start = time.time()

    queue_deque = deque([])
    for j in range(10 ** i):
        queue_deque.append(j)

    queue_deque_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_deque.popleft()

    queue_deque_pop.append(time.time() - start)

Use Queue

# queue(Queue)
queue_Queue_append = []
queue_Queue_pop = []

for i in range(1, 6):
    start = time.time()

    queue_Queue = Queue()
    for j in range(10 ** i):
        queue_Queue.put(j)

    queue_Queue_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_Queue.get()

    queue_Queue_pop.append(time.time() - start)

Measurement result

When the measurement result is graphed, it is as follows.

Let's start from the upper left.

Stack result

Add element

The graph on the upper left. The deque is slightly faster, but it's about the same.

Extracting elements

The graph on the upper right. Again, the deque is slightly faster, but it's about the same.

Queue result

Add element

The lower left graph. With a large number of elements, the Queue is more than 10 times slower than the others.

Extracting elements

The graph at the bottom right. The Queue is the same as when adding an element, but the list is obviously bad. It's more than 100 times slower than the fastest deque.

Conclusion

It's best to use collections.deque for both stacks and queues.

Since it's a big deal, I'll write a simple usage.

stack

from collections import deque

s = deque([])
s.append(1)  # [1]
s.append(2)  # [1, 2]
s.append(3)  # [1, 2, 3]
s.pop()      #Remove from top[1, 2, 3] -> [1, 2]
s.pop()      # [1, 2] -> [1]
s.pop()      # [1] -> []

queue

In the stack, it was pop when it was removed, but in the queue it is just popleft.

from collections import deque

q = deque([])
q.append(1)  # [1]
q.append(2)  # [1, 2]
q.append(3)  # [1, 2, 3]
q.popleft()  #Remove from the bottom[1, 2, 3] -> [2, 3]
q.popleft()  # [2, 3] -> [3]
q.popleft()  # [3] -> []