配列、リンクリスト、ハッシュテーブル、赤と黒の木（バイナリクエリツリー）など、以前にいくつかのデータ構造にさらされています。今日は、別のデータ構造、スタックを見てみましょう。
スタックとは何ですか？まず、例を見てみましょう。スタックは非常に狭い木製の樽に相当します。木製の樽に物を入れて物を取り出すと、最初に底に置いたものが、最初に取り出したものは、私たちがちょうど入れたものでした。口は1つしかなく、この口に要素を入れ、この口に要素を取り出します。次に、JDKのスタックを次に学びましょう。
1。ベクターとスタックの基本的な紹介と使用
まず、JDKの定義を見てみましょう。
パブリッククラススタック<e> extends vector <e> {上記から、スタックがベクトルから継承されていることがわかります。そのため、ベクターについての特定の理解も必要です。
ベクトル：スレッドセーフダイナミックアレイ
スタック：動的配列に基づいて実装されたスレッドセーフスタックであるベクトルを継承します。
1。ベクターとスタックの機能：
ベクトルとアレイリストは基本的に同じです。違いは、ベクトルがスレッドセーフであり、可能なスレッドセーフメソッドの前に同期されたキーワードを追加することです。
ベクトル：高速ランダムアクセス速度、挿入不良、除去性能（アレイの特性）;ヌル要素をサポートします。注文があります。要素を繰り返すことができます。スレッドセーフ;
スタック：アフターイン、ファーストアウト、いくつかの基本的なスタック操作方法を実装します（実際、ベクターから継承されるため、アフターイン、ファーストアウトだけでなく、多くの操作が存在する可能性があり、ある意味ではスタックではありません）。
2.ベクトルおよびスタック構造：
ベクトルクラス
基本的にArrayListと同じであり、残りの主な違いは次のとおりです。
1.ベクトルはスレッドセーフです
2。アレイリストの成長は、ベクターの成長と矛盾しています
その他、構築方法が一貫していない場合、ベクトルは建設方法を介して容量挿入を初期化でき、インデックスの方法などの他の方法があります。 Vectorは、指定された場所からの検索と検索をサポートします。さらに、Vectorには、AddElementやSetelementatメソッドなど、複製関数を備えたいくつかの冗長な方法もあります。この理由は、歴史的な理由によるものです。たとえば、AddElementメソッドは以前に残されています。コレクションフレームワークが導入されたとき、ベクターはコレクションファミリーに参加し、リストインターフェイスを実装するために変更されました。リストインターフェイスで定義されたいくつかのメソッドを実装する必要があります。ただし、互換性の理由から、古い方法を削除することはできないため、冗長性のある古いメソッドが表示されます。現在、それはArrayListに置き換えられており、基本的にはめったに使用されていないため、理解してください。
スタッククラス
スタックの基本操作が実現されます。この方法は次のとおりです。
public stack（）;
空のスタックを作成します
public同期e peek（）;
スタックの上部に値を返します。
public e push（e item）;
スタック操作;
public同期e pop（）;
アウトスタック操作。
public boolean empty（）;
スタックが空であるかどうかを判断します。
パブリック同期INT検索（オブジェクトO）;
スタック内のオブジェクトの位置を返します。
上記のスタックについては、基本的に上記の方法を頻繁に使用するだけです。ベクトルを継承し、多くの方法を持っていますが、基本的には使用されませんが、スタックとして扱われます。
3。基本的な使用
ベクトルのいくつかの方法は、次のように使用されます。さらに、ベクトルのトラバーサル方法は、ArrayListのトラバーサル方法と同じです。 Foreach、Iterator、およびLoop Traversalを使用できます。
Import java.util.arrays; Import java.util.iterator; import java.util.list; import java.util.listiterator; import java.util.vector; public static void main（string [] args）{vector <integer> vector = new vector <integer>（ for（int i = 0; i <10; i ++）{vector.add（i）; } // print system.out.println（vector.toString（））; // size（）system.out.println（vector.size（））; // system.out.println（vector.contains（2））; // iterator iterator <integer> iterator = vector.iterator（）; while（iterator.hasnext（））{system.out.print（iterator.next（） + ""）; } // toArray object [] objarr = vector.toarray（）; system.out.println（ "/nobjarr：" + arrays.aslist（objarr））; integer [] intarr = vector.toarray（new Integer [vector.size（）]）; system.out.println（ "intarr：" + arrays.aslist（intarr））; // vector.add（5）を追加します。 // vector.remove（5）を削除します。 System.out.println（vector）; // containsall system.out.println（vector.containsall（arrays.aslist（5,6）））; // addall vector.addall（arrays.aslist（555,666））; System.out.println（vector）; // removeall vector.removeall（arrays.aslist（555,666））; System.out.println（vector）; // addallメソッドvector.addall（5、arrays.aslist（666,666、6））; System.out.println（vector）; // Method System.out.println（vector.get（5））を取得します。 //メソッドvector.set（5、55）を設定します。 System.out.println（vector.get（5））; //メソッドvector.add（0、555）を追加します。 System.out.println（vector）; //メソッドvector.remove（0）を削除します。 System.out.println（vector）; // indexof method system.out.println（vector.indexof（6））; // lastIndexofメソッドSystem.out.println（vector.lastindexof（6））; // listiteratorメソッドlistiterator <integer> listiterator = vector.listiterator（）; system.out.println（listiterator.hasprevious（））; // listiterator（index）method listiterator <integer> ilistiterator = vector.listiterator（5）; system.out.println（ilistiterator.previous（））; // Sublist Method System.out.println（vector.sublist（5、7））; // clear vector.clear（）; System.out.println（vector）; }}スタックのいくつかの方法は、次のように使用されます。スタックはベクトルを継承するため、スタックはベクトルが使用できるメソッドを使用することもできます。以下には、Stackのユニークな方法の例をいくつか示しています。非常にシンプルで、スタックの基本的な操作です。ベクターのいくつかのトラバーサル方法に加えて、Stackには独自の独自のトラバーサルメソッドもあります（空の方法とPOPメソッドを使用して、スタックの上部から下部へのトラバーサルを実現します）：
Import java.util.stack; public class test {public static void main（string [] args）{stack <integer> stack = new stack <integer>（）; for（int i = 0; i <10; i ++）{stack.add（i）; } system.out.println（stack）; System.out.println（stack.peek（））; stack.push（555）; System.out.println（stack）; System.out.println（stack.pop（））; System.out.println（stack）; system.out.println（stack.empty（））; System.out.println（stack.search（6））; System.out.println（ "Stack Traversal："）; while（！stack.empty（））{system.out.print（stack.pop（） + ""）; }}}サブセクション：
ベクトルはスレッドセーフですが、パフォーマンスが低いです。通常、特別な要件がない限り、アレイリストが使用されます。
スタックをスタックとして使用する場合は、スタックのいくつかの操作を正直かつ厳密に追跡する必要があります。それ以外の場合、スタックを使用することは意味があり、ベクトルを使用する方が良いでしょう。
2。Vector＆Stackeの構造と基礎となるストレージ
パブリッククラスVector <e>拡張<e> abstractlist <e>を実装<e>、ランダムアクセス、クローン可能、java.io.serializable
Vectorはリストの実装クラスです。実際、ベクトルは、配列の実装に基づいたリストコンテナでもあります。その関数と実装コードは、基本的にArrayListと同じです。では、何が違うのでしょうか？ 1つは、配列が拡張されると、ベクトルが *2で、アレイリストは *1.5+1であることです。もう1つは、ベクトルがスレッドセーフであり、アレイリストはそうではないということです。ベクトルのスレッドセーフアプローチは、各メソッドに同期されたキーワードを追加して、それを確保することです。しかし、ここでは、ベクターはもはや公式にはなく（すべての人に認識されています）、推奨されません。それは公式には、そのスレッド安全方法が方法全体をロックするためであり、効率が低いことです。それで、より良い解決策はありますか？実際、1つがあるとは言えませんが、実際に1つ、collections.synchronizedList（）があります。
スタックは継承され、ベクトルに基づいているため、ベクターのいくつかの定義とメソッドソースコードを見てみましょう。
//基礎となるレイヤーは配列を使用してデータ保護オブジェクト[] elementDataを保存します。 //保護された要素の数int elementCount。 //コンテナの拡張とインクリメントサイズ保護されたINT容量インクリメントをカスタマイズします。 public vector（int initialcapacity、int capationalincrement）{super（）; // bounds exit bounds check（initialcapacity <0）を新しいIllegalargumentException（ "違法容量：" + initial -capacity）; //配列を初期化this.elementData = new Object [initialCapacity]; this.capacityIncrement = caputionIncrement; } //同期されたキーワードロックメソッドを使用して、1つのスレッドのみが同時にメソッドを操作できることを確認してください。 //拡大チェックEnsureCapacityHelper（ElementCount + 1）; elementData [ementscount ++] = e; trueを返します。 } private void ensurecapacityhelper（int mincapacity）{//現在の要素数int oldcapacity = elementdata .length; //（mincapacity> oldcapacity）{object [] ofldata = elementData; //コンテナの拡張がカスタマイズされている場合、容量に応じて容量を拡張し、それ以外の場合は容量を2回（*2）int newcapacity =（caputerincrement> 0）拡大しますか？ （oldcapacity + caputerincrement）：（ oldcapacity * 2）; if（newcapacity <mincapacity）{newcapacity = mincapacity; } //配列コピーelementData = arrays.copyof（elementData、newCapacity）; }}ベクトルはこれを見るだけです。他のスタックメソッドが呼び出されない場合、分析されません。わからない場合は、ArrayListソースコード分析を確認できます。
3。主な方法の分析
1.peek（） - スタックの上部にオブジェクトを取得します
/ ** *スタックの上部にオブジェクトを取得しますが、削除しないでください */ public同期e peek（）{//コンテナ要素の現在の数int len = size（）; //要素がない場合は、（len == 0）新しいemptystackexception（）を投げる場合、例外を直接スローします。 // elementAtメソッドを呼び出して、配列の最後の要素を取得します（最後の要素はスタックの上部にあります）return elementat（len -1）; } / ***インデックスインデックスに従ってこの位置で要素を取得すると、このメソッドはベクトルにあります* / public同期e elementat（int index）{// bounds if（index> = elementCount）{throw new ArrayIndexOutOfBoundSexception（index + "> = =" + ementaunt）; } // retention return（e）elementData [index]; }2.pop（） - スタック（スタックから）をポップし、スタックの上部にオブジェクトを取得し、コンテナからオブジェクトを削除します
/ ***スタックをバンブルし、スタックの上部にオブジェクトを取得して削除します*/ public同期E pop（）{//スタックE objの上部にオブジェクトを記録します。 //現在のコンテナ要素の数int len = size（）; // PEEK（）Method OBJ = PEEK（）を介してStack OBJの上部にオブジェクトを取得します。 // remofelementメソッドを呼び出して、スタックremoveElementat（len -1）の上部にあるオブジェクトを削除します。 //スタックの上部にあるオブジェクトに戻るOBJを返します。 } / ***インデックスインデックスに従って要素を削除します* / public同期void remoidElementat（int index）{modcount ++; // bounds if（index> = elementCount）{new arrayindexOutofboundsexception（index + "> =" + ementcount）; } else if（index <0）{new arrayindexOutofboundsexception（index）; } //移動する配列要素の数を計算しますint j = elementCount -index -1; if（j> 0）{//配列を移動し、中央の配列を削除するので、後続の要素を前方に移動します（ここで移動すると、削除に相当するインデックス位置要素を直接上書きします）システム。 ArrayCopy（elementData、Index + 1、ElementData、Index、J）; } //マイナス1 elementCount--; //コンテナの最後の要素を空にするように設定します（要素が削除され、インデックスの背後にある要素が前方に移動されたため、最後の要素は役に立たなかったため）elementData [elementCount] = null; / * GCにその仕事をさせる */}3.push（e item） - プッシュ（スタックに）、オブジェクトをコンテナに追加して返します
/ ** *オブジェクトをコンテナに追加して戻ります */ public e push（e item）{// addelementにaddelement（item）を呼び出します。 //要素返品アイテムを返します。 } /***要素をコンテナに追加します。この方法はベクター*/ public同期void addelement（e obj）{modcount ++; //拡大チェックEnsureCapacityHelper（ElementCount + 1）; //オブジェクトを配列に入れます。要素の数+1 elementData [elementCount ++] = obj; }4.Search（オブジェクトO） - コンテナ内のオブジェクトの位置を返し、スタックの上部は1です
/ ** *コンテナ内のオブジェクトの位置を返し、スタックの上部は1 */ public同期INT検索（オブジェクトO）{// Arrayの要素を見つけます。 //スタックの上部は1であるため、size（） - iを使用してif（i> = 0）{return size（） - i;を計算する必要があります。 } return -1; }5.Empty（） - コンテナは空です
/ ***コンテナが空であるかどうかを確認*/ public boolean empty（）{return size（）== 0; }サブセクション：
この時点で、スタック法が分析されます。スタックは最終的にアレイに基づいているため、まだ理解しやすいです（アレイリストに基づいているため）。
JDKのStackのソースコードは分析されていますが、ここで議論する必要があります。ここのスタックが非常に奇妙であることがわかったかどうかはわかりません。
（1）アレイに基づいてスタックが実装されるのはなぜですか？
私たちは皆、アレイの特性を知っています。それらはサブスクリプト（ランダムアクセス）に基づいてクエリするのに便利ですが、メモリは固定されており、容量の拡張効率は低いです。スタックがリンクされたリストを使用するのに最も適したものを考えるのは簡単です。
（2）なぜスタックはベクトルを継承するのですか？
継承とは、スタックがベクトル法を継承することを意味します。これにより、Stackはリストとスタックの両方で少し不適切に感じられます。ベクターを継承する必要がある場合、合理的なアプローチは何ですか：Stackはベクトルを継承しないが、ベクトル自体への参照のみを持っているのか、集約は正しいですか？
唯一の説明は、スタックがJDK1.0によって作成されたことです。当時、JDKのコンテナには、ArrayList、LinkedListなどのベクトルのみがありませんでした。また、すでにベクトルを持ち、スタック関数を実装できるため、それを行います。 。 。リンクされたリストでスタックを実装することが理想的であるため、試してみましょう。
java.util.linkedListをインポートします。 public class linkedStack <e> {private linkedlist <e> linked; public linkedStack（）{this.linked = new LinkedList <e>（）; } public e push（e item）{this.linked .addfirst（item）;返品アイテム。 } public e pop（）{if（this.linked.isempty（））{return null; } this.linked.removefirst（）; } public e peek（）{if（this.linked.isempty（））{return null; } this.linked.getFirst（）; } public int search（e item）{int i = this.linked.indexof（item）; I + 1を返します。 } public boolean empty（）{return this.linked.isempty（）; }}LinkedListによって実装されたスタックは、ここで使用されます。 LinkedListで述べたように、LinkedListはDequeインターフェイスを実装して、スタック（最初のインとアウト）およびキュー（最初のインとアウト）として使用できるようにします。
4.ベクターとアレイリストの違い
リストインターフェイスには、ArrayList、Vector、LinkedListの3つの実装クラスがあります。リストは、複数の要素を保存し、要素の順序を維持し、要素の繰り返しを許可するために使用されます。
3つの特定の実装クラスの関連する違いは次のとおりです。
1. ArrayListは、アレイを介して内部的に実装される最も一般的に使用されるリスト実装クラスであり、要素へのランダムアクセスを迅速に可能にします。配列の欠点は、各要素間に間隔を置くことができないことです。アレイサイズが満たされていない場合、ストレージ容量を増やす必要があります。すでにアレイのデータが新しいストレージスペースにコピーされていると言う必要があります。アレイリストの中間位置から要素を挿入または削除する場合、配列をコピー、移動する必要があり、コストが比較的高くなります。したがって、挿入や削除ではなく、ランダムルックアップやトラバーサルに適しています。
2.ベクトルはアレイを介して実装されます。違いは、スレッドの同期をサポートすることです。つまり、特定の瞬間に、1つのスレッドのみがベクトルを記述して、複数のスレッドが同時に書き込むことによって引き起こされることを避けることができますが、同期を実装するのに費用がかかるため、アレイリストにアクセスするよりも遅くなります。
3. LinkedListは、リンクされたリスト構造を使用してデータを保存します。これは、データの動的挿入と削除に非常に適しており、ランダムアクセスとトラバーサル速度は比較的遅いです。さらに、テーブルヘッダーとテール要素の操作に特別に使用され、スタック、キュー、双方向のキューとして使用できるリストインターフェイスでは定義されていないメソッドも提供します。
5.キューキュー、両端のキューデクの簡単な理解
1。キュー
一般的なキュー操作をサポートするために、新しいJava.util.queueインターフェイスがJava5に追加されました。このインターフェイスは、java.util.collectionインターフェイスを拡張します。
パブリックインターフェイスキュー<e>拡張コレクション<e>
基本的な収集操作に加えて、キューは他の挿入、抽出、および操作のチェックを提供します。
各メソッドには2つのフォームがあります。1つは例外をスローし（操作が失敗した場合）、もう1つは特別な値（操作に応じてnullまたはfalse）を返します。
通常、キューは（必ずしもそうではない）FIFOの個々の要素をソートします（最初は最初に）。ただし、優先キューとLIFOキュー（またはスタック）は例外です。前者は、提供されたコンパレータまたは要素の自然な順序に従って要素をソートし、後者はLIFOの要素をソートします（最新の最初のアウト）。
FIFOキューでは、すべての新しい要素がキューの最後に挿入され、削除要素がキューヘッダーから削除されます。
キューを使用する場合は、add（）およびremot（）コレクションの方法を回避しますが、offer（）を使用して要素を追加し、poll（）を使用して要素を取得して削除します。彼らの利点は、価値を返すことによって成功が達成されるかどうかを判断できること、およびadd（）およびremove（）メソッドが失敗したときに例外をスローすることです。要素を削除せずにフロントエンドを使用する場合は、Element（）またはPeek（）メソッドを使用します。
オファーメソッドは要素を挿入できます。そうしないと、falseを返します。これは、Collection.Addメソッドとは異なります。これは、未チェックの例外をスローすることによってのみ要素を追加できないことができます。
remove（）およびpoll（）メソッドは、キューのヘッダーを削除して返します。キューから削除される要素は、さまざまな実装で異なるキューソートポリシーの関数です。 remove（）とpoll（）メソッドは、キューが空の場合にのみ異なります。Remove（）メソッドは例外をスローし、Poll（）メソッドはnullを返します。
element（）およびpeek（）は、キューヘッダーを削除しますが、削除しないでください。
通常、キューの実装ではヌル要素の挿入は許可されていませんが、一部の実装（LinkedListなど）はヌルの挿入を禁止していません。 nullはキューに挿入されてはならないため、nullをキューに挿入しないでください。nullは投票方法の特別な返品値としても使用されており、キューに要素が含まれていないことを示しています。
LinkedListクラスがキューインターフェイスを実装していることは注目に値します。そのため、LinkedListをキューとして使用できます。
java.util.queueをインポートします。 java.util.linkedListをインポートします。 public class testqueue {public static void main（string [] args）{queue <string> queue = new linkedlist <string>（）; queue.offer（ "hello"）; queue.offer（ "world！"）; queue.offer（ "hello！"）; system.out.println（queue.size（））;文字列str; while（（str = queue.poll（））！= null）{system.out.print（str）; } system.out.println（）; system.out.println（queue.size（））; }}2。デク
パブリックインターフェイスdeque <e>拡張キュー<e>
両端での要素の挿入と除去をサポートする線形コレクション。
Dequeという名前は、「Double End Queue」の略語であり、通常は「デッキ」と読みます。
ほとんどのDeque実装には、含めることができる要素の数に固定制限はありませんが、このインターフェイスは、固定サイズ制限なしで容量制限キューとデュアルエンドキューの両方をサポートします。
このインターフェイスは、両端のキューの両端に要素にアクセスする方法を定義します。要素を挿入、削除、検査する方法を提供します。このインターフェイスはキューインターフェイスキューを継承するため、各メソッドに2つのフォームがあります。1つは操作が故障したときに例外をスローし、もう1つは特別な値（操作に応じてnullまたはfalse）を返します。
a。両端のキューをキューとして使用すると、FIFO（ファーストイン、ファーストアウト）動作が得られます。両端のキューの端に要素を追加し、両端のキューの先頭から要素を削除します。次の表に示すように、キューインターフェイスから継承された方法は、Dequeメソッドと完全に同等です。
b。 LIFO（最初のアウトで最後）スタックとして使用されます。このインターフェイスは、レガシースタッククラスではなく、最初に使用する必要があります。両端のキューをスタックとして使用する場合、要素は両端のキューの先頭に押し込まれ、両端のキューの先頭からポップアップします。次の表に示すように、スタック法はDequeメソッドと完全に同等です。