你好！今天我們將討論對於任何程式設計師來說都很重要的事情，例如資料結構。維基百科說： 資料結構（eng.data Structure）是一個軟體單元，可讓您在計算中儲存和處理大量相同類型和/或邏輯相關的資料。這個定義有點混亂，但本質很清楚。 資料結構是一種儲存方式，我們在其中儲存資料以供進一步使用。 程式設計中有各種各樣的資料結構。 很多時候，在解決特定問題時，最重要的是選擇最適合此目的的資料結構。 而且您已經熟悉其中的許多內容了！例如，使用數組。還有with ![資料結構 - 堆疊和佇列 - 2]()
沒錯，就是這樣的：）鍊錶資料結構是在類別中用Java語言實作的![資料結構 - 堆疊和佇列 - 3]()
閱讀哪封信？沒錯，您將閱讀最上面的字母。也就是時間上最後的那個。這正是堆疊的工作原理。這種操作原則稱為LIFO—「後進先出」（「後進先出」）。堆疊有什麼用？例如，您正在用 Java 創建某種紙牌遊戲。桌上放著一副紙牌。打出的牌將被丟棄。您可以使用兩個堆疊來實現套牌和棄牌。玩家從牌堆頂部抽牌 - 與字母相同的原理。當玩家棄牌時，新牌會放在舊牌之上。這是我們遊戲的初稿，使用堆疊實作：
![Java-университет]()
![資料結構 - 堆疊和佇列 - 4]()
如果有五個人排隊，則第一個排隊的人進入商店。如果還有一個人（除了排隊的五個人之外）想要買東西並排隊，那麼他最後進入商店，也就是第六個。使用佇列時，新元素會新增到末尾，如果要取得元素，將從頭開始取得。這是它運作的基本原理，需要記住， ![資料結構 - 堆疊和佇列 - 5]()
隊列的原理很容易直觀地理解，因為它在現實生活中經常遇到。值得注意的是，在 Java 中，佇列不是由類別表示，而是由介面 - 表示![資料結構 - 堆疊和佇列 - 6]()
雙端隊列在開發中被廣泛使用。請注意我們上面提供的隊列類別清單。名單很長，但裡面有我們熟悉的東西嗎？
Map（通常被翻譯為「字典」、「地圖」或「關聯數組」）。理解這一點非常重要：資料結構不依賴任何特定的語言。這些只是抽象的“藍圖”，每種程式語言都根據它們創建自己的類別 - 該結構的實現。例如，最著名的資料結構之一是鍊錶。你可以去維基百科，了解它是如何運作的，它有什麼優點和缺點。您可能會發現它的定義很熟悉:) 「鍊錶是電腦科學中的一種基本動態資料結構，由節點組成，每個節點都包含資料本身以及一個或兩個到下一個和/或上一個節點列表」 所以這是我們的LinkedList！ 
沒錯，就是這樣的：）鍊錶資料結構是在類別中用Java語言實作的LinkedList。但其他語言也實作鍊錶！在Python中它被稱為“ llist”，在Scala中它被稱為與Java中相同的“ LinkedList”。鍊錶是基本的常見資料結構之一，因此您可以在任何現代程式語言中找到它的實作。關聯數組也是如此。以下是維基百科對其的定義： 關聯數組是一種抽象資料類型（資料儲存的介面），允許儲存「（鍵，值）」形式的對，並支援添加對以及搜尋的操作並透過鍵刪除一對。沒有提醒你什麼嗎？:) 確實，對我們Javaists來說，關聯數組就是一個接口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 {
// колода
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();
}
// ..геттеры, сеттеры и т.д.
}java.util.Stack。在我們的紙牌遊戲中，有 3 種方法來描述玩家的行為：
- 從牌堆中取出一張牌（方法
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());
}
}
Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}
Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}佇列
隊列（或英語“Queue”）是另一種常見的資料結構。就像堆疊一樣，它可以用多種程式語言實現，包括 Java。佇列和堆疊有什麼區別？它的隊列不是基於LIFO，而是基於另一個原則——FIFO（“先進先出”，“先進先出”）。這很容易理解，舉個例子……或至少是現實生活中一個普通的、真實的隊列！例如，去商店排隊。
如果有五個人排隊，則第一個排隊的人進入商店。如果還有一個人（除了排隊的五個人之外）想要買東西並排隊，那麼他最後進入商店，也就是第六個。使用佇列時，新元素會新增到末尾，如果要取得元素，將從頭開始取得。這是它運作的基本原理，需要記住， 
隊列的原理很容易直觀地理解，因為它在現實生活中經常遇到。值得注意的是，在 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, SynchronousQueueDeque。它有什麼特別之處？ Deque- 這是一個雙向隊列。 它擴展了常規隊列的功能，允許您向兩端（隊列的開頭和結尾）添加元素並從隊列的兩端獲取元素。 
雙端隊列在開發中被廣泛使用。請注意我們上面提供的隊列類別清單。名單很長，但裡面有我們熟悉的東西嗎？
LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueueLinkedList！也就是說，它實作了接口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的文章－「優先權佇列」。這是隊列最有趣和最有用的實作之一。例如，如果你的店裡有50個人排隊，其中7個是VIP客戶，PriorityQueue那麼你就可以先為他們服務！非常有用的東西，你不同意嗎？:) 其次，再次提及Robert Laforet 的書《Java 中的資料結構與演算法》也並非多餘。在閱讀本書的過程中，你不僅會學到許多資料結構（包括堆疊和佇列），還會自己實作其中許多資料結構！例如，想像一下如果 Java 沒有 Stack 類別。如果您的程式需要這樣的資料結構，您會怎麼做？當然，我必須自己寫。當閱讀拉弗雷的書時，你通常會這樣做。這樣，你對資料結構的理解將比僅僅學習理論要廣泛得多:)我們今天已經講完了理論，但是沒有實踐的理論什麼都不是！問題不會自行解決，所以現在是解決問題的時候了！:)
GO TO FULL VERSION