CodeGym /Java 博客 /China /数据结构:堆栈和队列
作者
Vasyl Malik
Senior Java Developer at CodeGym

数据结构:堆栈和队列

已在 China 群组中发布
你好!今天我们讨论的内容对任何程序员来说都非常重要:数据结构。 维基百科指出:“数据结构是一种能够实现数据的高效访问和修改的数据组织、管理和存储形式。 更准确地说,数据结构是数据值、数据值之间的关系以及可应用于数据的功能或操作的集合。”这个定义有点混乱,但它的主旨是清楚的。 数据结构是一种存储数据以备将来使用的储存库。 在编程中,数据结构数不胜数。 在解决特定问题时,通常最重要的事情是为该问题选择最合适的数据结构。 而且很多数据结构你已经很熟悉了!例如,你知道数组。你也熟悉Map(这种数据结构也可以称为“字典”或“关联数组”)。 理解数据结构不依赖于任何特定的语言是非常重要的。 数据结构只是抽象的“蓝图”,每种编程语言都用它来创建自己的类或特定结构的实现。 例如,最著名的数据结构之一是链表。 你可以去维基百科了解它是如何工作的,有什么优点和缺点。 也许其定义对你来说很熟悉 :) “链表是数据元素的线性集合,其顺序不是由它们在内存中的物理位置指定的。相反,每个元素都指向下一个元素。” 下图描述了我们心爱的LinkedList,不是吗? 数据结构:堆栈和队列 - 1是的,这就是事实 :) 在 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 张。 她得到了哪些牌? 数据结构:堆栈和队列 - 2控制台输出:

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 原则(“先进先出”)。 这个原理很容易理解,例如,在现实生活中,一个普通的队列!例如,在杂货店排队。 如果有五个人在排队,第一个获得服务的人将是第一个排队的人。如果另一个人(除了已经排队的五个人之外)想买东西并排队,那么他最后得到服务,也就是第六个得到服务的人。 在使用队列时,新元素被添加到尾部(后面),如果你想要获取一个元素,它将从头部(前面)获取。 关于队列如何工作,这是你需要记住的主要原则。 数据结构:堆栈和队列 - 3队列的操作非常直观,因为我们在现实生活中经常看到队列。 值得单独注意的是,在 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 是一个双端队列。 它扩展了常规队列的功能,允许你在队列的两端(头部和尾部)添加元素,并从队列的两端获取元素。 数据结构:堆栈和队列 - 4双端队列广泛应用于软件开发中。 请注意我们上面提供的队列类列表。这个列表很长,但是它包含了什么熟悉的东西吗?

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 的开头和结尾获取元素。它还允许我们在开头和结尾添加元素。 下面是 LinkedListDeque 接口获取的方法:
  • peekFirst() — 返回第一个元素(但不将其从队列中删除)。
  • peekLast() — 返回最后一个元素(但不将其从队列中删除)。
  • pollFirst() — 返回队列中的第一个元素并将其删除。
  • pollLast() — 返回队列中的最后一个项目并将其删除。
  • addFirst() — 将新项目添加到队列的前面。
  • addLast() — 将项目添加到队列的末尾。
如你所见,LinkedList 完全实现了双端队列的功能! 如果你的程序需要这样的功能,你知道在哪里寻找 :) 今天的课就要结束了。 最后,我会给你一些额外阅读的链接。 首先关注这篇关于 PriorityQueue 的文章。 这是最有趣和最有用的 Queue 实现之一。举个例子,假设你的店里有 50 个人在排队,其中 7 个是 VIP 客户。PriorityQueue 会让你先为他们服务!很有用,对吧?:) 其次,再提一下 Robert Lafore 的书《Java中的数据结构和算法》也无妨。阅读这本书,你不仅会学到许多数据结构(包括栈和队列),而且你还会自行实现其中的许多数据结构!比如 Java 没有 Stack 类怎么办?如果你的程序需要这样的数据结构,你会怎么做?当然,你得自己写。当你读 Lafore 的书时,你会经常这样做。因此,你对数据结构的理解将比你从简单的理论学习中得到的要深刻得多 :) 我们总结了今天学到的理论,但是没有实践,理论什么都不是!任务不会自己解决,而是该由你来解决!:)
评论
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION