Javaスタックとキューを実装する方法-＆＃＆チュートリアル-php.cn

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

WBOY

リリース： 2023-04-18 15:52:03

転載

829 人が閲覧しました

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

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

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

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

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

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

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

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

スタック

このデータ構造は、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 サイトの他の関連記事を参照してください。