Java のデータ構造 - スタックとキュー

こんにちは！今日は、データ構造など、プログラマーにとって非常に重要なことについて話します。Wikipedia には次のように書かれています: データ構造( eng. data Structure ) は、コンピューティングにおいて多数の同じタイプのデータや論理的に関連したデータを保存および処理できるようにするソフトウェア ユニットです。定義は少しわかりにくいですが、その本質は明らかです。 データ構造は、さらなる使用のためにデータを保存する一種のストレージです。 プログラミングには多種多様なデータ構造があります。 多くの場合、特定の問題を解決する場合、最も重要なことは、この目的に最適なデータ構造を選択することです。 そして、それらの多くはすでによく知られています。たとえば、配列の場合です。また、Map（通常は「辞書」、「地図」、または「連想配列」と訳されます）も使用します。データ構造は特定の言語に関連付けられていないことを理解することが非常に重要です。これらは単なる抽象的な「設計図」であり、それに従って各プログラミング言語が独自のクラス、つまりこの構造の実装を作成します。たとえば、最も有名なデータ構造の 1 つはリンク リストです。ウィキペディアにアクセスして、それがどのように機能するか、どのような利点と欠点があるかを読むことができます。その定義には馴染みがあるかもしれません :) 「リンク リストは、コンピュータ サイエンスにおける基本的な動的データ構造であり、ノードで構成されます。各ノードには、データ自体と、次のノードやデータへの 1 つまたは 2 つのリンク (「リンク」) の両方が含まれます。前のノードのリスト」 これが私たちのものですLinkedList！ まさにその通りです:) リンクされたリストのデータ構造は、クラス内の Java 言語で実装されますLinkedList。しかし、他の言語でもリンク リストが実装されています。Python では「 」と呼ばれますllistが、Scala では Java と同じ「LinkedList」と呼ばれます。リンク リストは基本的な共通データ構造の 1 つであるため、最新のプログラミング言語でその実装を見つけることができます。連想配列でも同じです。Wikipedia からの定義は次のとおりです。 連想配列は、「(キー, 値)」形式のペアを保存できる抽象データ型 (データ ストアへのインターフェイス) であり、ペアの追加操作と検索操作をサポートします。キーごとにペアを削除します。何か思い出しませんか？:) まさに、私たち Java 主義者にとって、連想配列はインターフェイスです。Map。しかし、このデータ構造は他の言語でも実装されています。たとえば、C# プログラマはこれを「辞書」という名前で知っています。Ruby 言語では、「Hash」と呼ばれるクラスに実装されます。一般に、その意味はおおよそ理解できています。データ構造はすべてのプログラミングに共通のものであり、特定の言語ごとに異なる方法で実装されます。今日は、そのような 2 つの構造 (スタックとキュー) を学習し、それらが Java でどのように実装されるかを見ていきます。

Javaでのスタック

スタックは既知のデータ構造です。それは非常にシンプルであり、私たちの日常生活からの非常に多くのオブジェクトがスタックとして「実装」されています。単純な状況を想像してください。あなたはホテルに住んでいて、日中ビジネスレターを受け取ります。そのときあなたは部屋にいなかったため、ホテルの従業員は届いた手紙をテーブルの上に置いただけです。まず彼は最初の手紙をテーブルの上に置きました。それから2番目のものが来て、彼はそれを最初のものの上に置きました。彼は届いた 3 通目の手紙を 2 通目の手紙の上に置き、4 通目の手紙を 3 通目の手紙の上に置きました。 さて、簡単な質問に答えてください。自分の部屋に来てテーブルの上に手紙が置かれているのを見たとき、最初に読むのはどの手紙ですか? そうです、一番上の文字を読みます。つまり、時間的に最後に来たものです。これはまさにスタックの仕組みです。この動作原理はLIFO (「後入れ先出し」) と呼ばれます。スタックは何に役立ちますか? たとえば、Java で何らかのカード ゲームを作成しているとします。トランプがテーブルの上に置かれています。プレイされたカードは捨てられます。2 つのスタックを使用して、デッキとディスカードの両方を実装できます。プレイヤーは山札の一番上からカードを引きます。これは手紙と同じ原理です。プレイヤーがカードを捨てると、新しいカードが古いカードの上に置かれます。スタックを使用して実装されたゲームの最初のドラフトは次のようになります。

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       graveyard.push(card);
   }

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

前に述べたように、山札と捨て札の 2 つのスタックがあります。スタック データ構造は、Java で実装されていますjava.util.Stack。私たちのカード ゲームでは、プレイヤーのアクションを記述する 3 つのメソッドがあります。

• デッキからカードを 1 枚取り出します (メソッドgetCardFromDeck())。
• カードを破棄します (メソッドdiscard());
• 一番上のカードを見てください (メソッドlookTopCard())。これがボーナスメカニズム「インテリジェンス」であるとしましょう。これにより、プレイヤーは次にどのカードが場に出るかを知ることができます。

メソッド内では、クラス メソッドが呼び出されますStack。

• push()— 要素をスタックの先頭に追加します。カードを捨てると、そのカードは前に捨てたカードの上に重ねられます。
• pop()— スタックから最上位の要素を削除して返します。この方法は、「プレイヤーがカードを引く」メカニズムを実装するのに最適です。
• peek()- スタックの最上位要素を返しますが、スタックからは削除しません

ゲームがどのように機能するかを見てみましょう:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

ということで、デッキに5枚のカードを追加しました。最初のプレイヤーはそれらのうち 3 つを取りました。彼はどんなカードを手に入れましたか？ コンソール出力:

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

カードがコンソールに出力された順序に注意してください。「エドウィン ヴァン クリーフ」カードはデッキに最後に登場したカード (5 回連続) で、プレイヤーが最初に取ったカードでした。「Michhlaus」はデッキの最後から 2 番目にあり、そのプレイヤーが 2 番目にそれを獲得しました。「シルヴァナス」はデッキに最後から3番目にヒットし、3番目のプレイヤーに行きました。次に、プレイヤーは自分のカードを捨てます。最初に彼はエドウィンを落とし、次にミルハウス、そしてシルヴァナスを落とします。その後、捨て札にあるカードを 1 枚ずつコンソールに出力します。 コンソールに出力します。

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

スタックがどのように機能するかをもう一度見てみましょう。このゲームの捨て札も (デッキと同様に) スタックです。最初に削除されたのは「エドウィン・ヴァン・クライフ」でした。2番目にドロップされたのは「ミルハウス・マナストーム」で、ディスカードでエドウィンの上に置かれました。次に、シルヴァナスが捨てられ、このカードがミルハウスの上に置かれました。ご覧のとおり、スタックの動作については何も複雑ではありません。ただし、このデータ構造を知っておく必要があります。これはインタビューでよく質問され、さらに複雑なデータ構造がそれに基づいて構築されることがよくあります。

列

キュー (英語では「Queue」) も一般的なデータ構造です。スタックと同様に、Java を含む多くのプログラミング言語で実装されています。キューとスタックの違いは何ですか? そのキューは LIFO ではなく、別の原則である FIFO (「先入れ先出し」、「先入れ先出し」) に基づいています。例として挙げるとわかりやすいでしょう...少なくとも現実世界の普通の実際の行列です。たとえば、お店への行列。 5名様お並びの場合、先頭の方からのご入店となります。(並んでいる 5 人以外に) もう 1 人が何かを買いたいと思って列に並んだ場合、その人は最後、つまり 6 番目に店に入ります。キューを操作する場合、新しい要素は最後に追加され、要素を取得したい場合は先頭から取得されます。これは、キューの基本的な動作原理であり、覚えておく必要があります。 キューの原理は、実際の生活でも頻繁に使用されるため、直感的に理解するのが非常に簡単です。Java ではキューはクラスではなくインターフェース - によって表されることは別途注意する価値がありますQueue。しかし同時に、Java のキューは多くの実装があるインターフェイスでもあります。Oracle のドキュメントを見ると、4 つの異なるインターフェイスと非常に印象的なクラスのリストがキューから継承されていることがわかります。

All Known Subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All Known Implementing Classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

なんて大きなリストでしょう！しかし、もちろん、今すぐこれらのクラスとインターフェイスをすべて暗記する必要はありません。頭が爆発するかもしれません :) 最も重要で興味深い点をいくつかだけ見ていきます。まず、キューの 4 つの「サブインターフェイス」のうちの 1 つに注目してみましょう - Deque。何がそんなに特別なのでしょうか？ Deque- これは双方向のキューです。 これは、キューの両端 (キューの先頭と末尾) に要素を追加したり、キューの両端から要素を取得したりできるようにすることで、通常のキューの機能を拡張します。 deque は開発で広く使用されています。上記で提供したキュー クラスのリストに注目してください。リストはかなり長いですが、私たちに馴染みのあるものはありますか?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

ああ、私たちの古い友人がここに来たのですねLinkedList！つまり、インターフェイスQueue?を実装します。しかし、どうして彼は行列になれるのでしょうか？結局のところLinkedList、これはつながったリストなのです。確かにそうですが、それがキューであることを止めるわけではありません:) 以下に、それが実装するすべてのインターフェースのリストを示します。

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

ご覧のとおり、これは双方向キューというLinkedListインターフェイスを実装しています。Dequeなぜこれが必要なのでしょうか? これのおかげで、先頭と末尾の両方から要素を取得できますLinkedList。また、最初と最後の両方に要素を追加します。LinkedListインターフェースから継承されたメソッドは次のとおりですDeque。

• peekFirst()— 最初の要素を返します (ただし、キューからは削除されません)。
• peekLast()— 最後の要素を返します (ただし、キューからは削除されません)。
• pollFirst()- キューから最初の要素を返し、それを削除します。
• pollLast()- キューから最後の要素を返し、それを削除します。
• addFirst()— 新しい要素をキューの先頭に追加します。
• addLast()— キューの最後に要素を追加します。

ご覧のとおり、LinkedListこれは双方向キューの機能を完全に実装しています。そして、そのような機能がプログラムで必要な場合は、それを使用できることがわかります :) そして、今日の講義は終わりに近づいています。最後に、さらに読んでいただくためのリンクをいくつか紹介します。まず、PriorityQueue に関する記事「優先キュー」に注目してください。これは Queue の最も興味深く便利な実装の 1 つです。たとえば、店舗に 50 人が並んでいて、そのうち 7 人が VIP 顧客である場合、PriorityQueue最初にサービスを提供できます。とても便利なことだと思いませんか？:) 次に、 Robert Laforet の著書「Data Structures and Algorithms in Java」についてもう一度言及するのは不必要ではありません。この本を読みながら、多くのデータ構造 (スタックやキューを含む) を学ぶだけでなく、その多くを自分で実装することもできます。たとえば、Java に Stack クラスがなかった場合を想像してください。プログラムにそのようなデータ構造が必要な場合はどうしますか? もちろん、自分で書かなければなりません。ラフォーレの本を読んでいると、よくこうなります。このおかげで、データ構造の理解は、単に理論を勉強するよりもはるかに広範囲になります :) 今日の理論は終わりですが、実践のない理論は何の意味もありません。問題は自然に解決するものではないので、今こそ取り組むべき時です。:)