你好！今天我们讨论的内容对任何程序员来说都非常重要：数据结构。
维基百科指出：“数据结构是一种能够实现数据的高效访问和修改的数据组织、管理和存储形式。
更准确地说，数据结构是数据值、数据值之间的关系以及可应用于数据的功能或操作的集合。”这个定义有点混乱，但它的主旨是清楚的。
数据结构是一种存储数据以备将来使用的储存库。
在编程中，数据结构数不胜数。
在解决特定问题时，通常最重要的事情是为该问题选择最合适的数据结构。
而且很多数据结构你已经很熟悉了！例如，你知道数组。你也熟悉![数据结构：堆栈和队列 - 1]()
是的，这就是事实 :)
在 Java 中，“链表”数据结构是由 ![数据结构：堆栈和队列 - 2]()
控制台输出：
![数据结构：堆栈和队列 - 3]()
队列的操作非常直观，因为我们在现实生活中经常看到队列。
值得单独注意的是，在 Java 中，队列不是由类表示的，而是由接口表示的：Queue。
更何况这个队列接口在 Java 里有很多实现。
如果我们看一下 Oracle 文档，会看到 4 个不同的接口，以及一个令人印象深刻的类列表，它们继承了 Queue 接口：
![数据结构：堆栈和队列 - 4]()
双端队列广泛应用于软件开发中。
请注意我们上面提供的队列类列表。这个列表很长，但是它包含了什么熟悉的东西吗？
Map（这种数据结构也可以称为“字典”或“关联数组”）。
理解数据结构不依赖于任何特定的语言是非常重要的。
数据结构只是抽象的“蓝图”，每种编程语言都用它来创建自己的类或特定结构的实现。
例如，最著名的数据结构之一是链表。
你可以去维基百科了解它是如何工作的，有什么优点和缺点。
也许其定义对你来说很熟悉 :)
“链表是数据元素的线性集合，其顺序不是由它们在内存中的物理位置指定的。相反，每个元素都指向下一个元素。”
下图描述了我们心爱的LinkedList，不是吗？
是的，这就是事实 :)
在 Java 中，“链表”数据结构是由 LinkedList 类实现的。
但是其他语言也实现了链表！在 Python 中，这种数据结构被称为“llist”。在 Scala 中称为“LinkedList”，就像在 Java 中一样。
链表是基本的常用数据结构之一，所以你会发现它在任何现代编程语言中都有实现。
关联数组也是如此。这是维基百科提供的定义：“关联数组、映射、符号表或字典是由（键、值）对的集合组成的抽象数据类型，这样每个可能的键在集合中最多出现一次。”
这让你想起什么了吗？:)
没错。对于我们这些 Java 开发人员来说，关联数组就是 Map 接口。但是这个数据结构也是用其他语言实现的！比如 C# 程序员知道它的名字是“字典”。而在 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.util.Stack 类中实现的。我们的纸牌游戏有 3 种描述玩家行为的方法：- 从一副牌中取出一张牌（
getCardFromDeck()方法） - 弃牌（
discard()方法） - 查看顶部的卡（
lookAtTopCard()方法）。让我们假设这是一个“智力”奖励，它允许玩家找出游戏中的下一张牌。
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());
}
}
控制台输出：
Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}
Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}
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
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 实现之一。举个例子，假设你的店里有 50 个人在排队，其中 7 个是 VIP 客户。PriorityQueue 会让你先为他们服务！很有用，对吧？:)
其次，再提一下 Robert Lafore 的书《Java中的数据结构和算法》也无妨。阅读这本书，你不仅会学到许多数据结构（包括栈和队列），而且你还会自行实现其中的许多数据结构！比如 Java 没有 Stack 类怎么办？如果你的程序需要这样的数据结构，你会怎么做？当然，你得自己写。当你读 Lafore 的书时，你会经常这样做。因此，你对数据结构的理解将比你从简单的理论学习中得到的要深刻得多 :)
我们总结了今天学到的理论，但是没有实践，理论什么都不是！任务不会自己解决，而是该由你来解决！:)
GO TO FULL VERSION