数据结构：堆栈和队列

你好！今天我们讨论的内容对任何程序员来说都非常重要：数据结构。 维基百科指出：“数据结构是一种能够实现数据的高效访问和修改的数据组织、管理和存储形式。 更准确地说，数据结构是数据值、数据值之间的关系以及可应用于数据的功能或操作的集合。”这个定义有点混乱，但它的主旨是清楚的。 数据结构是一种存储数据以备将来使用的储存库。 在编程中，数据结构数不胜数。 在解决特定问题时，通常最重要的事情是为该问题选择最合适的数据结构。 而且很多数据结构你已经很熟悉了！例如，你知道数组。你也熟悉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 中，堆栈数据结构是在 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”牌是最后一张（第五张），也是玩家最先抽出的那张牌。“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 原则（“先进先出”）。 这个原理很容易理解，例如，在现实生活中，一个普通的队列！例如，在杂货店排队。 如果有五个人在排队，第一个获得服务的人将是第一个排队的人。如果另一个人（除了已经排队的五个人之外）想买东西并排队，那么他最后得到服务，也就是第六个得到服务的人。 在使用队列时，新元素被添加到尾部（后面），如果你想要获取一个元素，它将从头部（前面）获取。 关于队列如何工作，这是你需要记住的主要原则。 队列的操作非常直观，因为我们在现实生活中经常看到队列。 值得单独注意的是，在 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。是什么让它如此特别？ 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 的书时，你会经常这样做。因此，你对数据结构的理解将比你从简单的理论学习中得到的要深刻得多 :) 我们总结了今天学到的理论，但是没有实践，理论什么都不是！任务不会自己解决，而是该由你来解决！:)