データ構造: スタックとキュー

やあ！今日は、プログラマーにとって非常に重要なこと、つまりデータ構造について話します。 Wikipedia には次のように記載されています。「データ構造とは、効率的なアクセスと変更を可能にするデータの組織、管理、および保存形式です。より正確には、データ構造とは、データ値、それらの間の関係、およびデータ値間の関係、および実行できる機能や操作の集合です。データに適用されます。」定義は少しわかりにくいですが、その要点は明確です。 データ構造は、将来の使用に備えてデータを保存する一種のリポジトリです。 プログラミングには、非常に多様なデータ構造があります。 特定の問題を解決する場合、最も重要なことは、問題に最適なデータ構造を選択することです。 そして、それらの多くはすでによく知られています。たとえば、配列についてはご存知でしょう。そしてあなたもよく知っていますMap(このデータ構造は、「辞書」または「連想配列」と呼ばれることもあります)。データ構造が特定の言語に関連付けられていないことを理解することが非常に重要です。これらは、各プログラミング言語が独自のクラスや特定の構造の実装を作成するために使用する、単なる抽象的な「設計図」です。たとえば、最も有名なデータ構造の 1 つはリンク リストです。Wikipedia にアクセスして、その仕組みや長所と短所について読むことができます。おそらくその定義はあなたには馴染みのあるものだと思われるでしょう :) 「リンク リストはデータ要素の線形コレクションであり、その順序はメモリ内の物理的な配置によって与えられるものではありません。代わりに、各要素が次の要素を指します。」それは私たちの最愛の人を表していますLinkedListね? はい、それはまさにその通りです:) Java では、「リンク リスト」データ構造はクラスによって実装されますLinkedList。しかし、他の言語でもリンク リストが実装されています。Python では、このデータ構造を「llist」と呼びます。LinkedListScala では、Java と同様に「」と呼ばれます。リンク リストは基本的な共通データ構造の 1 つであるため、最新のプログラミング言語で実装されていることがわかります。連想配列にも同じことが当てはまります。Wikipedia の定義は次のとおりです。「連想配列、マップ、シンボル テーブル、または辞書は、(キー、値) ペアのコレクションで構成される抽象データ型であり、考えられる各キーがコレクション内に 1 回しか出現しません。」それを聞いて何か思い出しますか？:) はい。私たち Java 開発者にとって、連想配列はMapインターフェース。しかし、このデータ構造は他の言語でも実装されています。たとえば、C# プログラマはこれを「辞書」という名前で知っています。そしてRubyでは「Hash」というクラスで実装されます。データ構造はプログラミングにおける普遍的な概念であり、各プログラミング言語は独自の方法でデータ構造を実装します。今日は、そのような 2 つの構造 (スタックとキュー) を学習し、それらが Java でどのように実装されるかを見ていきます。

Javaのスタック

スタックはよく知られたデータ構造です。とてもシンプルです。私たちの日常生活のかなりの数のアイテムがスタックとして「実装」されています。この単純な状況を想像してみてください。あなたはホテルに滞在していて、一日のうちにいくつかのビジネスレターを受け取りました。その時あなたは部屋にいなかったため、ホテルの係員は届いた手紙をただ机の上に置きました。まず、彼は最初の手紙を机の上に置きました。それから二通目の手紙が届き、彼はそれを最初の手紙の上に置きました。彼は 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 {

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

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

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

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

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

• デッキからカードを取り出します (getCardFromDeck()メソッド)
• カードを捨てる (discard()メソッド)
• 一番上のカードを見てください (lookAtTopCard()メソッド)。これは、プレイヤーがゲームで次にどのカードが出てくるかを知ることができる「知性」ボーナスだとしましょう。

メソッド内では、Stack クラスの次のメソッドを呼び出します。

• push()— アイテムをスタックの一番上に追加します。カードを捨て札に送ると、それは山の一番上に置かれます
• pop()— スタックから最上位の要素を削除して返します。このメソッドは、プレイヤーがカードを引くアクションを実装するのに最適です。
• peek()— スタックの最上位の要素を返しますが、スタックからは削除しません

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

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

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

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

コンソールにカードが表示される順序に注意してください。「エドウィン ヴァンクリーフ」カードは最後にデッキに入れられ (5 番目のカードでした)、プレイヤーが最初に引いたカードでした。「ミルハウス」はデッキの最後から 2 番目にあり、プレイヤーはそれを 2 番目に引きました。「シルヴァナス」はデッキの上から3番目に入り、プレイヤーが引いた3枚目のカードでした。次に、プレイヤーはカードを捨てます。まず、彼女はエドウィンを捨て、次にミルハウスを捨て、次にシルヴァナスを捨てます。次に、捨て札の山にあるカードを 1 枚ずつ表示します。 コンソール出力:

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

スタックがどのように機能するかをもう一度見てみましょう。私たちのゲームでは、捨て札もスタックです (山札と同じように)。「Edwin VanCleef」が最初に破棄されました。2枚目の捨て札は《ミルハウス・マナストーム》で、捨て札の山のエドウィンの上に置かれました。その後、シルヴァナスを捨て、このカードをミルハウスの上に置きました。ご覧のとおり、スタックについては何も複雑ではありません。それでも、このデータ構造について知っておく必要があります。これは就職面接でよく質問され、より複雑なデータ構造を構築するための基礎となることがよくあります。

Javaのキュー

キューも一般的なデータ構造です。スタックに加えて、Java を含む多くのプログラミング言語もキュー データ構造を実装しています。キューとスタックの違いは何ですか? キューは、LIFO 原則ではなく、FIFO 原則 (「先入れ先出し」) に基づいています。この原理は、たとえば現実の通常の行列を考えると簡単に理解できます。たとえば、食料品店の行列。 5名様で並んでいる場合は、先に列に入った方から順にご案内させていただきます。すでに並んでいる 5 人に加えて、別の人が何かを買おうとして列に並んだ場合、その人が最後にサービスを受けます。、つまり6番目です。キューを操作する場合、新しい要素は末尾 (後ろ) に追加され、要素を取得する場合は先頭 (前) から取得されます。これは、キューの動作に関して覚えておく必要がある主な原則です。 キューは実際の生活でもよく見かけるので、キューの操作は非常に直感的です。Java では、キューはクラスではなく、インターフェイス Queue によって表されることに別途注意してください。さらに、このキュー インターフェイスは Java で多数実装されています。Oracle のドキュメントを見ると、4 つの異なるインターフェイスと非常に印象的なクラスのリストが Queue インターフェイスを継承していることがわかります。

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

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

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

はぁ！ここに私たちの古い友人がいますLinkedList！Queue インターフェースを実装しているということでしょうか？しかし、どうして行列ができるのでしょうか？結局のところ、a は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 Lafore の著書「Data Structures and Algorithms in Java」についてもう一度触れても問題ありません。。この本を読むと、多くのデータ構造 (スタックやキューを含む) を学ぶだけでなく、その多くを自分で実装することもできます。たとえば、Java に Stack クラスがなかったらどうなるでしょうか? プログラムにそのようなデータ構造が必要な場合はどうしますか? もちろん、自分で書く必要があります。ラフォーレの本を読んでいると、まさにそれを行うことがよくあります。その結果、データ構造についての理解は、単純な理論の研究から得られるものよりもはるかに深くなります :) 今日は理論をまとめますが、実践のない理論は何の意味もありません。タスクは自動的には解決されないので、今すぐ取り組んでください。:)