JavaScriptの配列にはpushpopがあるのでそれを使えばわざわざ自分でこねこねしなくてもいいのですが、一度自分で実装しておこうとおもったのでやったメモ。

環境


下記の環境で試してます。

  • Node.js 13.0.1
  • TypeScript 3.8.3

配列を使用したコード (JavaScript)


まず、初回に書いたのがコレ。配列のindexでこねこねする。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Stack {

constructor() {
this._stack = [];
}

push(item) {
this._stack[this._stack.length] = item;
}

pop() {
if (this._stack.length == 0) {
return null;
}
const top = this._stack[this._stack.length - 1]
this._stack.splice(this._stack.length - 1, 1);
return top;
}
}

実行してみる。

1
2
3
4
5
6
7
8
9
10
const stack = new Stack();

stack.push('a');
stack.push('b');
stack.push('c');

console.log(stack.pop()); // c
console.log(stack.pop()); // b
console.log(stack.pop()); // a
console.log(stack.pop()); // null

さて、これでできた…と言えなくもない。

データ構造を自分で定義するコード (JavaScript)


配列を使うのがなんか邪道な気がしたので配列を使わずに実装してみる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Item {

constructor(value) {
this._value = value;
this._prevItem = null;
}

getValue() {
return this._value;
}

setPrevItem(item) {
this._prevItem = item;
}

getPrevItem() {
return this._prevItem;
}
}

class Stack {

constructor() {
this._size = 0;
this._top = null;
}

push(item) {
this._size++;
item.setPrevItem(this._top);
this._top = item;
}

pop() {
if (this._size === 0) {
return null;
}
const top = this._top;
this._top = this._top.getPrevItem();
this._size--;
return top;
}
}

実行してみる。

1
2
3
4
5
6
7
8
9
10
const stack = new Stack();

stack.push(new Item('a'));
stack.push(new Item('b'));
stack.push(new Item('c'));

console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

ちゃんと動く。

1
2
3
4
Item { _value: 'c', _prevItem: Item { _value: 'b', _prevItem: Item { _value: 'a', _prevItem: null }}}
Item { _value: 'b', _prevItem: Item { _value: 'a', _prevItem: null } }
Item { _value: 'a', _prevItem: null }
null

データ構造を自分で定義するコード (TypeScript)


せっかくなので一つ前のやつをTypeScriptでやってみる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Item<T> {

private _value: T;
get value(): T {
return this._value;
}
set value(value: T) {
this._value = value;
}

private _prevItem: Item<T>;
get prevItem(): Item<T> {
return this._prevItem;
}
set prevItem(value: Item<T>) {
this._prevItem = value;
}

constructor(data: T) {
this._value = data;
}
}

class Stack<T> {

private _size: number = 0;
get size(): number {
return this._size;
}
set size(value: number) {
this._size = value;
}

private _top: Item<T>;
get top(): Item<T> {
return this._top;
}
set top(value: Item<T>) {
this._top = value;
}

constructor() {
this._size = 0;
this._top = null;
}

push(item: Item<T>) {
this.size++;
item.prevItem = this.top;
this.top = item;
}

pop() {
if (this._size === 0) {
return null;
}
const _top = this.top;
this.top = this.top.prevItem;
this.size--;
return _top;
}
}

実行してみる。

1
2
3
4
5
6
7
8
9
10
const stack = new Stack<string>();

stack.push(new Item<string>('a'));
stack.push(new Item<string>('b'));
stack.push(new Item<string>('c'));

console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

結果。ちゃんと動く。

1
2
3
4
Item { _value: 'c', _prevItem: Item { _value: 'b', _prevItem: Item { _value: 'a', _prevItem: null }}}
Item { _value: 'b', _prevItem: Item { _value: 'a', _prevItem: null } }
Item { _value: 'a', _prevItem: null }
null

まとめ


満足した。おわり。