スタック

英

stack

関

積み重なる

WordNet

1. load or cover with stacks; "stack a truck with boxes"
2. an orderly pile
3. arrange in stacks; "heap firewood around the fireplace"; "stack your books up on the shelves" (同)pile, heap
4. arrange the order of so as to increase ones winning chances; "stack the deck of cards"

PrepTutorEJDIC

1. 『干し草の山』,麦わらなどの山,いなむら / (一般に,物を積み上げた)『山』,(…の)積み重ね《+『of』+『名』》 / (図書館などの)書架,ラック;《複数形で》(特に,図書館などの)書庫 / 煙突 / 《しばしば複数形で》《話》多数,多量(の)《+『of』+『名』》 / 〈干し草・本・皿など〉‘を'積み重ねる《+『up』+『名,』+『名』+『up』》 / (…を)〈ある場所〉‘に'積み上げる《+『名』+『with』+『名』》 / 《米話》(…に対して)〈カード〉‘を'不正な切り方をする《+『名』+『against』+『名』》 / 〈飛行機〉‘を'空港上空で旋回待機させる / 山に積まれる,山になる / 〈飛行機が〉空港上空で旋回待機する

Wikipedia preview

出典(authority):フリー百科事典『ウィキペディア（Wikipedia）』「2016/06/03 01:04:32」(JST)

wiki ja

[Wiki ja表示]

push（プッシュ） およびpop（ポップ） のスタックの単純な表現

スタックの単純な表現

スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。

特にその具象としては、割込みやサブルーチンを支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタによるコールスタックをメモリ上に持っていることが多い。

抽象データ型

抽象データ型としてのスタックは、ノード（何らかのデータを持ち、別のノードを指し示すことができる構造）のコンテナ（データを集めて格納する抽象データ型の総称）であり、2つの基本操作プッシュ(push)とポップ(pop)を持つ。Pushは指定されたノードをスタックの先頭（トップ）に追加し、既存のノードはその下にそのまま置いておく。Popはスタックの現在のトップのノードを外してそれを返す。

よく使われる比喩として、食堂にあるバネが仕込まれた台に皿や盆を積み重ねておく様子がある。そのようなスタックでは利用者は一番上（トップ）の皿だけにアクセスすることができ、それ以外の皿は隠されている。新たに皿が追加される（Pushされる）と、その新しい皿がスタックのトップとなり、下にある皿を隠してしまう。皿をスタックから取る（Popする）と、それを使うことができ、二番目の皿がスタックのトップとなる。二つの重要な原則がこの比喩で示されている。第一は後入れ先出し (LIFO: Last In First Out) の原則である。第二はスタックの中身が隠されているという点である。トップの皿だけが見えているため、三番目の皿がどういうものかを見るには一番目と二番目の皿を取り除かなければならない。

他の操作

多くのスタック実装では「Push」と「Pop」以外の操作をサポートしている。スタックの大きさ（長さ）、「現在のスタックのトップのノードを返すが、それをスタックから取り除かない」Peek操作、トップではなくn番目の参照・操作、入れ替え等も実装されることもある。連結リストではO(n)だが配列による実装ではO(1)、その逆、等色々な場合がある。

実装

n 個の要素のスタックが必要とするメモリ容量はO (n )、つまりスタック長に比例する。個々の操作が一定時間O (1) で完了する実装は配列や連結リストを使っても簡単に実現できる。

実装の詳細については別に議論する。

関連するデータ構造

FIFO(First In First Out、先入れ先出し)の原則を持つデータ構造または抽象データ型はキューである。スタックとキューの操作を組み合わせて提供するものは両端キュー(deque)と呼ぶ。例えば、探索アルゴリズムでスタックを使うかキューを使うかによって、深さ優先探索（スタック使用）か幅優先探索（キュー使用）になる。

ハードウェア

ハードウェアによるスタックの実装法には、主に次の2つがある。

• シフトレジスタ等により、ハードウェア的に直接、プッシュ・ポップできるようにしたもの
• メモリ上の領域と、スタックポインタによるもの

前者は、たとえば4004の「3段のスタック」がそのようなものである。後者は多くのコンピュータが持っている。以下これについて述べる。

典型的なスタック

典型的なスタックはコンピュータのメモリ上に固定の基点と可変のサイズを持つ領域である。初期状態ではスタックのサイズはゼロである。「スタックポインタ」（一般にハードウェアのレジスタが使われる）はスタック内で最も後で参照された位置を指している。スタック長がゼロのとき、スタックポインタはスタックの基点を指す。

あらゆるスタックで実施可能な2つの操作は以下の通りである。

Push操作

スタックポインタが指す場所にデータを格納し、そのデータのサイズのぶんだけスタックポインタをずらす。

Pop操作

スタックポインタが指している現在位置にあるデータを取り出し、スタックポインタをそのデータのぶんだけ（Pushとは逆方向に）ずらす。

スタック操作の基本原則には様々なバリエーションがある。スタックは初期状態ではメモリ上の固定の位置に配置される。データがスタックに追加されると、スタックポインタはデータ追加に伴うスタックの領域拡張に従って変更される。そのときのスタックの延びていく方向は特に規則は無く、実装によってアドレスの小さくなる方向だったり、大きくなる方向だったりする。

昔のコンピュータで、ヒープ領域をアドレスの小さいほうから大きいほうへ伸ばし、スタックを大きいほうから小さいほうへ伸ばす（そのようにすると、メモリが足りない場合はどちらを伸ばす余裕もなく、完全にメモリを使い切って計算続行不可能となる）という設計にした名残りから、アドレスの大きいほうから小さいほうへ伸びるものが多いが、PA-RISCは逆である。

例えば、あるスタックが1000番地から開始して、アドレスの小さい方向に延びていくとする。その場合、データは1000番地よりも小さい番地に格納され、スタックポインタはそれに伴って小さな番地を格納するようになる。そのスタックからデータをPopすると、スタックポインタに格納されているアドレスは大きくなる。

（初期状態の）スタックポインタはスタックの基点そのものではなく、その少し上か下（スタック成長方向に依存）の限界アドレスを指している場合もある。しかし、スタックポインタは基点を超えていくことはできない。換言すれば、スタックの基点が1000番地でスタックがアドレスの小さい方向（999番地、998番地など）に成長する場合、スタックポインタは決して1000番地を超えてはならない（1001番地や1002番地は不可）。Pop操作によってスタックポインタが基点を超えると「スタック・アンダーフロー」が発生する。逆にPush操作がスタックの最大許容範囲を超えてスタックポインタを操作することになるなら「スタック・オーバーフロー」が発生する。

スタックに強く依存している環境では、追加の操作を備えている場合がある。以下に例をあげる。

Dup(licate)

トップのアイテムを pop して2回 push する。これによって元のスタックトップのアイテムが2個スタックトップに存在することになる。

Peek

トップのアイテムを pop するが、スタックポインタを変更せず、スタックのサイズも変化しない（つまり、アイテムはスタック上に残存する）。Top 操作と呼ぶことも多い。

Swap または Exchange

スタックトップの2つのアイテム（つまり一番目と二番目）を入れ替える。

Rotate

トップの n 個のアイテムを回転するように入れ替える。例えば、n = 3 で、スタックに 1、2、3 が順に置かれているとき、この順番を 2、3、1 のように変化させる。この操作はバリエーションが多く、一般には left rotate（左回転）とright rotate（右回転）と呼ばれる操作を備えることが多い。

スタックは上に成長するようにイメージされることもあるし、左から右に成長するようにイメージされることもあり、トップという言い方ではなく右端と言ったりもする。このようなイメージはメモリ上のスタックの実際の構造とはあまり関係ない。right rotateと言ったとき、一番目の要素を三番目の位置に置き、二番目を一番目、三番目を二番目の位置に置く。これを二種類のイメージで表すと次のようになる。

apple banana
banana ==right rotate==> cucumber
cucumber apple

cucumber banana apple ==right rotate==> apple cucumber banana

スタックはコンピュータ内では通常、メモリセルのブロックで構成される。そのブロックの「底」は固定の位置にあり、スタックポインタが「トップ」のセルのアドレスを格納している。「底」とか「トップ」という用語はスタックがアドレスの大きくなる方向に成長するか、小さくなる方向に成長するかに関係なく使われる。

スタックへのアイテムの push により、そのアイテムのサイズのぶんだけスタックポインタがずらされ（増減はメモリ空間内のスタックの成長方向に依存する）、次のセルを指すようにして、新たなトップとなるアイテムをスタック領域にコピーする。詳細な実装に依存するが、push 操作を完了したときのスタックポインタの値はスタック上の次の未使用領域を指しているかもしれないし、現在のトップのアイテムを指しているかもしれない。スタックポインタが現在のトップのアイテムを指している場合、次回の push のときには最初にスタックポインタをずらさなければならない。逆にスタックポインタが次の未使用領域を指しているなら、次回の push のときには最後にスタックポインタをずらすことになる。

スタックの pop 操作は push の逆となる。Push とは逆の順番でスタックのトップのアイテムが取り出され、スタックポインタが更新される。

コールスタック

詳細は「コールスタック」を参照

以上のようなスタックは、特にコールスタックに使われる。

具体例

多くのプロセッサはスタックポインタとして使用可能なレジスタを持っている。x86のようなプロセッサは専用のスタックポインタレジスタを持っている。他のPDP-11や68000ファミリなどは、アドレッシングモードによって任意のレジスタをソフトウェア的にスタックポインタとして使用できるようになっているが、普通は割込みやJSR命令が操作するA7レジスタを使う。RISCの多くはそのように特別扱いされるようなレジスタを持たず、どのレジスタをスタックポインタとして使うかは通常ABIで決めており、ソフトウェアでスタック処理をおこなう。Intel 8087シリーズの数値演算コプロセッサはスタックアーキテクチャである。一部のマイクロコントローラ（例えばいくつかのPIC）は固定サイズのスタックを内蔵しており、その任意の位置に直接アクセスすることはできない。

以上のようなスタックポインタによるスタックではなく、直接ハードウェアで実現したスタックを持つコンピュータもある。

• Computer Cowboys MuP21
• Harris RTX line
• Novix NC4016

なお、以上のようなスタックがあるコンピュータをスタックマシンとするのは間違いである。詳細は後述のスタックマシンについての記述を参照すること。

ソフトウェア

この節では、抽象データ型としてのスタックのソフトウェアによる実装について述べる。

高水準言語では、スタックは配列や線形リストを使って効率的に実装可能である。LISPでは任意のリストに対して push や pop に相当する関数（consがpush、cdrがpopである）を使用可能なので、スタックを実装する必要は無い。

応用例

式評価と構文解析

逆ポーランド記法を使用している電卓（Hewlett-Packardの関数電卓など）は、値を保持するためにスタック構造を使う。式は、前置記法、中置記法、後置記法のいずれかで表現される。ある記法から別の記法への変換にはスタックが必要となる。多くのコンパイラは低レベルな言語に翻訳する前の構文解析のためにスタックを使用する。多くのプログラミング言語は文脈自由言語であり、スタックベースの機械で構文解析することができる。ちなみに自然言語は文脈依存言語であり、スタックだけではその意味を解釈することはできない。

例えば、((1 + 2) * 4) + 3 という計算は、交換法則と括弧を優先するという前提で、次のように後置記法（逆ポーランド記法）に変換できる。

1 2 + 4 * 3 +

この式はスタックを使って左から右に以下のように評価できる。

• オペランド（演算数）に遭遇したら push する。
• 演算子に遭遇したら、スタックから2つのオペランドを pop して演算を行い、
• その解を push する。

具体的には以下のようになる。「スタック」は「操作」した後の状態を示している。

入力	操作	スタック
1	オペランドをPush	1
2	オペランドをPush	1, 2
+	加算	3
4	オペランドをPush	3, 4
*	乗算	12
3	オペランドをPush	12, 3
+	加算	15

最終的な演算結果は 15 で、終了時にスタックのトップに置かれている。

探索問題の解法

探索問題を解くとき、総当り的か最適化されているかに関わらず、スタックを多大に必要とすることが多い。総当り探索の例としては、力まかせ探索やバックトラッキングがある。最適探索の例としては、分枝限定法(branch and bound)やヒューリスティックによる解法がある。いずれのアルゴリズムでも、発見してはいるが探索していない探索ノードを覚えておくのにスタックが必要となる。スタックを使う以外の手法としては再帰を使う方法があるが、これはコンパイラが生成するコードが内部的に使用するスタックで代替しているだけである。スタックを使った探索は幅広く使われており、木構造の単純な幅優先探索や深さ優先探索から、クロスワードパズルを自動的に解くプログラムやコンピュータチェスゲームでも使われている。ある種の問題はキューなどの別のデータ構造を使って解くこともでき、探索順を変えたいときに有効である。

プログラミング言語処理系の実装

詳細は「コールスタック」を参照

ほとんどのコンパイルされたプログラムは実行時（ランタイム）環境においてコールスタックを使用し、プロシージャ/関数呼び出しに関する情報を格納するのに使っている。そして、呼び出し時のコンテキスト切り替えや呼び出し元への復帰の際に使用して、呼び出しの入れ子を可能としている。そのとき、呼び出される側と呼び出し側の間には引数や返り値をスタックにどう格納するかという規則が存在する。スタックは関数呼び出しの入れ子や再帰呼び出しを実現するための重要な要素となっている。この種のスタックはコンパイラが内部的に使用するもので、プログラマがこれを直接操作することはほとんど無い。

コールスタック内に関数の呼び出し毎に作られるフレームをスタックフレームと言い、それをたどって（トレースして）得られる呼び出しの情報をスタックトレースと言う。

プログラミング言語によっては、プロシージャ内のローカルなデータをスタックに格納する。ローカルなデータの（スタック上の）領域はプロシージャに入ってきたときに割り当てられ、出て行くときに解放される。C言語はこのような手法で実装されている典型例である。データとプロシージャ呼び出しに同じスタックを使うことは重大なセキュリティ問題を引き起こす可能性があり、プログラマはそのようなバグを作りこんで深刻なセキュリティ問題を発生させないように気をつける必要がある。

セキュリティ

詳細は「バッファオーバーラン」を参照

たいていの場合、プロシージャ内のローカルなデータとプロシージャ呼び出しに関する情報は共通のスタックに格納されている。つまりプログラムは、プロシージャ呼び出しのリターンアドレスという極めて重要な情報を保持しているスタックに対して、データを出したり入れたりしているのである。データをスタック上の間違った領域に書き込んだり、大きすぎるデータをスタックに書き込んだりして、リターンアドレスが壊されると、プログラムが異常動作することになる（バッファオーバーラン攻撃）。

悪意ある者がこの種の実装を逆手にとって、入力データのサイズをチェックしていないプログラムに大きすぎるデータを入力したりする。そのようなプログラムはデータをスタック上に格納しようとしてリターンアドレスを壊してしまう。攻撃者は実験を繰り返し、リターンアドレスがスタック領域内（特に攻撃者の入力データが書き込まれた領域内）を指すようになる入力データのパターンを見つけ出し、許可されていない操作をするような命令列を入力データに含ませることでセキュリティを破る。こうした攻撃に対してプログラマはスタックの扱いに注意する必要がある。

スタック指向プログラミング言語

いくつかのプログラミング言語はスタック指向である。スタック指向言語は、基本操作（二つの数の加算、一文字表示など）でスタックから引数を取ってくるようになっていて、結果をスタックに返すようになっている言語である。

たいていは複数のスタックを使うよう設計されており、典型的なForthは、引数受け渡しのためのスタックとサブルーチンのリターンアドレスのためのスタックを持つ。PostScriptはリターンスタックとオペランドスタックを持ち、グラフィックス状態スタックと辞書スタックも持っている。日本語プログラミング言語のMindもForthベースである。

スタックマシン

詳細は「スタックマシン」を参照

機械語命令の体系がスタック指向プログラミング言語に類似している、すなわち、命令のオペランドがスタックであるマシンをスタックマシンと言う。最も有名なものとしてバロース B5000がある（B5000は、高水準言語（ALGOL）のサポートを目的として、前述のコールスタックもアーキテクチャでサポートしているが、コールスタックをアーキテクチャでサポートしている、という意味では「スタックマシン」の語は使わない）。

またx86等でも、スタックポインタ間接参照によってスタックマシンのように使うことはできるが、普通あまりスタックマシンとはしない。

多くの仮想機械もスタックマシンであり、例えばp-コードマシンやJava仮想マシンなどがある。x87の命令もスタックマシン的である。

これに対し、オペランドがレジスタのマシンをレジスタマシンと言う。多くの実機がレジスタマシンであるため実機に対してこの語が使われることは少ない。仮想機械ではLua 5の仮想機械がレジスタマシンである。

歴史

スタックを使った式評価方法を最初に提案したのはドイツの初期のコンピュータ科学者フリードリッヒ・L・バウアーであり、その業績により1988年、IEEE Computer Society Pioneer Award を受賞した。

UpToDate Contents

全文を閲覧するには購読必要です。 To read the full text you will need to subscribe.

• 1. 遠位指節間関節（つち指）の伸筋腱損傷 extensor tendon injury of the distal interphalangeal joint mallet finger
• 2. 超音波内視鏡検査：正常な膵胆管の解剖学 endoscopic ultrasound normal pancreaticobiliary anatomy
• 3. 肺結節のCTおよびPET computed tomographic and positron emission tomographic scanning of pulmonary nodules
• 4. 陣痛室および分娩室以外での急産 precipitous birth not occurring on a labor and delivery unit
• 5. 第VIII因子および第IX因子の生物学と正常な機能 biology and normal function of factor viii and factor ix

Japanese Journal

• スマートスタック技術による異種材料高効率多接合太陽電池

• 応用物理 86(7), 552-557, 2017-07
• NAID 40021261685

• Ge₁-xSn[x]ゲートスタック構造における欠陥の物性評価 (シリコン材料・デバイス)

• 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 117(101), 39-42, 2017-06-20
• NAID 40021249459

• 2チップスタックWABEパッケージ

• フジクラ技報 (130), 37-41, 2017-04
• NAID 40021220942

Related Links

• スタック（車）って何ですか？ - その他(車) 解決済 | 教えて！goo

車がスタックするっていいますが、どのような状態になるのでしょうか？ 九州在住で雪が少ない為、よく理解できません。辞書にもないし、パソコン関連の言葉としての説... - その他(車) 解決済 | 教えて！goo

• スタックとは｜stack - 意味/解説/説明/定義 ： IT用語辞典

スタック（stack）とは、最後に入力したデータが先に出力されるという特徴をもつ、データ構造の一種。本を机の上に積み上げるような構造になっており、データを入れるときは新しいデータが一番上に追加され、データを出すときは ...

Related Pictures

Japan Pharmaceutical Reference

薬効分類名

• 経皮複合消炎剤

販売名

ゼスタックローション

禁忌

（次の患者には使用しないこと）

• 出血性血液疾患（血友病、血小板減少症、紫斑病等）[本剤に含まれるヘパリン類似物質は血液凝固抑制作用を有し、出血を助長するおそれがある。]
• 僅少な出血でも重大な結果を来すことが予想される場合[本剤に含まれるヘパリン類似物質は血液凝固抑制作用を有し、出血を助長するおそれがある。]
• サリチル酸に対し過敏症の既往歴のある患者

効能または効果

• 外傷後の疼痛・腫脹・血腫、肩関節周囲炎、腱・腱鞘・腱周囲炎、筋・筋膜性腰痛、変形性関節症（深部関節を除く）、関節リウマチによる小関節の腫脹・疼痛の緩解
• 通常、1日1〜数回適量を患部に塗布する。

薬効薬理

鎮痛作用

• Randall-Selitto法によるラット足蹠のイースト浮腫に対する疼痛抑制試験において、本剤は無処置対照群及び基剤群に対し有意にその効果が認められた。³⁾

抗炎症作用

• ラットアジュバント関節炎抑制試験、マウスクロトン油耳浮腫抑制試験、マウスピクリルクロライド誘発遅延型炎症抑制試験において、本剤は無処置対照群及び基剤群に対し有意にその効果が認められた。³⁾

---

★リンクテーブル★

リンク元	「stack」「積み重なる」
拡張検索	「ゼスタック」「スタック・ツイン」

「stack」

　　[★]

• スタック、積み重なる

　 　 　 　 　

「積み重なる」

　　[★]

英

stack

関

スタック

「ゼスタック」

　　[★] ヘパリン類似物質、副腎エキス、サリチル酸

「スタック・ツイン」

　　[★]

英

stuck twin

関

双胎間輸血症候群