Zenn
📖

Dart・FlutterにStackを作りましょう

2022/10/24に公開
Flutter
Dart
tech

日本語版

用語説明

スタック構造は、オブジェクトの物理的なスタックと同じ概念である。スタックに項目を追加すると、スタックの一番上に置かれます。スタックから項目を削除するときは、常に一番上の項目を削除します。

スタック操作

スタック構築の主目的は データへのアクセス方法を強制することです。
スタックには2つだけ操作があります。

  • push: スタックの先頭に要素を追加する。
  • pop:スタックの先頭の要素を削除する。

コンピュータサイエンスでは、スタックはLIFO（last-in-first-out「後入れ先出し」 データ構造として知られています。

実装

最初にStackというクラスを作成しましょう。

stack.dart
class Stack<E> {
 Stack() : _storage = <E>[]; //初期化子リスト
 final List<E> _storage;
# }

ジェネリックに慣れていない人のために説明すると、上のコードのEは、String、int、double、または独自のカスタム型など、スタックに格納したいあらゆるデータ型を表します。Eという文字を使う必要はありませんが、コレクションの要素を表現する場合には、E を使うのが一般的です。

スタックの中身を見たい場合なら、クラス内でtoStringもオーバーライドしてください。

stack.dart
@override
String toString() {
 return '--- トップ ---\n'
 '${_storage.reversed.join('\n')}'
 '\n-----------';
}

_storageのすべての要素を最後のものを先頭にしてリストアップします。

PushとPop操作

Stackに以下の操作を追加します。

stack.dart
void push(E element) => _storage.add(element);
E pop() => _storage.removeLast();

pushはリストの最後の要素を追加し、popはリストの最後の要素を削除して返します。

main 関数でスタックをテストしましょう。

main.dart
final stack = Stack<int>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
print(stack);
final element = stack.pop();
print('Popped: $element');

次のような出力が表示されるはずです:

--- トップ ---
4
3
2
1
-----------
Popped: 4

非本質的な操作

スタックをより使いやすくするために、いくつかの便利な操作があります。

Stackクラスにこのコードを追加しましょう。

stack.dart
E get peek => _storage.last;
bool get isEmpty => _storage.isEmpty;
bool get isNotEmpty => !isEmpty;

peekのおかげでトップのデータ見られます。

イテラブルからスタックの作成

イテラブル・コレクションをスタックに変換することができます。
そのためにこのコードを追加しましょう。

stack.dart
Stack.of(Iterable<E> elements) : _storage = 
List<E>.of(elements)

このサンプルをmainで実行します。

main.dart
const list = ['S', 'T', 'A', 'C', 'C'];
final staccStack = Stack.of(list);
print(staccStack);
staccStack.pop();

このコードでは、文字列のスタックを作成し、一番上の要素「E」をポップアップしています。Dartコンパイラはリストから要素の型を推測するので、より冗長なStack<String>の代わりにStackを使用することができます。

参考：Data Structures & Algorithms in Dart

English ver.

Term explenation

The stack structure is the same concept as the physical stack of objects. When an item is added to the stack, it is placed at the top of the stack. When you remove an item from the stack, you always remove the topmost item.

Stack Operations

Stacks are useful and also exceedingly simple. The main goal of building a stack is to enforce how you access your data.
There are only two essential operations for a stack:

  • push: Add an element to the top of the stack.
  • pop: Remove the top element of the stack.

In computer science, stacks are known as LIFO (last-in-first-out) data structures.

Implementation

First, let's create Stack class.

stack.dart
class Stack<E> {
 Stack() : _storage = <E>[]; //初期化子リスト
 final List<E> _storage;
# }

For those unfamiliar with generics, the E in the code above represents any data type you wish to store on the stack, such as String, int, double or your own custom type. You don't have to use the letter E, but to represent the elements of a collection, It is common to use the letter E.

If you want to see the contents of the stack, you should also override toString in your class.

stack.dart
@override
String toString() {
 return '--- TOP ---\n'
 '${_storage.reversed.join('\n')}'
 '\n-----------';
}

This will list all of the elements in _storage with the last one at the top.

Push & Pop

In Stack class add following lines.

stack.dart
void push(E element) => _storage.add(element);
E pop() => _storage.removeLast();

push adds the last element of the list, pop removes the last element of the list and returns it.

Ler's test our stack in the main function.

main.dart
final stack = Stack<int>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
print(stack);
final element = stack.pop();
print('Popped: $element');

And the output should looks like this:

--- TOP ---
4
3
2
1
-----------
Popped: 4

Non-Essential Operations

There are several useful operations that can make the stack easier to use.

Let's add this to our Stack class.

stack.dart
E get peek => _storage.last;
bool get isEmpty => _storage.isEmpty;
bool get isNotEmpty => !isEmpty;

Thanks to peek getter will we see Top of stack.

Creating a Stack From an Iterable

It is possible to convert iterable collections into stacks.
To do this add this code.

stack.dart
Stack.of(Iterable<E> elements) : _storage = 
List<E>.of(elements)

Run this sample in main.

main.dart
const list = ['S', 'T', 'A', 'C', 'C'];
final staccStack = Stack.of(list);
print(staccStack);
staccStack.pop();

This code creates a stack of strings and pops the top element “E”. The Dart compiler
infers the element type from the list, so you can use Stack instead of the more
verbose Stack.

Reference:Data Structures & Algorithms in Dart

Discussion