# 問題解決力を鍛える！アルゴリズムとデータ構造
## 第9章
- 任意参加
- ファシリテーター: teruya
### 話す・書く順番決めルーレット
in Ruby
```ruby
['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }
```
in JavaScript
```javascript
const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]
```
### ファシリテーター決め方
- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく
### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）
当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分
### 勉強会時にやること
各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め
## 各自が書き込む場所
>[name=chen]
パッと見ただけであんまり感想が思いつかないんですが、
大学時代の授業内容を思い出しました...スタックとキューですね。
jsでキューの実装を試したい。
> キューで enqueue と dequeue を繰り返していると，tail だけでなく head も右へ右へと進んでいくので、head も tail もドンドン右に移動することになります。このままでは不必要に大きな配列サイズが必要となってしまいます。これを解決する仕組みとして広く用いられている方法が、`リングバッファ`とよばれる配列の使い方です。
リングバッファは重点なのでそれについてメモします。
https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%90%E3%83%83%E3%83%95%E3%82%A1
```
リングバッファとは、
一時的にデータを貯めておくバッファ領域のうち、
終端と先端が論理的に連結され、
循環的に利用されるようになっているもの。
```
```javascript=
const MAX = 10000
let qu = []
let tail = 0, head = 0
let result
function init() {
tail = 0
head = 0
}
function isEmpty() {
return head === tail
}
function isFull() {
return (head === (tail + 1) % MAX)
}
function enqueue(x) {
if(isFull()){
console.log('error: queue is fill.')
return
}
qu[tail] = x
++tail
if(tail === MAX) tail = 0
result = qu.slice(head, tail)
}
function dequeue() {
if(isEmpty()) {
console.log('error: queue is empty.')
return -1
}
++head
if(head === MAX) head = 0
result = qu.slice(head, tail)
return result
}
console.log('--- enqueue start ---')
enqueue(1)
console.log('qu:' + result)
enqueue(3)
console.log('qu:' + result)
enqueue(5)
console.log('qu:' + result)
enqueue(9)
console.log('qu:' + result)
enqueue(23)
console.log('qu:' + result)
console.log('dequeue:' + dequeue())
console.log('dequeue:' + dequeue())
console.log('dequeue:' + dequeue())
enqueue(100)
console.log('qu:' + result)
console.log('--- end ---')
// --- enqueue start ---
// qu:1
// qu:1,3
// qu:1,3,5
// qu:1,3,5,9
// qu:1,3,5,9,23
// dequeue:3,5,9,23
// dequeue:5,9,23
// dequeue:9,23
// qu:9,23,100
// --- end ---
```
>[name=teruya]
Rubyでは
https://docs.ruby-lang.org/ja/latest/method/Array/i/shift.html
と
https://docs.ruby-lang.org/ja/latest/method/Array/i/unshift.html
を使うと配列の先頭に追加/取り出しをできるのでキューを実現できます。
章末問題9.3
```ruby=
string = '((()()))'
answers = []
stack = []
string.each_char.with_index do |c, i|
if c == '('
stack << i
else
if stack.empty?
puts ") exists more than ( !"
exit
else
answers << [stack.pop, i]
end
end
end
if stack.empty?
puts 'Answers are:'
pp answers
else
puts '( exists more than ) !'
end
# => Answers are:
# => [[2, 3], [4, 5], [1, 6], [0, 7]]
```
>[name=hsu]
予約キャンセル待ちなどの日常はあまり意識してなかったです :thinking_face:
例えば、予約の内容変更したりする時には同じ順番になってるでしょうか？
```javascript=
class QueueNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.first = null;
this.last = null;
this.length = 0;
}
enqueue(value) {
const newNode = new QueueNode(value);
if (!this.first) {
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
this.length++;
}
dequeue() {
if (!this.first) {
return null;
}
if (this.first === this.last) {
this.last = null;
}
const dequeuedNode = this.first;
this.first = dequeuedNode.next;
dequeuedNode.next = null;
this.length--;
return dequeuedNode.value;
}
peek() {
if (!this.first) {
return null;
}
return this.first.value;
}
isEmpty() {
return this.length === 0;
}
}
```
>[name=okura]
### 9.1 スタックとキューの概念
日常生活でもキューとかスタックってよくあるよなー、と考えながら生活すると面白いです（つけ麺屋に行くと、麺の種類によっては順番が前後することがあって、これは麺の種類ごとにキューがあるんだなあ、とか）。
### 9.2 スタックとキューの動作と実装
Rubyなら`Array`クラスで済んでしまう（継承する必要もない）、特異クラスにエイリアスを付けると盤石。
```ruby=
stack = []
stack.singleton_class.class_eval do
alias_method :peek, :last
remove_method :[]=
end
stack.push 1
stack.peek # => 1
```
### 章末問題
#### 9.3
```ruby=
str = '((())))'
Char = Struct.new(:char, :index)
match = []
stack = []
str.each_char.with_index do |char, index|
if stack.last&.char == '(' && char == ')'
open = stack.pop
match << [open.index, index]
else
stack.push Char.new(char, index)
end
end
p stack.empty?
p match
```
>[name=tsujita]
> 9.1 スタックとキューの概念
勝手なイメージでスタック = 溜めているもの と思っていたので、最後にpushされたものを取り出すことなのだと勉強になりました
章末9.2の逆ポーランド記法を実装したかったのですが時間が足りず、ChatGPTにお願いしたら最初間違ったコードが返ってきて焦りました（これは直してもらったものですが、最初9行目のxとyが逆になっていた）
```ruby=
expression = ["3", "4", "+", "1", "2", "-", "*"]
def evaluate_rpn(expression)
stack = []
expression.each do |token|
case token
when /\A\d+\z/ # tokenが数字の場合
stack.push(token.to_i)
when '+', '-', '*', '/' # tokenが演算子の場合
x, y = stack.pop(2) # スタックから2つの値をpopする
case token
when '+'
stack.push(x + y)
when '-'
stack.push(x - y)
when '*'
stack.push(x * y)
when '/'
stack.push(x / y)
end
end
end
return stack.pop # スタックに残った1つの値をpopして返す
end
```
## 振り返り
>[name=teruya]
配列の機能を削ってキューを作る発想、斬新でした
>[name=hsu]
実装したすぐ忘れる一つ
>[name=tsujita]
スタックとキューはどこかで活用できそうな予感がしてます
>[name=okura]
`Queue#peek`は先頭の要素を見るの、勘違いしていたので知れてよかった。
## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める
- 大倉さん
- 読む範囲を決める
- 第10章 10.4(重み付きグラフまで)
Sign in with Wallet
Connect another wallet