データ構造は、データ値、それらの間の関係、およびデータに適用できる関数または操作のコレクションです。現在、利用可能なデータ構造がたくさんあります。しかし、今日はスタックデータ構造に焦点を当てます。次のトピックについて説明します。
なぜデータ構造なのか？
これに答えるには、大きなレベルで考える必要があります。 Googleマップがほんの数秒で最適なルートを表示する方法、マイクロ秒で検索結果を返す方法を考えてみてください。 100のWebサイトだけを処理するのではなく、10億を超えるサイトを処理し、それでも非常に迅速に結果を表示します。
パブリック文字列tostring（）
使用されるアルゴリズムは重要な役割を果たしますが、使用されるデータ構造またはコンテナーがそのアルゴリズムの基盤です。どのアプリケーションでも、データをその使用法に最も適した方法または構造で編成および保存することが、データへの効率的なアクセスと処理の鍵となります。
データ構造の種類
データを効率的に処理するために使用できるいくつかの標準的なデータ構造があります。アプリケーションに合わせて、カスタマイズしたり、まったく新しいものを作成したりすることもできます。
スタックデータ構造とは何ですか？
実際の例をいくつか考えてみましょう。
- 貨物での出荷
- トレイ上のプレート
- コインのスタック
- 引き出しのスタック
- 車両基地での列車の入換
これらの例はすべて、 最初のうちの最後の 戦略。トレイ上のプレートを検討してください。プレートを選択する場合は、上からプレートを選択する必要がありますが、プレートがトレイに保持されている場合は、逆の順序にする必要があります。以下の例は 後入れ先出し（LIFO） 原理はとして知られています スタック 。
補完的な操作とは別に、スタックで可能な主な操作は次のとおりです。
- 要素をスタックの一番上にプッシュまたは挿入します
- スタックの一番上から要素をポップまたは削除します
スタックデータ構造の作成
クラススタック：def __init __（self、max_size）：self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- max_size スタックで予想される要素の最大数です。
- スタックの要素はPythonリストに保存されます。
- Topは、空のスタックをマークするために最初に-1と見なされるスタックの最上位のインデックスを示します。
スタックの初期ステータスは、max_size = 5の図で確認できます。
要素をスタックにプッシュする
さて、要素をスタックに入力またはプッシュしたい場合は、それを覚えておく必要があります
- 上部は、要素が挿入されるインデックスを指します。
- また、スタックがいっぱいの場合、つまりmax_size = topの場合、要素は挿入されません。
では、アルゴリズムはどうあるべきですか？
＃スタックの最大サイズを返しますdef get_max_size（self）：return self .__ max_size＃スタックがいっぱいかどうかに関係なくブール値を返します。いっぱいの場合はTrue、それ以外の場合はFalse def is_full（self）：return self.get_max_size（）-1 == self .__ top＃スタックの最上位にある要素をプッシュしますdefpush（self、data）：if（self.is_full（））：print（ 'スタックはすでにいっぱいです'）else：self .__ top = self .__ top + int（1 ）self .__ elements [self .__ top] = data＃以下の__str __（）を使用して、def __str __（self）のデバッグ中にDSオブジェクトの要素を出力できます。msg= [] index = self .__ top while（index> = 0）：msg.append（（str）（self .__ elements [index]））index- = 1 msg = '' .join（msg）msg = 'スタックデータ（上から下）：' + msg return msg
ここで、以下を実行すると：
stack1 = Stack（4）
＃必要なすべての要素をプッシュします。
stack1.push（ 'A'）
stack1.push（ 'B'）
stack1.push（ 'C'）
stack1.push（ 'E'）
print（stack1.is_full（））
print（stack1）
出力：
スタックはすでにいっぱいです
本当
スタックデータ（上から下）：D C B A
スタックから要素をポップ
ここで、要素をスタックに挿入したので、それらをポップしたいので、次のことに注意する必要があります。
- スタックは空ではありません。つまり、トップ！= -1
- データを削除する場合、最上位はスタックの前の最上位を指している必要があります。
では、アルゴリズムはどうなるのでしょうか？
＃スタックが空かどうかに関係なくブール値を返します。空の場合はTrue、そうでない場合はFalse def is_empty（self）：return self .__ top ==-1＃ポップされた値を返しますdef pop（self）：if（self.is_empty（））： print（ '何もポップせず、すでに空です'）else：a = self .__ elements [self .__ top] self .__ top = self .__ top-1は、＃displayすべてのスタック要素を上から下に表示しますdef display（self）： for i in range（self .__ top、-1、-1）：print（self .__ elements [i]、end = ''）print（）
ここで、以前に作成したスタックを考慮して、要素をポップしてみてください
print（stack1.pop（））
print（stack1.pop（））
print（stack1）
print（stack1.pop（））
print（stack1.pop（））
print（stack1.pop（））
出力：
D
C
スタックデータ（上から下）：B A
B
に
ポップするものはなく、すでに空です
スタックデータ構造のアプリケーション
- 例1：
スタックは、算術式の評価のためのブラケットマッチングアルゴリズムの実装、およびメソッド呼び出しの実装に使用されます。
答えは5です。
- 例2：
Windowsのクリップボード 2つのスタックを使用して、元に戻す-やり直し（ctrl + z、ctrl + y）操作を実装します。あなたはMS-Word、メモ帳などのWindowsワードエディタで働いていたでしょう。これはMS-Wordで書かれたテキストです。 Ctrl-ZとCtrl-Yをクリックするとテキストがどのように変化するかを観察します。
これは、元に戻す-やり直し操作をシミュレートするコードです。コードに目を通し、この実装でスタックがどのように使用されるかを観察します。
#creating class stack class Stack：def __init __（self、max_size）：self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full（self）：if（self .__ top == self .__ max_size-1）：return True return False def is_empty（self）：if（self .__ top ==-1）：return True return False def push（self、data）：if（self.is_full（））：print （ 'スタックがいっぱいです!!'）else：self .__ top + = 1 self .__ elements [self .__ top] = data def pop（self）：if（self.is_empty（））：print（ 'スタックが空です！ ！ '）else：data = self .__ elements [self .__ top] self .__ top- = 1 return data def display（self）：if（self.is_empty（））：print（'スタックが空です '）else：index = self .__ top while（index> = 0）：print（self .__ elements [index]）index- = 1 def get_max_size（self）：return self .__ max_size＃以下の__str __（）を使用して、の要素を出力できます。 def __str __（self）のデバッグ中のDSオブジェクト：msg = [] index = self .__ top while（index> = 0）：msg.append（（str）（self .__ elements [index]））index- = 1 msg = ' '.join（msg）msg ='スタックデータ（上から下）： '+ msg return ms g＃removeまたはbackspace操作を実装する関数defremove（）：global clipboard、undo_stack data = clipboard [len（clipboard）-1] clipboard.remove（data）undo_stack.push（data）print（ 'Remove：'、clipboard） ＃元に戻す操作を実装する関数def undo（）：グローバルclipboard、undo_stack、redo_stack if（undo_stack.is_empty（））：print（ '元に戻すデータがありません'）else：data = undo_stack.pop（）clipboard.append（ data）redo_stack.push（data）print（ 'Undo：'、clipboard）＃REDO操作を実装する関数def redo（）：グローバルクリップボード、undo_stack、redo_stack if（redo_stack.is_empty（））：print（ 'データがありませんto redo '）else：data = redo_stack.pop（）if（データがクリップボードにありません）：print（'やり直すデータがありません '）redo_stack.push（data）else：clipboard.remove（data）undo_stack.push（ data）print（ 'Redo：'、clipboard）clipboard = ['A'、 'B'、 'C'、 'D'、 'E'、 'F'] undo_stack = Stack（len（clipboard））redo_stack = Stack （len（clipboard））remove（）undo（）redo（）
出力：
削除：[「A」、「B」、「C」、「D」、「E」]
元に戻す：[「A」、「B」、「C」、「D」、「E」、「F」]
やり直し：[「A」、「B」、「C」、「D」、「E」]
これで、Pythonでのこのスタックデータ構造の記事は終わりです。コードを自分でうまく理解して実行した場合、Stacks DataStructureの初心者ではなくなります。
質問がありますか？この記事のコメントセクションにその旨を記載してください。できるだけ早くご連絡いたします。
Pythonとそのさまざまなアプリケーションに関する詳細な知識を得るには、ライブに登録できます。 24時間年中無休のサポートと生涯アクセス。