はじめに 本記事は、主に競技プログラミングにおける話です。 Python において、スタックとキューを実装するには複数の方法があります。 スタック(stack) list を使う(append(), pop()) collections.deque を使う(append(), pop()) キュー(queue) list を使う(append(), pop(0)) collections.deque を使う(append(), popleft()) queue.Queue を使う(put(), get()) さて、この中で一体どれを使うのが最適でしょうか。 今回はそれを速度面に注目して調べます。 計測方法 各データ構造に対して、要素の追加と取り出しを10回、100回、1000回、10000回、100000回行います。 どのコードも、以下の import 部分は省略しています。
![Pythonのスタックとキューには何を使えばいいのか(各データ構造の速度比較) - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/ac967ca30794442fc75bf0a7de6d943eeb105a9f/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-412672c5f0600ab9a64263b751f1bc81.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9UHl0aG9uJUUzJTgxJUFFJUUzJTgyJUI5JUUzJTgyJUJGJUUzJTgzJTgzJUUzJTgyJUFGJUUzJTgxJUE4JUUzJTgyJUFEJUUzJTgzJUE1JUUzJTgzJUJDJUUzJTgxJUFCJUUzJTgxJUFGJUU0JUJEJTk1JUUzJTgyJTkyJUU0JUJEJUJGJUUzJTgxJTg4JUUzJTgxJUIwJUUzJTgxJTg0JUUzJTgxJTg0JUUzJTgxJUFFJUUzJTgxJThCJUVGJUJDJTg4JUU1JTkwJTg0JUUzJTgzJTg3JUUzJTgzJUJDJUUzJTgyJUJGJUU2JUE3JThCJUU5JTgwJUEwJUUzJTgxJUFFJUU5JTgwJTlGJUU1JUJBJUE2JUU2JUFGJTk0JUU4JUJDJTgzJUVGJUJDJTg5JnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmcz1jZjVkNjE4NTZiZmU2MTQwZmExNTYwMmUyZDNiODRiZg%26mark-x%3D142%26mark-y%3D57%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9NzcwJnR4dD0lNDBzYWJhJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9MzYmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz1hMDQ1OWUwY2NjZjBjZDFhNmMzYzM5NTNiNGM3ZTQxNA%26blend-x%3D142%26blend-y%3D486%26blend-mode%3Dnormal%26s%3D78a6b8561019c55898103dccf5e25679)