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

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

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

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

スタック表現

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

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

基本操作

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

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

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

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

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

常に、スタック上の最後のPUSHされたデータへのポインターを維持します。このポインタは常にスタックの最上位を表すため、top。ザ・top ポインタは、実際にスタックを削除せずに、スタックの最上位値を提供します。

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

ピーク（）

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

begin procedure peek
   return stack[top]
end procedure

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

Example

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

一杯（）

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

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

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

Example

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で初期化します。したがって、topが0または-1を下回っているかどうかを確認して、スタックが空かどうかを判断します。これがコードです-

Example

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

プッシュ操作

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

Step 1 −スタックがいっぱいかどうかを確認します。
Step 2 −スタックがいっぱいの場合、エラーが発生して終了します。
Step 3 −スタックがいっぱいでない場合は、増分します top 次の空きスペースをポイントします。
Step 4 −topが指しているスタック位置にデータ要素を追加します。
Step 5 −成功を返します。

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

PUSH操作のアルゴリズム

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

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

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

Example

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

ポップオペレーション

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

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

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

ポップ演算のアルゴリズム

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

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

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

Example

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プログラミング言語の完全なスタックプログラムについては、ここをクリックしてください。