數據結構：棧和隊列

你好！今天我們將討論對任何程序員都非常重要的東西：數據結構。 維基百科說：“數據結構是一種數據組織、管理和存儲格式，可以實現高效的訪問和修改。更準確地說，數據結構是數據值的集合，它們之間的關係，以及可以被執行的功能或操作。應用於數據。” 這個定義有點混亂，但它的要點很清楚。 數據結構是一種存儲庫，我們在其中存儲數據以供將來使用。 在編程中，有各種各樣的數據結構。 在解決具體問題時，很多時候最重要的是選擇最適合問題的數據結構。 而且您已經熟悉其中的許多內容！例如，您了解數組。而你也很熟悉Map（此數據結構也可稱為“字典”或“關聯數組”）。了解數據結構與任何特定語言無關是非常重要的。它們只是抽象的“藍圖”，每種編程語言都使用它們來創建自己的類或特定結構的實現。例如，最著名的數據結構之一是鍊錶。你可以去維基百科看看它是如何工作的以及它有什麼優點和缺點。也許它的定義對你來說很熟悉 :) “鍊錶是數據元素的線性集合，其順序不是由它們在內存中的物理位置給出的。相反，每個元素都指向下一個。” 這描述了我們心愛的人LinkedList，不是嗎？ 是的，就是這樣:) 在 Java 中，“鍊錶”數據結構由類實現LinkedList。但是其他語言也實現了鍊錶！在 Python 中，這種數據結構被稱為“ llist”。在 Scala 中它被稱為“ LinkedList”，就像在 Java 中一樣。鍊錶是基本的常用數據結構之一，因此您會發現它在任何現代編程語言中都有實現。關聯數組也是如此。這是維基百科的定義：“關聯數組、映射、符號表或字典是由（鍵、值）對集合組成的抽像數據類型，這樣每個可能的鍵在集合中最多出現一次。” 這讓你想起了什麼嗎？：） 是的。對於我們 Java 開發人員來說，關聯數組是Map界面。但是這個數據結構也有其他語言實現的！例如，C# 程序員知道它的名稱是“Dictionary”。而在 Ruby 中，它是在一個名為“Hash”的類中實現的。好吧，你明白了：數據結構是編程中的通用概念，每種編程語言都以自己的方式實現它們。今天我們將研究兩種這樣的結構——棧和隊列——看看它們是如何在 Java 中實現的。

Java 中的堆棧

堆棧是眾所周知的數據結構。這很簡單。我們日常生活中有相當多的項目是作為堆棧“實現”的。想像一下這個簡單的情況：您住在一家旅館，並且在一天中您收到了一些商業信函。當時你不在房間裡，所以酒店服務員只是把收到的信件放在你的桌子上。首先，他把第一封信放在了書桌上。然後第二封信到了，他把它放在第一封上面。他把第三個字母放在第二個上面，第四個放在第三個上面。 現在，回答一個簡單的問題：當你回到房間看到桌上的一疊信時，你會先讀哪封信？對，你會讀到最上面的信。也就是最近到的那個。這正是堆棧的工作原理。這個原則被稱為“後進先出”（LIFO）。堆棧有什麼用？好吧，假設您正在用 Java 創建某種紙牌遊戲。一副紙牌躺在桌子上。打出的牌被丟棄。您可以使用兩個堆棧來實現抽牌和棄牌堆。玩家按照與您的商業信函相同的原則，從一副牌的頂部取出他們的牌。當玩家將牌放入棄牌堆時，新棄牌會放在舊牌之上。這是我們在遊戲中的第一次嘗試，基於堆棧實現：

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.
}

正如我們之前所說，我們有兩堆：抽牌和棄牌堆。在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());
   }
}

我們在套牌中添加了五張牌。第一個玩家拿走了其中的 3 個。她得到了哪些卡片？控制台輸出：

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

注意卡片在控制台上的顯示順序。“Edwin VanCleef”牌最後進入牌組（這是第五張牌），也是玩家最先抽到的牌。“米爾豪斯”倒數第二個進入牌組，玩家第二個抽到它。“希爾瓦娜斯”從頂數第三個進入套牌，這是玩家抽到的第三張牌。接下來，玩家棄牌。首先，她拋棄了埃德溫，然後是米爾豪斯，然後是希爾瓦娜斯。然後我們一張一張地顯示我們棄牌堆中的牌： 控制台輸出：

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

我們再一次看到堆棧是如何工作的！在我們的遊戲中，棄牌堆也是一堆（就像抽牌一樣）。“Edwin VanCleef”首先被丟棄。第二張棄牌是 Millhouse Manastorm，它放在棄牌堆中的 Edwin 上面。隨後希爾瓦娜斯被棄掉，這張牌放在了米爾豪斯的上面。如您所見，堆棧並不復雜。儘管如此，您還是需要了解這種數據結構——它經常在求職面試中被問到，而且它通常是構建更複雜數據結構的基礎。

Java中的隊列

隊列是另一種常見的數據結構。除了棧，包括Java在內的很多編程語言也實現了隊列數據結構。隊列和棧有什麼區別？隊列不是基於 LIFO 原則，而是基於 FIFO 原則（“先進先出”）。通過考慮現實生活中的一條普通線路或隊列，這個原理很容易理解！例如，在雜貨店排隊。 如果有五個人排隊，那麼第一個上菜的就是第一個上桌的人。如果另一個人（除了已經排隊的五個人）想買東西並排隊，那麼他最後得到服務，也就是第六。使用隊列時，新元素被添加到尾部（後面），如果你想獲取一個元素，它將從頭部（前面）獲取。這是您需要記住的關於隊列如何工作的主要原則。 隊列的操作非常直觀，因為我們在現實生活中經常見到隊列。單獨值得注意的是，在 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 的四個“子接口”之一：Deque。是什麼讓它如此特別？ADeque是雙端隊列。它擴展了常規隊列的功能，允許您向兩端（頭部和尾部）添加元素並從隊列的兩端獲取元素。 雙端隊列在軟件開發中被廣泛使用。注意我們上面提供的隊列類列表。列表很長，但它包含任何熟悉的內容嗎？

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

哈！這是我們的老朋友LinkedList！那麼，它實現了Queue接口？但是怎麼可能是隊列呢？畢竟 aLinkedList是一個鍊錶！是的，但這並不能阻止它成為一個隊列 :) 下面是它實現的所有接口的列表：

All implemented interfaces:

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

如您所見，LinkedList實現了Deque接口（同樣，這意味著雙端隊列）。為什麼需要這個？這允許我們從 a 的開頭和結尾獲取元素LinkedList。它還允許我們在開頭和結尾添加元素。LinkedList以下是從接口獲取的方法Deque：

• peekFirst()— 返回第一個元素（但不會將其從隊列中移除）。
• peekLast()— 返回最後一個元素（但不會將其從隊列中移除）。
• pollFirst()— 返回隊列中的第一個元素並將其移除。
• pollLast()— 返回隊列中的最後一項並將其刪除。
• addFirst()— 將新項目添加到隊列的前面。
• addLast()— 添加一個項目到隊列的末尾。

可以看到，LinkedList完全實現了雙端隊列的功能！如果您的程序需要這樣的功能，您就會知道在哪裡可以找到它:) 今天的課程即將結束。 最後，我將為您提供幾個鏈接供您進一步閱讀。首先，關注這篇關於 PriorityQueue 的文章。這是最有趣和最有用的實現之一Queue。例如，假設你的店裡有50個人在排隊，其中有7個人是VIP客戶。PriorityQueue 將讓您首先為他們服務！非常有用的東西，對吧？:) 其次，再次提及Robert Lafore 的書“Java 中的數據結構和算法”也無妨. 閱讀本書，您不僅會學到許多數據結構（包括堆棧和隊列），而且您還將自己實現其中的許多數據結構！例如，如果 Java 沒有 Stack 類怎麼辦？如果您的程序需要這樣的數據結構，您會怎麼做？當然，您必須自己編寫。當您閱讀Lafore 的書時，您通常會這樣做。因此，您對數據結構的理解將比您從簡單的理論研究中獲得的理解更深刻:) 我們今天總結了理論，但是沒有實踐的理論是空談！這些任務不會自行解決，所以是時候解決它們了！:)