エンジニア実践的基礎: スタック

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

スタックとは

スタックは最後の要素のみ参照・追加・削除できるデータ構造です。これは積み上がったお皿のようなものです。お皿をとり出すとき途中のお皿を取り出す人はあまりいません。普通は一番上の皿を取り出します。新しいお皿を置くときも、途中からではなく一番上におきます。

別の考えではスタックは制限された配列と言えます。配列は要素を追加するときにはどこにでも追加できますが、スタックは最後の要素にしか追加できません。また、配列は要素を取り出すときにはどこからでも取り出せますが、スタックは最後の要素しか取り出せません。

このように配列の操作を制限することで、スタックは簡単に実装できます。

class Stack:
  def __init__(self):
    # 配列から実装
    self.stack = []
  
  def push(self, value):
    # 末尾に追加
    self.stack.append(value)
  
  def pop(self):
    if self.is_empty():
      return None
    # 末尾から取り出し
    return self.stack.pop()

  def peek(self):
    if self.is_empty():
      return None
    # 末尾の値を取得
    return self.stack[-1]
  
  def is_empty(self):
    return len(self.stack) == 0

まとめ