スタック構成、動作の仕組みと実用的な応用

スタックは重要なデータ構造であり、配列よりも複雑な仕組みを提供し、計算を高速化し、プログラミング時の利便性を生み出すのに役立ちます。それでは、スタックとは何か、スタック構成の意味、どのようなときに使うのかを調べてみましょう。 

1.スタックとは？ 

プログラマーになりたての人は、スタックとはどういう意味なのかと疑問に思うだろう。それは頂上（top）と呼ばれる一方の端でのみデータの追加・削除が行われる特殊な線形リストです。 

もう一つの定義は、「Last In First Out（LIFO）」（後入れ先出し）の原則に基づいて動作する抽象的なデータ構造であるということです。  

実際の例：ケーキを箱に入れるとき、箱の上にケーキをひとつずつ置いていきますので、この動作はスタックのpushと同じです。ケーキを取り出したいときは、スタックのpopと同じように、まず一番上のケーキを取り出さなければなりません。 

スタックはコンテナのようなデータ構造で、ノードと呼ばれる要素を含んでいます。基本的な操作は2つあります。 

・push：スタックの一番上に要素を追加します。つまり、その要素はすでにスタックにある要素の後に追加されます。 

・pop：スタックの一番上にある要素を取り出して返します。この要素は、取り出される以上、スタックから削除されます。 

それに、スタックが空かどうかをチェックするisEmpty()や、スタックから削除せずに最初の要素の値を返すTop()などの追加操作もあります。 

>>> もっと見る: オフショア開発 

2. スタックオーバーフローの原因 

プログラミングにおいて、スタックオーバーフローは、スタックポインタがスタックの限界を超えたときに発生します。スタックは通常、有限のアドレス空間から構成され、通常はプログラムの開始時点から決定されます。スタックのサイズは、プログラム、プログラミング言語、アーキテクチャ、シングル・マルチスレッド、利用可能なメモリ量など、様々なな要因によって決まります。 

プログラムが、利用可能なメモリよりも多くのメモリをオーバーロードしようとするとき（つまり、プログラムがスタックの境界を超えたメモリ領域にアクセスしようとしてバッファオーバーフローを起こすとき）、スタックがオーバーフローとみなされ、多くの場合にエラーや予想しないプログラムの動作につながります。 

3. スタックの表現 

このセクションでは、スタックを表現するための配列と連結リストという2つの方法を紹介します。両者の共通点と相違点を見てみましょう。 

3.1. 配列によるスタックの表現 

配列で表現する場合、以下のような特徴があります。 

• 要素を追加することは、配列の末尾に要素を追加することと同じです。 
• スタックから要素を削除する場合、これは配列の末尾から要素を削除するということです。 
• すでに満杯の配列に追加されるとスタックの構成はオーバーフローになります。 
• 配列の実際の要素数が0のとき、スタックは空であるとみなされます。 

3.2. 単一連結リストを使ったスタックの表現 

単一連結リストを使って表現する場合、次のような特徴もあります。 

• ITスタックに要素を追加する場合、これはリストの末尾に要素を追加すること（insertlast）と同じです。 
• スタックから要素を削除することは、リストの末尾から要素を削除することと同じです。 
• 構成がオーバーフローするのは、変数用のメモリ・スペースが新しい要素を追加するのに十分でない場合です。しかし、このチェックは非常に複雑で、コンピューターやプログラミング言語に依存します。そのため、デプロイ時にはスタックオーバーフローのチェックを省略することができます。 

知っておくべきスタックの基本操作 

スタック・データ構造に対する基本的な操作は、初期化、使用、そして削除です。これらの基本操作に加えて、スタックには以下のような概念に関連する2つの基本操作もあります。 

• push()の操作：スタックの先頭に要素を追加します。 
• pop()の操作：スタックの先頭から要素を削除します。 

>>> もっと見る: ベトナムIT企業トップ10 

4. スタックの基本操作 

データがスタックにpushされたら、スタックを効果的に使うために、スタックの状態をチェックする必要があります。これを最も正確に行うために、スタックの他のサポート機能を見てみましょう。 

• peek()操作：スタックの一番上にある要素を、削除せずに取得します。 
• isFull()操作：スタックが満杯かどうかをチェックします。 
• isEmpty()操作：スタックが空かどうかをチェックします。 

常に、スタックの先頭にプッシュされたデータ要素へのポインタを保持します。このポインタは常にスタックの先頭要素の位置を表し、しばしば「top」と呼ばれます。topポインタは、pop 操作を行わずにスタックの先頭要素の値を提供します。 

5. スタック構成とは？ 

ソフトウェア・スタック構成とは？以下は、スタック上で行われている動作を示すスタック図です。 

スタックは、配列、構造体、ポインター、連結リストによってうまく実装できます。 

スタックには固定サイズと変更可能サイズという2種類があります。以下では、配列を使って固定サイズのスタックを実装します。

>>> もっと見る: オフショア開発とは？ オフショア開発のメリットと適切なオフショア開発企業の見つけ方を解説

6. 配列を使ったスタックの実装 

このチュートリアルでは、スタック・データ構造の各操作を詳しく説明し、配列を使ってスタックを実装します。次のセクションでは、他の実装方法を紹介します。  

そのテクニックを分析し、スタックを作成するために int 型の 1 次元配列と、サイズを格納する capacity 変数、先頭要素のインデックスを記録する top 変数を使用します。 

6.1. スタックが満杯かどうかを判定する (IsFull) 

この関数はスタックが満杯かどうかを判定します。先頭のインデックスが capacity – 1 に等しければ、満杯と判定されます。 

bool IsFull(int capacity){ 

if(top >= capacity – 1){ 

     return true; 

}else{ 

     return false; 

} 

} 

6.2. スタックが空かどうかを判定する (IsEmpty) 

要素がない場合は、top = -1として付与してマークします。したがって、スタックが空かどうかを判定するには、topの値を-1と比較して判定します。 

bool IsEmpty(){ 

if(top == -1){ 

     return true; 

}else{ 

     return false; 

} 

} 

6.3. スタックの一番上に要素を追加する (Push) 

スタックが満杯でない場合のみ、スタックの一番上にプッシュ（要素を追加）することができます。スタックが満杯の場合は、プッシュを実行せずに通知します。そうでなければ、topを1つ増やし、一番上のインデックスの要素に値を付与します。 

void Push(int stack[], int value, int capacity){ 

if(IsFull(capacity) == true){ 

     printf(“nStack is full. Overflow condition!”); 

}else{ 

     ++top; 

     stack[top] = value; 

} 

} 

6.4. スタックの先頭から要素を取り除く(Pop) 

スタックが空でない場合のみ、スタックの先頭からポップ（要素を取り除く）ができます。スタックが空なら、ポップせずに通知します。そうでなければ、先頭を1つ減らします。 

void Pop(){ 

if(IsEmpty() == true){ 

     printf(“nStack is empty. Underflow condition!”); 

}else{ 

     –top; 

} 

} 

6.5. 一番上にある要素の値を取得する（Top） 

スタックの一番上にある要素の値を得るには、以下の簡単な操作を使います。 

int Top(int stack[]){ 

return stack[top]; 

}  

6.6. スタックの要素数を取得する（Size） 

変数topには、スタックの最大のインデックスが保存されているため、スタックのサイズを得るのは簡単です。 

int Size(){ 

return top + 1; 

} 

結果として、以下のようにインストールされたプログラムスタックができました。 

#include <stdio.h> 

int top = -1;  

bool IsFull(int capacity){ 

if(top >= capacity – 1){ 

     return true; 

}else{ 

     return false; 

} 

}   

bool IsEmpty(){ 

if(top == -1){ 

     return true; 

}else{ 

     return false; 

} 

}   

void Push(int stack[], int value, int capacity){ 

if(IsFull(capacity) == true){ 

     printf(“nStack is full. Overflow condition!”); 

}else{ 

     ++top; 

     stack[top] = value; 

} 

}   

void Pop(){ 

if(IsEmpty() == true){ 

     printf(“nStack is empty. Underflow condition!”); 

}else{ 

     –top; 

} 

}   

int Top(int stack[]){ 

return stack[top]; 

} 

int Size(){ 

return top + 1; 

}   

int main(){ 

int capacity = 3;  

int top = -1;  

int stack[capacity];   

// pushing element 5 in the stack . 

Push(stack, 5, capacity);       

printf(“nCurrent size of stack is %d”, Size());     

Push(stack, 10, capacity); 

Push(stack, 24, capacity);    

printf(“nCurrent size of stack is %d”, Size());   

// As the stack is full, further pushing will show an overflow condition. 

Push(stack, 12, capacity);     

//Accessing the top element 

printf(“nThe current top element in stack is %d”, Top(stack));     

//Removing all the elements from the stack 

for(int i = 0 ; i < 3;i++) 

     Pop(); 

printf(“nCurrent size of stack is %d”, Size());  

//As the stack is empty , further popping will show an underflow condition. 

Pop();   

}   

上記プログラムを実行した結果は下記になります。 

Current size of stack is 1 

Current size of stack is 3 

Stack is full. Overflow condition! 

The current top element in stack is 24 

Current size of stack is 0 

Stack is empty. Underflow condition! 

7. スタックの実用的な応用 

スタックを実際に応用する場合の意味を、以下の情報を通して学ぶましょう。 

文字列を反転する：文字列をスタックに入力し、スタックの先頭から1つずつ要素を取り出します。こうして、反転した文字列が取得されます。 

数字を10進法から2進法に変換する：余りn%2を取ってスタックに格納し、n=n/2 を代入します。n=1になるまでこの処理を続け、ここにも保存します。次に、要素を1つずつ取得し、nの2進文字列を取得します。 

この記事を通して、スタックとそれが実際に何に使われるのか、スタック開発の意味とそれがもたらす機会について、理解していただけただろうか。 

スタック技術や、学習しているプログラミング言語に関する知識に基づいて、スタックを実装して、スタックについてよりよく理解できるようにしましょう。次回は、今日最も発展している技術の意味を紹介します。