logo

スタックとは何ですか?

スタックは、次の線形データ構造です。 LIFO (後入れ先出し) 原理。スタックには 1 つの端がありますが、キューには 2 つの端があります ( フロントとリア )。ポインタが 1 つだけ含まれています トップポインタ スタックの最上位の要素を指します。要素がスタックに追加されるときは常にスタックの先頭に追加され、要素はスタックからのみ削除できます。言い換えれば、 stack は、スタックの最上部と呼ばれる一方の端から挿入と削除を実行できるコンテナとして定義できます。

スタックに関連するいくつかの重要なポイント

  • 現実世界のスタック、本の山などのように動作するため、スタックと呼ばれます。
  • スタックは、事前定義された容量を持つ抽象データ型です。つまり、限られたサイズの要素を格納できます。
  • これは、ある順序に従って要素を挿入および削除するデータ構造であり、その順序は LIFO または FILO です。

スタックの働き

スタックは LIFO パターンで動作します。以下の図からわかるように、スタックには 5 つのメモリ ブロックがあります。したがって、スタックのサイズは 5 です。

文字列ビルダーJava

要素をスタックに格納したいと考え、スタックが空であると仮定しましょう。以下に示すようにサイズ 5 のスタックを取得し、スタックがいっぱいになるまで要素を 1 つずつプッシュしています。

DS スタックの概要

スタックのサイズが 5 であるため、スタックはいっぱいになっています。上記の場合、スタックに新しい要素を入力するときに、スタックが上から下に移動していることがわかります。スタックは下から上に向かって埋められます。

スタックに対して削除操作を実行する場合、もう一方の端が閉じられているため、出入りする方法は 1 つだけです。これは LIFO パターンに従います。つまり、最初に入力された値が最後に削除されます。上記の場合、値 5 が最初に入力されるため、他のすべての要素が削除された後でのみ削除されます。

標準的なスタック操作

以下は、スタックに実装される一般的な操作の一部です。

    押す():スタックに要素を挿入するときの操作はプッシュと呼ばれます。スタックがいっぱいになると、オーバーフロー状態が発生します。ポップ():スタックから要素を削除するときの操作はポップと呼ばれます。スタックが空の場合は、スタックに要素が存在しないことを意味し、この状態はアンダーフロー状態と呼ばれます。isEmpty():スタックが空かどうかを判断します。一杯():スタックがいっぱいかどうかを判断します。ピーク():指定された位置にある要素を返します。カウント():スタック内で使用可能な要素の合計数を返します。変化():指定された位置の要素を変更します。画面():スタック内で使用可能なすべての要素を出力します。

PUSH動作

PUSH 操作に含まれる手順は次のとおりです。

変更して列を追加します。
  • 要素をスタックに挿入する前に、スタックがいっぱいかどうかを確認します。
  • 要素をスタックに挿入しようとしたときにスタックがいっぱいの場合、 オーバーフロー という状態が発生します。
  • スタックを初期化するとき、スタックが空であることを確認するために、top の値を -1 に設定します。
  • 新しい要素がスタックにプッシュされると、まず先頭の値がインクリメントされます。 トップ=トップ+1、 要素は新しい位置に配置されます。
  • 要素は、次の位置に到達するまで挿入されます。 最大 スタックのサイズ。
DS スタックの概要

POP操作

POP 操作に関連する手順は次のとおりです。

  • スタックから要素を削除する前に、スタックが空かどうかを確認します。
  • 空のスタックから要素を削除しようとすると、 アンダーフロー という状態が発生します。
  • スタックが空でない場合は、まず、
  • ポップ操作が実行されると、先頭が 1 減算されます。 トップ=トップ-1
DS スタックの概要

スタックの応用例

スタックの用途は次のとおりです。

    シンボルのバランス調整:スタックはシンボルのバランスを取るために使用されます。たとえば、次のようなプログラムがあります。
 int main() { cout&lt;<'hello'; cout<<'javatpoint'; } < pre> <p>As we know, each program has <em>an opening</em> and <em>closing</em> braces; when the opening braces come, we push the braces in a stack, and when the closing braces appear, we pop the opening braces from the stack. Therefore, the net value comes out to be zero. If any symbol is left in the stack, it means that some syntax occurs in a program.</p> <ul> <tr><td>String reversal:</td> Stack is also used for reversing a string. For example, we want to reverse a &apos; <strong>javaTpoint</strong> &apos; string, so we can achieve this with the help of a stack. <br> First, we push all the characters of the string in a stack until we reach the null character. <br> After pushing all the characters, we start taking out the character one by one until we reach the bottom of the stack. </tr><tr><td>UNDO/REDO:</td> It can also be used for performing UNDO/REDO operations. For example, we have an editor in which we write &apos;a&apos;, then &apos;b&apos;, and then &apos;c&apos;; therefore, the text written in an editor is abc. So, there are three states, a, ab, and abc, which are stored in a stack. There would be two stacks in which one stack shows UNDO state, and the other shows REDO state. <br> If we want to perform UNDO operation, and want to achieve &apos;ab&apos; state, then we implement pop operation. </tr><tr><td>Recursion:</td> The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained. </tr><tr><td>DFS(Depth First Search):</td> This search is implemented on a Graph, and Graph uses the stack data structure. </tr><tr><td>Backtracking:</td> Suppose we have to create a path to solve a maze problem. If we are moving in a particular path, and we realize that we come on the wrong way. In order to come at the beginning of the path to create a new path, we have to use the stack data structure. </tr><tr><td>Expression conversion:</td> Stack can also be used for expression conversion. This is one of the most important applications of stack. The list of the expression conversion is given below: <pre>Infix to prefix Infix to postfix Prefix to infix Prefix to postfix Postfix to infix</pre> </tr><tr><td>Memory management:</td> The stack manages the memory. The memory is assigned in the contiguous memory blocks. The memory is known as stack memory as all the variables are assigned in a function call stack memory. The memory size assigned to the program is known to the compiler. When the function is created, all its variables are assigned in the stack memory. When the function completed its execution, all the variables assigned in the stack are released. </tr></ul> <hr></'hello';>
メモリ管理:スタックはメモリを管理します。メモリは連続したメモリ ブロックに割り当てられます。すべての変数が関数呼び出しスタック メモリに割り当てられるため、メモリはスタック メモリとして知られています。プログラムに割り当てられたメモリ サイズは、コンパイラに認識されます。関数が作成されると、そのすべての変数がスタック メモリに割り当てられます。関数の実行が完了すると、スタックに割り当てられていたすべての変数が解放されます。