你好！今天我们将讨论对于任何程序员来说都很重要的事情，比如数据结构。维基百科说： 数据结构（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