Javaスタックとキューを実装する方法

スタックとキュー

1. スタックは後入れ先出し (LIFO) データ構造です

2. キューは先入れ先出しです-out (FIFO) 構造

スタック

スタックは線形構造であり、配列と比較すると、スタックに対応する演算は配列のサブセットです。

一方の端からのみ要素を追加でき、一方の端からのみ要素を削除できます (この端はスタックの最上位と呼ばれます)。

スタックは広く使用されているデータ構造であり、コンピュータの使用においては、コンパイラの字句解析、Java 仮想マシン、ソフトウェアの元に戻す操作 (Undo)、ブラウジングなど、広く使用されています。コンパイラでのロールバック操作、コンパイラでの関数呼び出し実装など。

スタック実装

#O(1) #E Pop()均等に分散 E Peak( )int getSize()boolean isEmpty()注: プッシュ操作とポップ操作は最後に実行されるため、サイズ変更がトリガーされる可能性がありますが、均等に O(1) とみなされます。

インターフェイス	説明	複雑さ
void Push(E e)	スタックに要素を追加	均等に分割
スタックの最上位要素をポップします	O(1)
スタックの最上位要素を表示	O(1)
Getスタック内の要素の数	O(1)
スタックが空かどうかを判断します	O(1)

時間計算量の分析についてさらに詳しく知りたい場合は、著者が後で更新する記事に注目してください:

O(n) はどのような問題を説明しますか?
スタックは配列またはリンク リストを通じて実装できます。ここでは配列を使用して上記のインターフェイスを実装します。

スタックの設計では、ユーザーはスタックの最上位要素へのアクセスとスタック長のみに注意を払うため、設計コードは次のとおりです。

読者は

スタック

このデータ構造は、LeetCode の問題番号 20: 有効な括弧を解決するために使用されます。毎日の計算: 有効な括弧も確認できます。 Queue

キューも線形データ構造であり、配列と比較すると、キューに対応する操作は配列のサブセットです。

要素は一方の端 (キューの最後) からのみ追加でき、要素はもう一方の端 (キューの先頭) からのみ取り出せます。

キューの適用は、プレーヤー上のプレイリスト、データ ストリーム オブジェクト、非同期データ送信構造 (ファイル IO、パイプ通信、ソケットなど) に反映できます。もちろん、最も直感的なのはキューです。 . .

キューの実装

インターフェイスvoid enqueue(E e) 均等分散 #E dequeue()##E getFront()チームの最初の要素を取得しますO(1)#キュー要素の数を取得##O(1)##O(1)

説明	複雑さ
Enqueue	O(1)
Dequeue	O(n)
		#int getSize()
	boolean isEmpty()	キューが空かどうかを判定
	Enterキュー キューの最後から開始してサイズ変更がトリガーされる可能性があるため、均等に分散されるのは O(1) です。デキューはキューの先頭で行われ、配列の実装では毎回 O(n) ごとにすべての要素を移動する必要があります。

以上がJavaスタックとキューを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。