你好!今天我们讨论的内容对任何程序员来说都非常重要:数据结构。
维基百科指出:“数据结构是一种能够实现数据的高效访问和修改的数据组织、管理和存储形式。
更准确地说,数据结构是数据值、数据值之间的关系以及可应用于数据的功能或操作的集合。”这个定义有点混乱,但它的主旨是清楚的。
数据结构是一种存储数据以备将来使用的储存库。
在编程中,数据结构数不胜数。
在解决特定问题时,通常最重要的事情是为该问题选择最合适的数据结构。
而且很多数据结构你已经很熟悉了!例如,你知道数组。你也熟悉映射(这种数据结构也可以称为“字典”或“关联数组”)。
理解数据结构不依赖于任何特定的语言是非常重要的。
数据结构只是抽象的“蓝图”,每种编程语言都用它来创建自己的类或特定结构的实现。
例如,最著名的数据结构之一是链表。
你可以去维基百科了解它是如何工作的,有什么优点和缺点。
也许其定义对你来说很熟悉 :)
“链表是数据元素的线性集合,其顺序不是由它们在内存中的物理位置指定的。相反,每个元素都指向下一个元素。”
下图描述了我们心爱的链表,不是吗?
是的,这就是事实 :)
在 Java 中,“链表”数据结构是由 LinkedList 类实现的。
但是其他语言也实现了链表!在 Python 中,这种数据结构被称为“llist”。在 Scala 中称为“LinkedList”,就像在 Java 中一样。
链表是基本的常用数据结构之一,所以你会发现它在任何现代编程语言中都有实现。
关联数组也是如此。这是维基百科提供的定义:“关联数组、映射、符号表或字典是由(键、值)对的集合组成的抽象数据类型,这样每个可能的键在集合中最多出现一次。”
这让你想起什么了吗?:)
没错。对于我们这些 Java 开发人员来说,关联数组就是 Map 接口。但是这个数据结构也是用其他语言实现的!比如 C# 程序员知道它的名字是“字典”。而在 Ruby 中,它是在一个名为做“Hash”的类中实现的。
嗯,你明白了:数据结构是编程中的通用概念,每种编程语言都以自己的方式实现数据结构。
今天我们将研究两种这样的结构(堆栈和队列),并了解其是如何在 Java 中实现的。
控制台输出:
队列的操作非常直观,因为我们在现实生活中经常看到队列。
值得单独注意的是,在 Java 中,队列不是由类表示的,而是由接口表示的:Queue。
更何况这个队列接口在 Java 里有很多实现。
如果我们看一下 Oracle 文档,会看到 4 个不同的接口,以及一个令人印象深刻的类列表,它们继承了 Queue 接口:
双端队列广泛应用于软件开发中。
请注意我们上面提供的队列类列表。这个列表很长,但是它包含了什么熟悉的东西吗?

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> discardPile;
public Card getCardFromDeck() {
return deck.pop();
}
public void discard(Card card) {
discardPile.push(card);
}
public Card lookAtTopCard() {
return deck.peek();
}
// ...getter、setter 等
}
如前所述,我们有两个堆栈:一个为抽牌堆,一个为弃牌堆。在 Java 中,堆栈数据结构是在 java.util.Stack 类中实现的。我们的纸牌游戏有 3 种描述玩家行为的方法:- 从一副牌中取出一张牌(getCardFromDeck()方法)
- 弃牌(discard() 方法)
- 查看顶部的卡(lookAtTopCard() 方法)。让我们假设这是一个“智力”奖励,它允许玩家找出游戏中的下一张牌。
- 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("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"));
// 创建弃牌
Stack<Card> discardPile = new Stack<>();
// 开始游戏
SimpleCardGame game = new SimpleCardGame();
game.setDeck(deck);
game.setDiscardPile(discardPile);
// 第一个玩家从这副牌中抽出 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.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”牌是最后一张(第五张),也是玩家最先抽出的那张牌。“Millhouse”是倒数第二张牌,玩家第二个抽出。“Sylvanas”从上面数第三个进入牌堆,这是玩家抽的第三张牌。
接下来,玩家弃牌。首先,她弃了 Edwin,然后 Millhouse,再者是 Sylvanas。
然后,我们逐一展示弃牌堆中的牌:
控制台输出:
Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}
我们再一次了解到堆栈是如何工作的!在我们的游戏中,弃牌堆也是一个堆栈(就像抽牌堆一样)。
“Edwin VanCleef”首先被丢弃。第二张弃牌是 Millhouse Manastorm,它放在弃牌堆中 Edwin 的上面。然后 Sylvanas 被丢弃,这张卡被放在 Millhouse 的上面。
如你所见,堆栈并不复杂。尽管如此,你需要了解这种数据结构 — 在求职面试中经常会被问到,而且它通常是构建更复杂的数据结构的基础。
Java 中的队列
队列是另一种常见的数据结构。 除了栈之外,包括 Java 在内的许多编程语言也实现了队列数据结构。 队列和栈有什么区别? 队列不是基于 LIFO 原则,而是基于 FIFO 原则(“先进先出”)。 这个原理很容易理解,例如,在现实生活中,一个普通的队列!例如,在杂货店排队。 如果有五个人在排队,第一个获得服务的人将是第一个排队的人。如果另一个人(除了已经排队的五个人之外)想买东西并排队,那么他最后得到服务,也就是第六个得到服务的人。 在使用队列时,新元素被添加到尾部(后面),如果你想要获取一个元素,它将从头部(前面)获取。 关于队列如何工作,这是你需要记住的主要原则。
已知的全部子接口
BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>
已知的全部实施类
AbstractQueue, ArrayBlockingQueue, ArrayDeque
ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue
LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue
PriorityBlockingQueue, PriorityQueue, SynchronousQueue
这个列表不小啊!
当然,你不需要马上记住所有这些类和接口 — 您的脑袋可能会爆炸 :)
我们将只考虑几个最重要和最有趣的知识点。
首先,我们来关注一下 Queue 的四个“子接口”之一:Deque。是什么让它如此特别?
Deque 是一个双端队列。
它扩展了常规队列的功能,允许你在队列的两端(头部和尾部)添加元素,并从队列的两端获取元素。

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue
哈!这是我们的老朋友 LinkedList!
所以,它实现了 Queue 接口?但是怎么会是队列呢?毕竟,LinkedList 就是一个链表!
没错,但这并不会妨碍它成为队列 :)下面是它实现的所有接口的列表:
所有实现的接口:
Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>
如你所见,LinkedList 实现了 Deque 接口(同样,这意味着双端队列)。
为什么需要这样做?
这允许我们从 LinkedList 的开头和结尾获取元素。它还允许我们在开头和结尾添加元素。
下面是 LinkedList 从 Deque 接口获取的方法:- peekFirst() — 返回第一个元素(但不将其从队列中删除)。
- peekLast() — 返回最后一个元素(但不将其从队列中删除)。
- pollFirst() — 返回队列中的第一个元素并将其删除。
- pollLast() — 返回队列中的最后一个项目并将其删除。
- addFirst() — 将新项目添加到队列的前面。
- addLast() — 将项目添加到队列的末尾。
GO TO FULL VERSION