【プログラミング】スタックとキューって反対の概念ってより

1 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:03:44.987 ID:Vab1xMJi0.net

全く違う概念って感じじゃないか？
LIFOとFIFOで退避させて学ぶ理由が分からない

2 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:04:30.933 ID:WwG6aj1b0.net

型が同じだからだろ

3 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:04:53.588 ID:EyuqK5QO0.net

先入れ中出し

4 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:05:13.345 ID:Vab1xMJi0.net

中入れ中出しデータ構造

5 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:05:41.330 ID:KmcT6PDt0.net

連結リスト

6 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:07:19.556 ID:Vab1xMJi0.net

型とかそういう単純な話じゃないだろ

7 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:08:38.830 ID:WwG6aj1b0.net

[First/Last] in [First/Last] out
２つの言葉は同じ型

8 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:09:45.324 ID:xPlPAG2j0.net

両方dequeで実装できるってこともあるし近しい概念なのは間違いないだろ

9 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:14:18.273 ID:Vab1xMJi0.net

先頭や末尾への操作っては線形なデータ操作として統一されてるんだがな

10 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:18:26.714 ID:Vab1xMJi0.net

問題は関数フレームとかスタックマシンみたいに
計算のベースはキューよりスタックベースな点だよ

現在の計算機にとってはスタックの方が計算の基礎になってる気がするわけ
キューがベースになる計算機なんてデータフローマシン的なものしか思いつかん

11 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:28:51.840 ID:FgULmGwk0.net

並列処理

12 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:32:49.765 ID:Vab1xMJi0.net

並列処理とかバッチ処理系がキュー的なんだよな

13 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:34:52.749 ID:Vab1xMJi0.net

任意の再帰処理はループとスタック構造によって書き換えることができる

じゃあループとキューで書き換えられる処理の代表例はっていうとバッチ処理か？

14 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:35:17.958 ID:FgULmGwk0.net

待ち行列

15 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:37:55.962 ID:IAOmqUDnd.net

深さ優先探索はスタック
幅優先探索はキュー
深さ優先探索をキューで、幅優先探索をスタックで表現することは可能か

16 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:38:08.751 ID:Vab1xMJi0.net

待ち行列理論queueing theoryはあるが
スタック理論stacking theoryは聞くことがない

流石に分野が違ってくるが

17 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:43:41.677 ID:Vab1xMJi0.net

深さ優先探索、幅優先探索をそれぞれスタック、キューでやるのがベース

それを逆のデータ構造で実装するっていうことは
スタックをキューで
ないしはキューをスタックで表現できるかという問題

18 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:44:04.163 ID:DMJrKrYJd.net

反対の概念とか言ってるものあるか？
データの取り扱い方が反対って言ってるのはよく見るが

19 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:45:35.182 ID:FgULmGwk0.net

双対

20 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:48:05.580 ID:Vab1xMJi0.net

2つスタックがあればキューになる

データを積む時には一つ目のスタックAに順次積んでいく
データを取り出すときにはもう一つのスタックBに全てのデータを積み直して、その一番上を取る
再度スタックBのデータをAに積み直せばよい

面倒くさい

21 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:48:20.630 ID:Vab1xMJi0.net

双対っぽさはある

22 ：!omikuji：2018/07/05(木) 19:50:44.723 ID:LuZneegf0.net

中出しデータ構造ってえろい

23 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:51:10.808 ID:w5/Umfmq0.net

先入れ中だし

24 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:52:04.507 ID:Vab1xMJi0.net

2つキューがあればスタックになる

データを積むときには一つ目のキューAに積んでいく
データを取り出すときにはもう一つのキューBにキューAの要素を流し込んで、キューAが空になったときに移したデータが取り出すべきスタックのデータ
キューAとキューBの役割を交換すれば一連の操作が終了する

うーむ

25 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:53:26.511 ID:Vab1xMJi0.net

数学的にスタックとキューが双対であるみたいに言えるのかな
圏論が絡みそうで頭が痛いが

26 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 19:58:41.978 ID:DzmI7fzod.net

スタック２つ持つプッシュダウンオートマトンはチューリングマシンと等価って言われてるしそりゃな

27 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:00:41.813 ID:Qvpn/TR+0.net

41:03ごろ　　「やだひとしィ…」という声が初めて入る。ここで母親が死体発見らしい
　　　　　　　その後20秒ほど「ひとしぃ！ひとちゃん！」と呼び続けるも母親が涙声に。
41:38ごろ　　「やだちょっとひとし自殺しちゃった…。お願い、首つってるぅ」と母親が何者かを呼ぶ。恐らく家族
42:42ごろ　　母親が救急車へ第一報。住所氏名がばっちり入ってる
43:30ごろ　　母親が耐えきれずに電話口で嗚咽をもらす。
43:41ごろ　　ここから約十五秒ほど「ひとちゃーん、ごめんよぉ。ひとちゃん、ごめんごめん」と懺悔の声
44:36ごろ　ここ辺りから母親の呻くような鳴き声が約40秒続く
45:15ごろ　母親が泣きながら誰かに返答。口調から恐らく救急隊の電話と思われる
　　　　　「重いんで」「待っててください」等の声が聞こえるが文脈は不明
46:47ごろ　再度母親が「ひとちゃん」と呼びかけ出す。「これもうだめだな」と小声で呟く母親
　　　　　「重くて無理」と言っている為、死体の引き下ろしを試みた模様
47:27ごろ　母親が出かける前の状況を電話口で説明している。救急隊に向けてと思われる

28 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:01:22.534 ID:Vab1xMJi0.net

オートマトンにキューくっつけたマシンってあるんだっけ
それに対応する形式言語とか

29 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:04:48.358 ID:1cjC/k7Ed.net

https://en.m.wikipedia.org/wiki/Queue_automaton

チューリング完全らしい

30 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:06:26.466 ID:FgULmGwk0.net

wolframのチューリング機械がよく分からんから教えて

31 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:08:51.469 ID:Vab1xMJi0.net

分からないから感覚だけの話だけど

スタックとキューって双対っぽさがあって
オートマトンにスタック一つ乗せただけではプッシュダウンオートマトン止まり、CFG止まり
逆にキューをオートマトンに乗せればチューリング完全ってことは
状態遷移モデルのオートマトン自体、スタック寄りの計算モデル(とまでは言ってはいけないのだろうけど)なのかね

状態遷移モデルに双対になる処理マシンが存在するのか…

32 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:15:02.388 ID:Vab1xMJi0.net

スタックとキューって一体なんなんだろう

33 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:15:06.175 ID:FgULmGwk0.net

キューはInする位置とOutする位置が遠いのは関係ある？

34 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:15:07.756 ID:temraEp10.net

Cで作ってみればわかるよ

35 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:16:10.424 ID:Vab1xMJi0.net

計算量理論をもう少しちゃんとやっとけば良かったと後悔してるよ

36 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:19:51.113 ID:FgULmGwk0.net

キュー1つでスタックできる説

37 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:22:04.767 ID:Vab1xMJi0.net

キュー一つでスタックできるなら双対っぽさ無くなる

38 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:22:50.540 ID:Vab1xMJi0.net

俺には思いつかなかったけど、キュー一つでスタックになるのかね

39 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:23:07.452 ID:FgULmGwk0.net

キューとFAでチューリング完全ならできるしょたぶん

40 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:26:22.603 ID:pkLPinlFa.net

仕事だと一々スタックとかキューとか意識せず自然に使ってるからよく分からん

41 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:27:07.660 ID:Vab1xMJi0.net

キューQの長さがLのとき

スタックとしての入れる操作:
キューQの尾っぽに入れる
スタックとして出す操作:
キューQ単体で先頭から尾っぽに(L-1)データを流して取り出す

もしやこれだけでスタックなのでは

42 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:28:53.883 ID:FgULmGwk0.net

>>41
できるやん

43 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:29:09.695 ID:Vab1xMJi0.net

じゃあ双対っぽさないじゃん…

44 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:31:17.486 ID:Vab1xMJi0.net

そうなるとやっぱり>>1に戻って
スタックとキューって反対とか双対でなく
かなり違う概念なんじゃないのって話になるんだが
これが難しくてたまらなくてね

45 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:32:12.265 ID:Vab1xMJi0.net

ただ、
スタック2つでキューと等価ですよっていうこともそうなら
キュー=スタック*2
みたいなもんなのかもしれないね

46 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:32:29.827 ID:ODCGAaBz0.net

そんな事言うなら
リストだって動的に長さが変わる配列を便利にしたやつではないだろ

47 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:33:41.749 ID:FgULmGwk0.net

スタックは実質一つの値しか保存できない
キューは入る分だけ保存できる

48 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:34:15.700 ID:Vab1xMJi0.net

リストは配列の長さが動的になる版っていう説明は初歩の初歩でやるけど
あの二つの間の溝もとんでもないんだよな

49 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:35:37.870 ID:Vab1xMJi0.net

>>47
確かにそうだわ
一つしかスタックなかったら取り出してももう一度元に積み直すしかできないもんな

50 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:36:11.740 ID:pkLPinlFa.net

Array
ArrayList
List
Dictionary

51 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:37:28.122 ID:FgULmGwk0.net

楽しくなってきた

52 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:39:38.477 ID:Vab1xMJi0.net

形式言語の本でFAにスタックくっ付けてプッシュダウンオートマトンです、めでたしめでたしという論法で
なぜお友達のキューは出てこないのかようやく解決した気がする

53 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:41:47.913 ID:VEmNYwI00.net

>>48
実装も特性全然違うけど、どっちもリストだから同じともいえる

スタックとキューの比較も、どの立場でみるかで全然かわってくるのでは
そこ明らかにしないで論じても与太話以上にはならん

54 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:42:55.881 ID:Vab1xMJi0.net

>>53
このスレ、大概与太話だと思う

55 ：以下、？ちゃんねるからVIPがお送りします：2018/07/05(木) 20:45:21.539 ID:FgULmGwk0.net

>>53
今は計算可能性の観点