データ構造-Stack

スタックはデータ(資料)の積み重ねです.
資料を積み重ねて整理する場合、特性も同様に適用されます.
山積みの資料を思うと、一番上の資料から順番に出します.
実際の生活の中で整理しているとは思わないで、コンピューターが資料を蓄積していると思って、コンピューター自身のルールに従って資料を処理して、このように理解すればいいのです.
用語で言えば、これは最初の出力(LIFO)の方法であり、参考に供する.
Stackを作成します.△C言語を例にとると.
まず資料を保存するスペースが必要です.
空間を作ろう

#include <stdio.h>
#define MAX_STACK_SIZE 20

int stack[MAX_STACK_SIZE];

MAX STACK SIZEは、20と定義されている.
int型でMAX STACK SIZEのスタック配列を作成しました.
スペースを作った以上、今はフレームワーク(ルール)を作って、パソコンにここで資料を蓄積させておけばいいのです.
まず、空間の底から上に資料を積み上げるので、1層の資料を入れるたびに、最初の0格から最大格まで、1層の資料が積み上げられます.
ここでは,現在のスタック位置(レイヤ)に関する情報をtopという変数に入れる.

top = -1; //-1로 현재 위치를 지정한 이유는 다음에 나올 코드를 보면 알 수 있다.

stack位置情報を含む変数topが作成されましたが、データを入れるたびにtop変数をレイヤごとに置き換えるだけです.そうすると、資料がどんどん蓄積されて流失していきます.

void push(int v)
	if(top>=MAX_STACK_SIZE-1)
    		printf("오버플로우 방지"); //오버플로우 방지. 교재들에서는 IsFull 등의 함수로도 자주 처리함.
    	else
        	stack[++top]=value; //처음 top위치를 -1로 해서 배열의 순서 번호 0번부터 메모리 손해가 없게된다.
    	
```'```
int pop()
	if(top<0)
    		printf("언더플로우 방지"); //언더플로우 방지. 교재들에서는 IsEmpty 등의 함수로도 자주 처리함.
    	else
        	return stack[top--];

これでStackが完了しました.mainではpopは資料を返し(減算)し,pushは資料を入れることができる構造となる.
この点はほとんどすべてのプログラムを実現できるが,Stackは大量の資料を格納する必要があり,同時に少量の資料を格納する必要があることを考慮すると,上の配列でStackは非常に非効率である.
10,000,000,000,000種類のデータをStackに格納し、数少ないデータを格納する必要がある場合は、10,000,000,000種類のアレイを作成し、2,3種類のデータを入れて使用するだけで、残りのスペースはすべて消費されます.
したがって、Stackであれば、格納されるデータ量が指定されたスペースほど多くない場合は、より多くの異なる考えが必要です.
ありがたいことに、これらの考えはすでに他の人に解決策を研究された.
接続リストを利用します.
接続リストの各値には1つのアドレスと次の有効値のアドレスがあるため、値をStackに入れて減算するたびに、Stackのサイズも変化します.前述したレイアウトとは異なり、接続リストの各値は独立して存在し、相互に関連付けられています.
次に、接続リストを使用してStackを作成します.
まず接続リストを作成します.

typedef struct stack {
	int data;
    struct stack* link;
}stack;

このコードの説明は省略してもc言語が分かれば理解できる.
位置値を格納する接続リストtopを作成します.

stack* top;

次に、データの挿入と削除の関数を実装します.

void push(int v){
	stack* newnode = (stack *)malloc(sizeof(stack)) // malloc =memory alloc 코드 내용 그대로 메모리 할당 sizeof stack만큼. (stack *)으로 형변환해서 stack* newnode에 값 저장.
    newnode->data = v;
    newnode->link = top;
    top = newnode; //데이터를 push하면 가장 윗쪽에 데이터가 쌓여야하므로 stack에서의 위치를 담는 변수 top에 newnode 주소를 저장. 이해가 잘 안되시면 위 코드 내용을 머릿속으로 반복해보세요. 다음에 생성될 노드에 top 위치값을 넣고 현재 stack 꼭대기 위치 top을 재설정해주고 하면서 연결되는 흐름이 보일 겁니다.
}//node는 연결리스트에서 각 하나하나의 형태를 말합니다. (주소, 값, 다음 연결될 주소)

int pop(){
	if(top==NULL){ //비어있음 방지.
    	printf("Empty Stack!");
    }
	else {
    	stack* temp = top; //top위치의 노드를 없애야하므로 temp에 top을 저장하고
        int data = temp->data; //top(temp)의 데이터를 return해야 하므로 temp->data값을 data를 int 형으로 선언해서 저장하고
        top = temp->link;//temp(top)이 가르키는 다음 주소 값을 top에 저장해주고
        free(temp);//노드 temp를 free해준다. 그러면 top은 한칸 위로 이동하고 이전 칸은 temp로 주소와 데이터가 옮겨지고 free되어 삭제된다.
        return data;//마지막으로 data return.
    }
    

接続リストを使用してStackを完了!
では、これらはどこで使われていますか?
1.システムスタック.
プログラムは、呼び出しと返される実行順序を保存し、管理します.
ex)関数を実行するために必要な様々な変数を格納し,戻りアドレスを格納し,格納した情報をシステムスタックに挿入する.プログラムは順番に実行され、関数呼び出しと戻りに必要な情報がプッシュされ、上部のスタックがポップアップされて情報を確認し、戻りと変換操作が行われます.main関数(プログラム全体)に実行すると、空白のスタックが表示され、プログラムが終了します.

数式のかっこをチェック
1)左かっこpush
2)右括弧に遭遇したときにポップアップされ、最後に保存した括弧と比較されます.ex{()popは同じタイプok]popと同じタイプnoを比較します.
3)チェックが終了したら,空きスタックであるかどうかをチェックする.そして終わり

前衛、センター、バックを転換する
接尾辞表現を使用します.
1)「(」形式のかっこに遭遇した場合は無視し、次の文字を確認します.
2)被演算子に遭遇したときに出力します.
3)演算子に遭遇したときにスタックに挿入します.
4)「)」形式のかっこに遭遇した場合、ポップアップスタックが出力されます.
5)スペースにポップアップします.
ex.(A/B)+(C/D)//,=無視.=出力!=push ? = pop
-> , .!. ? !, . ! . ?? -> AB/CD/+

接尾辞表現演算
1)演算子をスタックに押し込む
2)演算子に遭遇した場合,必要に応じて被演算子をスタックからpopに押し込み,演算結果をスタックに押し込む.
3)修飾完了後にポップアップスタックを出力する.
ex. AB/CD/+//! = push ? = pop
. . . ! !??! !????
. . . . . . . . . !(計算結果のプッシュ)とpop

私が勉強した内容を整理した文章です.
勉強している人の中に補足説明が必要な人がいたらコメントを残しておくと積極的に回答します