今回はスタックです。
すこし特性を持った、データを持つ構造体ですね。
スタックの実装には様々な方法がありますが、この記事では構造体にtop(先頭の位置)の情報を持たせることで実装しています
全体のコードはこの記事の下に貼って置くので参考にどうぞ。
また「スタック」と対をなすような構造である「キュー」についてはこちらの記事で詳しく解説しているので是非参考にしてください！！
スタックとは？
LIFOの考え方
まず、スタックにはLIFOという考え方が必要です。
LIFOっていうのは、
LAST IN FIRST OUT
のことです。
直訳すると、後入れ先出しですね。
うーん、日本語でも何いってるかわからないっすね
難しいことではないです。なんなら訳した日本語そのままですね。
後に入れたやつが先に出てくるってことです。
イメージで説明しましょう。
こんな感じで石が置いてあるとします。石ですよ、石。
この上にどんどん石を積んでいって、
こうなったとしましょう。
ここから石を取り出せと言われたらどこから取りだしますか？
もちろん一番上の石からですよね。
なぜなら他の石だと積んだ石が崩れてしまうから。
今取りだした一番上の石について考えてみましょう。
この石がいつ積まれたかというと、取り出す直前ですよね。
つまり最後に積んだ石ってことです。
そのあとにまた石を取り出すとするとどの石を取りだしますか？
これも一番上に積まれている石ですよね（最初の時点では上から２番目の石）
この石が積まれたのはいつかっていうと、１番目の石が積まれる前です。
こんな感じで、後から積まれた石ほど先に取り出される。という性質になっています。
これが後入れ先出しという言葉の意味です！！
データでのスタック
このLIFOの特性を持つ、データを格納する構造のことをスタックと言います。
具体的には以下の図のような感じですね。
数字がその要素を持つ値ってことです。
石の例と同様に一番外側の要素のみを取りだしたり、そこに要素を付け加えたりすることができます。これを実装していく感じですね。
ちなみに、スタックにおいて要素を取り出すことをpop、要素を付け加えることをpushと呼びます。
以下のコード実装では関数名などでpop、pushを多用しているので注意してください！！
コードの実装
やっていきましょう。
いつもどおり構造体の定義から関数の順でやっていきま
構造体の定義
スタックが普通の配列と違う点は常にtop(一番上の要素)の位置情報を持つことです。
つまり普通の配列とint型の変数topを持たせます。
配列は要素が全て入るように大きめにマクロで定義したmaxを用いて、date[max]としてます。
typedef struct stack{
int date[max];
int top;
}stack;
注意する点は
構造体自体を配列にするのではなく、
一つの構造体の中に配列型のデータを持つ。
ということです。
そうすることで一つのint型を一つの配列で共有することが実現できました。
push関数
スタックに数値を積み上げるpush関数を作ります。
void push(stack *p){
int v;
if(p->top >= max-1){
printf("これ以上積めません\n");
}else{
printf("pushする値を入力してください:");
scanf("%d",&v);
p->top++;
p->date[p->top] = v;
}
}
とりあえず仮引数のスタックの構造体はポインタで渡します。
中身のデータを変えるからね。
おさらいですが、topは現在入っている一番新しい数値の添字です。
まずif文です。
if(p->top >= max-1)これはtop(先頭の要素の位置)がmax-1、つまり配列の最大の添字以上かどうかを確認しています。
もし以上ならこれ以上pushできないので、何もしません。
そうでない場合(まだ配列に余裕がある場合)は新しい値を先頭の要素として追加していくことになります。
p->top++;
p->date[p->top] = v;とりあえずp->top++としてtopをインクリメントですね。
その後、配列dateのtopの位置に新しい値を入れていきます。
これで先頭に要素を追加したことになっています。
pop関数
次はスタックから数値を取り上げるpop関数です
void pop(stack *p){
if(p->top <= -1)
printf("これ以上取り出せません");
else{
p->date[p->top] = 0;
p->top--;
}
}こちらも同様に仮引数は構造体のポインタですね。
まずはif文です。
if(p->top <= -1)前提として、配列の添字が0から始まることを利用して、
topが-1の時はスタックに要素が一つもないということにしています。
このif文のtopが-1以下かどうかという判定がまさにそうですね。
もし-1以下なら何もしない、
そうでない場合(スタックに少なくとも一つは要素がある場合)は要素を取りだしていきます。
p->date[p->top] = 0;
p->top--;配列dateのtopの位置(現在の先頭)の値を0に変更。
その後topをデクリメントしてます。
これで先頭の要素が一つ取り出されたことになります。
show関数
スタックの現在の中身を表示する関数です。
void show(stack *p){
printf("stack:");
for(int i=p->top; i >= 0; i--)
printf("%3d",p->date[i]);
printf("\n\n");
}これも仮引数はポインタで渡して
for文はtopから0に向かう方向で表示しています。
スタックの初期設定を行う関数
スタックを定義した後にかける関数です。
void init(stack *p){
p->top = -1;
for(int i=0; i<max; i++)
p->date[i] = 0;
}popのところでも言った通り、topの位置を-1としてます。
これは初期の状態では値がないからですね。
そんで配列の中身を全部0にしています。NULLだと動作が怖いので,,,
全体のコードと動作確認
全体のコードです。
#include <stdio.h>
#include <stdlib.h>
#define max 5
typedef struct stack{
int date[max];
int top;
}stack;
void init(stack *p){
p->top = -1;
for(int i=0; i<max; i++)
p->date[i] = 0;
}
void push(stack *p){
int v;
if(p->top >= max-1){
printf("これ以上積めません\n");
}else{
printf("pushする値を入力してください:");
scanf("%d",&v);
p->top++;
p->date[p->top] = v;
}
}
void pop(stack *p){
if(p->top <= -1)
printf("これ以上取り出せません\n");
else{
p->date[p->top] = 0;
p->top--;
}
}
void show(stack *p){
printf("stack:");
for(int i=p->top; i >= 0; i--)
printf("%3d",p->date[i]);
printf("\n\n");
}
int main(int argc, const char * argv[]) {
int sw;
stack S;
init(&S);
while(1){
printf("何を行いますか？\n");
printf("0:push 1:pop 2:exit\n:");
scanf("%d",&sw);
switch(sw){
case 0: push(&S); show(&S); break;
case 1: pop(&S); show(&S); break;
case 2: exit(0); break;
}
}
}
main関数ではwhile文で基本的に無限ループです。
exit関数はプログラムを終了する関数で、stdlib.hをインクルードする必要があります。
実際に動かすと
おｋ
てことで今回はここまで。
ではまた〜
コメント