java数据结构队列（数据结构（java）问题：队列颠倒 假设现在需要将一个队列中的元素顺序颠倒,只使用队列操作要）

本文目录

• 数据结构（java）问题：队列颠倒 假设现在需要将一个队列中的元素顺序颠倒,只使用队列操作要
• 数据的基本结构有哪些
• 优先队列通常采用（ ）数据结构实现，向优先队列中插入—个元素时间复杂度为（请作答此空）
• java中的queue类有哪些用法
• 【排序】堆、完全二叉树、堆排序、PriorityQueue、TopK
• 数据结构与算法分析2.表、栈、队列、字符串

数据结构（java）问题：队列颠倒 假设现在需要将一个队列中的元素顺序颠倒,只使用队列操作要

// 双向队列可以吗？如果Deque不让用，那就麻烦了，代码又丑。
// Concole:
//     c
//     b
//     a
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
public class Q {
public static void main(String args) {
Deque《String》 srcQ = new LinkedList《String》();
Deque《String》 destQ = new LinkedList《String》();
srcQ.offer("a");
srcQ.offer("b");
srcQ.offer("c");
Q.reverse(srcQ, destQ);
for (String s : destQ) {
System.out.println(s);
}
}
public static 《T》 void reverse(Deque《T》 src, Deque《T》 dest) {
while (src.size() 》 0) {
dest.offer(src.pollLast());
reverse(src, dest);
}
}
}

数据的基本结构有哪些

数据结构有：1.数组；2.栈；3.队列；4.链表（单链表、双向链表、循环链表）；5.数；6.散列表；7.堆；8.图。数据结构是计算机存储知识数据的方式，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

1、数组

数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。

2、栈

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。

3、队列

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队。

4、链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

5、树

树是一种数据结构，它是由n（n》=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个节点有零个或多个子节点；

• 没有父节点的节点称为根节点；

• 每一个非根节点有且只有一个父节点；

• 除了根节点外，每个子节点可以分为多个不相交的子树；

6、散列表

散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。

7、堆

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；

• 堆总是一棵完全二叉树。

8、图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

优先队列通常采用（ ）数据结构实现，向优先队列中插入—个元素时间复杂度为（请作答此空）

【答案】：C
本题考查数据结构基础知识。普通队列是一种先进先出数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级元素最先删除。优先队列具有最高级先出（largest-in，first-out）行为特征。优先队列一般采用二叉堆数据结构实现，由于是二叉堆，所以插入和删除一个元素时间复杂度均为O(lgn)。本题依次选A、C选项。

java中的queue类有哪些用法

java中的queue类是队列数据结构管理类。在它里边的元素可以按照添加它们的相同顺序被移除。
队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。无论使用哪种排序方式，队列的头都是调用remove()或poll()所移除的元素。在 FIFO 队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个Queue实现必须指定其顺序属性。

offer 添加一个元素并返回true 如果队列已满，则返回false
poll 移除并返问队列头部的元素 如果队列为空，则返回null
peek 返回队列头部的元素 如果队列为空，则返回null
put 添加一个元素 如果队列满，则阻塞
take 移除并返回队列头部的元素 如果队列为空，则阻塞
element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空，则抛出一个
NoSuchElementException异常
注意：poll和peek方法出错进返回null。因此，向队列中插入null值是不合法的。

还有带超时的offer和poll方法重载，例如，下面的调用：
boolean success = q.offer(x,100,TimeUnit.MILLISECONDS);
尝试在100毫秒内向队列尾部插入一个元素。如果成功，立即返回true；否则，当到达超时进，返回false。同样地，调用：
Object head = q.poll(100, TimeUnit.MILLISECONDS);
如果在100毫秒内成功地移除了队列头元素，则立即返回头元素；否则在到达超时时，返回null。
阻塞操作有put和take。put方法在队列满时阻塞，take方法在队列空时阻塞。

Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接 口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。BlockingQueue 继承了Queue接口。

【排序】堆、完全二叉树、堆排序、PriorityQueue、TopK

可以利用堆、外排序的方法来做多个处理单元的结果合并

堆，其实就是一个完全二叉树；
完全二叉树，要么是一个满二叉树，要么叶子节点层为从左到右；
堆，实际中是可以用数组实现的；

规律，把数组脑补成完全二叉树
节点 n 的左孩子为 2*n + 1 ,也就是 n《《1 +1
节点 n 的左孩子为 2*n + 2 ,也就是 n《《1 +2
节点 n 的父节点为 (n-1)/2 ,也就是 (n-1)》》2

堆分为小根堆、大根堆
小根堆：在完全二叉树中， 任何一个子树 的最小值都在头部，小根堆，数组最小值在 arr
大根堆：在完全二叉树中， 任何一个子树 的最大值都在头部，大根堆，数组最大值在 arr

思想：1、根据大根堆的特点，先将一个数组构建成为一个大根堆，这样堆顶就是最大的
2、再将堆顶和最后一个数互换，将最大的数放到最后，随即调整维持大根堆
继续互换、调整。

java实现的堆结构、优先级队列， PriorityQueue()
PriorityQueue当size达到了初始的initialCapacity容量后会进行扩容，每次容量加1。

1-》1
1,2-》1.5
1,2,3-》2
...
准备一个大根堆，一个小根堆
把小于等于大根堆对顶的树插入大根堆，
把大于大根堆对顶的树插入小根堆；
同时，要调整大根堆和小根堆的数量，数量差值不要超过1；
如果大根堆的size大了，就把大根堆 的堆顶取出插入小根堆；
如果小根堆的size大了，就把小根堆 的堆顶取出插入大根堆；
这样就能达到，大根堆，小根堆数量保持平衡，同时大根堆中的小的n/2个数，小根堆中是大的n/2个数，
（大根堆堆顶+小根堆堆顶）/2 就是流的中位数

假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。
思路： 利用一个小根堆，把每个文件的第一条记录取出来，放入小根堆中，那么小根堆的堆顶就是这100条记录中顺序最小的记，它为记录A，也是这100个文件中顺序最小的，将这个堆顶追加到准备的大文件。从记录A原来所在的文件中再取出一条记录，放入小根堆，取出堆顶，如此重复...

思路： 利用一个size为k的堆，求最大的Top K 用小根堆 ，求最小的Top k用大根堆。
我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。

遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，所以时间复杂度就是 O(nlogK)。

使用map《key,count》计数，count放入小根堆中，多个小根堆合并求top10.
分析：假设一条搜索50个字节，10亿条那么就占用了50GB的大小，所以一次对所有数据进行统计是不可行的。
0、准备10个空文件
1、采用hash 算法将日志进行计算之后得到hash值，模10，存放入对应的文件中。那么每个文件大概会有1亿条记录，假设平均每条关键词重复10次，那么就是1000万条关键词，大概500MB，1G的内存是可以存下的
2、使用hashmap对每个小文件中的关键词进行数量统计，对每个小文件的统计的结果存入一个Size为10 的小根堆。
3、对这10个小根堆再进行合并得到最终的Top 10 的搜索关键词

推荐阅读：
数据结构和算法|堆的应用

数据结构与算法分析2.表、栈、队列、字符串

线性表是 n 个数据元素的有限队列，同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，通常是用数组实现。在Java语言中，主要是 java.util.ArrayList 实现。

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），所以对数据元素而言，除了存储其本身的信息之外，还需要一个指示其后继数据元素的信息。

栈（Stack）是限定只能在表尾进行插入或删除的线性表。对栈来说， 表尾称为栈顶，表头称为栈底 。栈又称为后进先出线性表（LIFO，Last In First Out）。Java中由于 java.util.Stack 和 java.util.Vector 先天的设计问题，并不推荐使用；一般使用LinkedList来当作栈。

假设一个算术表达式中可以包含两种括号：圆括号和方括号，且这两种括号可按任意的次序嵌套使用，编写判别给定表达式中所含括号是否正确配对出现的算法。

迷宫问题是栈的典型应用，栈通常也与回溯算法连用，回溯算法的基本描述是：

尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径的通道块（否则只能在死胡同内转圈）。

为实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想如下：
(1) 首先置操作数栈OPND为空栈，表达式起始符"#"为运算符栈OPTR的栈底元素；
(2) 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR的栈顶元素符比较优先权后作相应操作，直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为"#")。

一个直接调用自己或通过一系列的调用语句间接地调用自己的函数。

假设有3个分别命名为X、Y和Z的塔座，在塔座X上插有n阶Hanoi塔个直径大小各不相同、依小到大编号1,2,...,n的圆盘。现要求将X轴上的n阶Hanoi塔个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则：

用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。和线性表的单链表一样，为了操作方便起见，我们也给链队列添加一个 头结点 ，并令头指针指向头结点。由此，空的链队列的判断条件为头指针和尾指针均指向头结点，如图所示：

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。
在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。队空和队满的情况如图：

双端队列，是限定插入和删除操作在表的两端进行的线性表，尽管双端队列看起来比栈和队列灵活，但实际上在应用程序中远不及栈和队列有用。