データ構造とアルゴリズム-スタック

スタックは、ほとんどのプログラミング言語で一般的に使用される抽象データ型（ADT）です。それは、実世界のスタックのように動作するため、スタックと呼ばれます。たとえば、カードのデッキやプレートの山などです。

実際のスタックでは、片側のみで操作が可能です。たとえば、スタックの上部からのみカードまたはプレートを配置または削除できます。同様に、スタックADTでは、すべてのデータ操作を一方の端でのみ許可します。常に、スタックの最上位要素にのみアクセスできます。

この機能により、LIFOデータ構造になります。 LIFOは後入れ先出しの略です。ここでは、最後に配置（挿入または追加）された要素が最初にアクセスされます。スタックの用語では、挿入操作は PUSH 操作と呼ばれ、削除操作は POP 操作と呼ばれます。

スタック表現

次の図は、スタックとその操作を示しています-

スタック表現

スタックは、配列、構造、ポインター、およびリンクリストによって実装できます。スタックは固定サイズにすることも、動的にサイズ変更することもできます。ここでは、配列を使用してスタックを実装します。これにより、固定サイズのスタック実装になります。

基本操作

スタック操作には、スタックの初期化、使用、および初期化解除が含まれます。これらの基本的なものとは別に、スタックは次の2つの主要な操作に使用されます-

* push（）*-スタック上の要素をプッシュ（保存）します。
* pop（）*-スタックから要素を削除（アクセス）します。

データがスタックにプッシュされたとき。

スタックを効率的に使用するには、スタックのステータスも確認する必要があります。同じ目的で、次の機能がスタックに追加されます-

* peek（）*-スタックの最上位データ要素を削除せずに取得します。
* isFull（）*-スタックがいっぱいかどうかを確認します。
* isEmpty（）*-スタックが空かどうかを確認します。

常に、スタック上の最後のプッシュされたデータへのポインターを維持します。このポインターは常にスタックの最上部を表すため、 top という名前が付けられます。 top ポインターは、実際にスタックを削除することなく、スタックの最高値を提供します。

まず、スタック機能をサポートする手順について学ぶ必要があります-

ピーク（）

peek（）関数のアルゴリズム-

begin procedure peek
   return stack[top]
end procedure

Cプログラミング言語でのpeek（）関数の実装-

例

int peek() {
   return stack[top];
}

一杯（）

isfull（）関数のアルゴリズム-

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif

end procedure

Cプログラミング言語でのisfull（）関数の実装-

例

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

isempty（）

isempty（）関数のアルゴリズム-

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif

end procedure

Cプログラミング言語でのisempty（）関数の実装はわずかに異なります。配列のインデックスは0から始まるため、topを-1で初期化します。そのため、スタックが空かどうかを判断するために、トップが0または-1未満かどうかを確認します。ここにコードがあります-

例

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

プッシュ操作

新しいデータ要素をスタックに配置するプロセスは、プッシュ操作と呼ばれます。プッシュ操作には、一連のステップが含まれます-

*ステップ1 *-スタックがいっぱいかどうかを確認します。
*ステップ2 *-スタックがいっぱいの場合、エラーを生成して終了します。
ステップ3 *-スタックが満杯でない場合、 *top をインクリメントして次の空きスペースを指します。
*ステップ4 *-topが指しているスタック位置にデータ要素を追加します。
*ステップ5 *-成功を返します。

スタックプッシュ操作

リンクリストを使用してスタックを実装する場合は、手順3でスペースを動的に割り当てる必要があります。

PUSH操作のアルゴリズム

プッシュ操作の簡単なアルゴリズムは、次のように導出することができます-

begin procedure push: stack, data

   if stack is full
      return null
   endif

   top ← top + 1
   stack[top] ← data

end procedure

Cでのこのアルゴリズムの実装は非常に簡単です。次のコードを参照してください-

例

void push(int data) {
   if(!isFull()) {
      top = top &plus; 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

ポップ操作

スタックからコンテンツを削除しながらコンテンツにアクセスすることを、ポップ操作と呼びます。 pop（）操作の配列実装では、データ要素は実際には削除されず、代わりに top がスタック内の下位位置までデクリメントされ、次の値を指します。しかし、リンクリストの実装では、pop（）は実際にデータ要素を削除し、メモリ空間の割り当てを解除します。

ポップ操作には、次の手順が含まれる場合があります-

*ステップ1 *-スタックが空かどうかを確認します。
*ステップ2 *-スタックが空の場合、エラーを生成して終了します。
ステップ3 *-スタックが空でない場合、 *top が指しているデータ要素にアクセスします。
*ステップ4 *-topの値を1減らします。
*ステップ5 *-成功を返します。

スタックポップ操作

ポップ操作のアルゴリズム

ポップ操作の簡単なアルゴリズムは、次のように導出することができます-

begin procedure pop: stack

   if stack is empty
      return null
   endif

   data ← stack[top]
   top ← top - 1
   return data

end procedure

Cでのこのアルゴリズムの実装は、次のとおりです-

例

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

Cプログラミング言語の完全なスタックプログラムについては、リンクしてください：/data_structures_algorithms/stack_program_in_c [ここをクリック]。

Data-structures-algorithms-stack-algorithm

目次

データ構造とアルゴリズム-スタック

スタック表現

基本操作

ピーク（）

一杯（）

isempty（）

プッシュ操作

PUSH操作のアルゴリズム

ポップ操作

ポップ操作のアルゴリズム