🎯
Dartで学ぶスタックとキュー

2024/11/28に公開
 アルゴリズムを学ぶPythonのアルゴリズムを学べる本を読んでいて、スタックとキューなるものがありました。アルゴリズムが好きな友人のSREがよく話題に出していました。
なんだろうなと気になり勉強してみました。Listを操作してるだけな気がするが。。。

 example// スタックの実装
class MyStack<T> {
  final List<T> _data = [];

  // データを追加
  void push(T value) {
    _data.add(value);
  }

  // データを取り出す
  T pop() {
    if (_data.isEmpty) {
      throw StateError('Stack is empty');
    }
    return _data.removeLast();
  }

  // スタックが空かどうかを確認
  bool get isEmpty => _data.isEmpty;

  // スタックの現在のサイズを取得
  int get length => _data.length;

  // スタックの内容を文字列として返す
  @override
  String toString() {
    return _data.toString();
  }
}

// キューの実装
class MyQueue<T> {
  final List<T> _data = [];

  // データを追加（エンキュー）
  void enqueue(T value) {
    _data.add(value);
  }

  // データを取り出す（デキュー）
  T dequeue() {
    if (_data.isEmpty) {
      throw StateError('Queue is empty');
    }
    return _data.removeAt(0);
  }

  // キューが空かどうかを確認
  bool get isEmpty => _data.isEmpty;

  // キューの現在のサイズを取得
  int get length => _data.length;

  // キューの内容を文字列として返す
  @override
  String toString() {
    return _data.toString();
  }
}

void main() {
  // スタックの使用例
  print('=== Stack Demo ===');
  final myStack = MyStack<String>();

  myStack.push('a');
  print(myStack);
  myStack.push('b');
  print(myStack);
  myStack.push('c');
  print(myStack);

  final val1 = myStack.pop();
  print(val1);
  final val2 = myStack.pop();
  print(val2);
  final val3 = myStack.pop();
  print(val3);

  print('$val1 $val2 $val3');

  // キューの使用例
  print('\n=== Queue Demo ===');
  final myQueue = MyQueue<String>();

  myQueue.enqueue('a');
  print(myQueue);
  myQueue.enqueue('b');
  print(myQueue);
  myQueue.enqueue('c');
  print(myQueue);

  final qVal1 = myQueue.dequeue();
  print(qVal1);
  final qVal2 = myQueue.dequeue();
  print(qVal2);
  final qVal3 = myQueue.dequeue();
  print(qVal3);

  print('$qVal1 $qVal2 $qVal3');
}
実行結果:

getterを使用していなかった💦

削除と値があるかのチェックはこのような動作になっております。
void main() {
  // スタックの使用例
  print('=== Stack Demo ===');
  final myStack = MyStack<String>();

  myStack.push('a');
  print(myStack); // [a]
  myStack.pop();
  print(myStack.isEmpty); // true
  print(myStack.length); // 0

  // キューの使用例
  print('\n=== Queue Demo ===');
  final myQueue = MyQueue<String>();

  myQueue.enqueue('a');
  print(myQueue); // [0]
  myQueue.dequeue();
  print(myQueue.isEmpty); // true
  print(myQueue.length); // 0
}
このDartコードには以下の特徴があります：
ジェネリクス対応: <T>を使用して、どんな型のデータでも扱えるようにしています。
エラー処理: 空のスタック/キューからの取り出しに対してエラー処理を実装しています。
プライベートな実装: _dataのように、アンダースコアを使用してプライベートなメンバーを定義しています。
追加機能:

isEmpty: スタック/キューが空かどうかの確認

length: 現在の要素数の取得
スタックとキューの主な違いは：
スタック: 後入れ先出し（LIFO - Last In First Out）
キュー: 先入れ先出し（FIFO - First In First Out）
実行すると、Pythonの例と同様の結果が得られますが、キューでは要素が異なる順序で取り出されます。
必要に応じて、さらにメソッドを追加したり、エラー処理を強化したりすることができます。
アルゴリズムを学ぶ

example

Discussion
