スタックはどのように作成され、処理されますか？

C++以降のものは、 "スタック"のような振る舞い（ベクタ、リスト、配列リストなど）を扱う素敵な構造を持っているので、Cの点で質問を残したい。スタックはどのように作成され、処理されますか？

コンパイラ、スタック、筆跡と追記、パーサー、レクサー、そしてコンパイラを一緒にまとめることを含むすべてのことについて、私が今学期のコースで後でやる必要があります。スタックの理解が確実であることを確認したい。

私は、一緒にどのように組み立てられるかに関する一般的な考えがあると信じています。基本的には、LIFOモデルに従った配列があります。要素を追加すると、配列の最後に「プッシュ」され、削除されると「ポップ」されます。そこに問題はありません。私の懸念事項は実装の詳細によって決まります。要素の数はどのように追跡されますか？スタックをどのくらいの大きさに初期化する必要がありますか？これらの詳細をまとめて保持する構造を使用すべきですか？変数はグローバルであるか？

私の教授は、すでに私は（一般的に、私は他の誰かのの理解を取得する前に一緒に自分自身を何かを置くために持っている私自身の理解のためのいくつかの補足的な詳細を探しています、私たちの割り当てに関連したいくつかのソースコードを手渡しましたコード）。私のプログラミング経験の大部分では、スタックは私のコントロールを超えた魔法の場所でしたが、再帰関数が深すぎると爆発するでしょう（誰ですか？）。

ありがとうございます。

EDIT：

[OK]を、私は明確にする必要があると思う一つのことは、私は「真」のスタックを作っていないのですが、中置epxressionを取り、後置に変換するために必要とされるということです。私はのスタックデータ構造を見ています。そのため、これに関連したアーキテクチャ関連のものはこれ以降適用されないかもしれません。私は、BNF表記法で説明されている規則の削減と同様に、スタックがこれを処理する方法であるという印象を与えられました。

出典

2012-01-12 Chad Harrison

あなた自身のデータを入れたいデータ構造としての "スタック"と、C/C++が通常はランタイム時にローカル変数を格納して関数呼び出しを行う "スタック"を区別する必要があるでしょう。 – nos

あなたはランタイムスタックについて話していますか？またはスタックのデータ構造ですか？ – Kekoa

コールスタックは、スタックデータ構造を介して実装されていません。 – Viruzzo

ここでどのような種類のスタックについて話していますか？

ほとんどのCPUアーキテクチャには、基本的にCPUが関数呼び出しをどのように追跡するかというスタックという概念があります。 Cは、通常、この目的のために同じスタックを使用するようにコンパイルされます。また、引数渡しにも頻繁に使用されます。

このような「アーキテクチャ上の」スタックはあまり必要としません。通常、CPUにスタックの先頭を指すレジスタがあります。オペレーティングシステムの仕事は、プロセスが開始するたびに、そのプロセスに有効なスタックポインタがあることを確認することです。これは、メモリを割り当て、レジスタを適切なアドレスに初期化することによって行われます。現代の「大」OS：仮想メモリなどを使用することで、要求に応じて動的にスタックを拡張することができます。

このような場合、スタック内の要素の数が明示的に追跡されていない場合は、現在のスタックポインタを調べ、プロセスのスタックスタックと比較して、バイトの数を計算できます。しかし、それらのバイトの内部構造については教えていません。これは、このような低レベルの構成では正常です。

、コメントでヒント号として、あなたが本当にスタックデータ構造の話をしている、それは多くの可能性のあるAPIを想像することが可能ですC.でこのようなことのための標準的な実装が存在しない場合：S、

typedef struct _Stack Stack; 

Stack * stack_new(size_t element_size, size_t initial_depth, int allow_growth); 
int  stack_push(Stack *stack, const void *element); 
int  stack_pop(Stack *stack, void *element); 
void stack_peek(const Stack *stack, void *element); 
size_t stack_depth(const Stack *stack); 
void stack_clear(Stack *stack);

上記のAPIは、最初の深さと、制限を超えてユーザーに成長しようとするとスタックが成長するかどうかを示します。これは、私の見解では、汎用APIの場合は賢明です。

出典

2012-01-12 16:02:37 unwind