栈和队列的基本结构

定义：栈是一种只能在一端进行插入或删除操作的线性表。允许插入和删除的一端被称为栈顶（动态变化），另一端被称为栈底（固定不变），栈的插入和删除被分别称作入栈和出栈。

特点：先进后出（FILO）。

存储结构：顺序栈和链式栈。

2、队列

定义：队列为一种只允许在表的一端进行插入，在一端进行删除的受限制的线性表。允许插入的一端叫做队尾，允许删除的一端叫做队头，队列的插入和删除被分别称作进队和出队。

特点：先进先出（FIFO）。

存储结构：顺序队和链队。

两个栈实现一个队列

【算法思想】

1>设计类

成员变量：给两个栈s1和s2来模拟实现一个队列

成员函数：入队Push()和出队Pop()

2>给两个指向栈对象s1、s2的指针input和output，分别用来入队和出队

3>按照先进先出的方式模拟入队和出队操作

Push：将input指向不空的栈，然后在input中入队

Pop：将input所指栈中的前n-1(n为栈中元素个数)的数据先转移到output所指的栈中，同时pop掉input中的前n-1个元素，最后pop掉input中的最后一个元素，即可实现先进先出。

问：简单说说什么是 Queue 以及 PriorityQueue 与 LinkedList 的区别及特点？

答：首先 Queue 是一种模拟 FIFO 队列的数据结构，新元素插入（offer）到队列的尾部，访问元素（poll）返回队列头部，一般队列不允许随机访问队列中的元素。Queue 接口主要定义了如下几个方法：

//将指定元素加入队列尾部void add(Object e);//获取队列头部元素，但是不删除该元素，如果队列为空抛出 NoSuchElementException 异常Object element();//将指定元素加入队列尾部（当使用有容量限制的队列时此方法比 add(Object e) 更好）boolean offer(Object e);//获取队列头部元素，但是不删除该元素，如果队列为空返回 nullObject peek();//获取队列头部元素并删除该元素，如果队列为空则返回 nullObject poll();//获取队列头部元素并删除该元素，如果队列为空抛出 NoSuchElementException 异常Object remove(); 

LinkedList 是一个比较奇怪的类，其即实现了 List 接口又实现了 Deque 接口（Deque 是 Queue 的子接口），而 LinkedList 的实现是基于双向链表结构的，其容量没有限制，是非并发安全的队列，所以不仅可以当成列表使用，还可以当做双向队列使用，同时也可以当成栈使用（因为还实现了 pop 和 push 方法）。此外 LinkedList 的元素可以为 null 值。

PriorityQueue 是一个优先级列表队列，因为 PriorityQueue 保存队列元素的顺序并不是按加入队列的顺序，而是按队列元素的大小进行重新排序，所以当调用 peek 或者 pull 方法从队列头取元素时并不是取出最先进入队列的元素，而是取出队列中最小的元素（默认顺序），所以说 PriorityQueue 实质违反了 FIFO 队列的基本原则，从而成了优先级列表实现，同时 PriorityQueue 的实现是基于动态扩容数组的二叉树堆结构，其最大容量长度为 Int 大小，是非并发安全的队列。此外 PriorityQueue 的元素不可为 null 值。

问：PriorityQueue 是怎么确定哪一个元素的优先级最高的？

答：PriorityQueue 确定最高优先级元素使用的是堆数据结构，因为堆是一棵完全树，堆中某个节点的值总是不大于或不小于其父节点值的，常见的堆有二叉堆、斐波那契堆等，二叉堆是完全二叉树或者是近似完全二叉树的一种特殊堆，其分为最大堆和最小堆，最大堆中父结点值总是大于或等于任何一个子节点值，最小堆中父结点值总是小于或等于任何一个子节点值，由于二叉堆一直是自左向右自上向下一层层填充的，所以其可以用数组来表示而不是用链表，PriorityQueue 就是采用了基于动态数组的二叉堆来确定优先级。

问：什么是 Vector 和 Stack，各有什么特点？

答：Vector 是线程安全的动态数组，同 ArrayList 一样继承自 AbstractList 且实现了 List、RandomAccess、Cloneable、Serializable 接口，内部实现依然基于数组，Vector 与 ArrayList 基本是一致的，唯一不同的是 Vector 是线程安全的，会在可能出现线程安全的方法前面加上 synchronized 关键字，其和 ArrayList 类似，随机访问速度快，插入和移除性能较差（数组原因），支持 null 元素，有顺序，元素可以重复，线程安全。Stack 是继承自 Vector 基于动态数组实现的线程安全栈，不过现在已经不推荐使用了，Stack 是并发安全的后进先出，实现了一些栈基本操作的方法（其实并不是只能后进先出，因为继承自 Vector，所以可以有很多操作，严格说不是一个栈）。其共同点都是使用了方法锁（即 synchronized）来保证并发安全的。

问：简单说说 ArrayList 和 Vector 的区别？

答：ArrayList 在默认数组容量不够时默认扩展是 1.5 倍，Vector 在 capacityIncrement 大于 0 时扩容 capacityIncrement 大小，否则扩容为原始容量的 2 倍。Vector 属于线程安全级别的，而 ArrayList 是非线程安全的。具体感兴趣可以去看二者源码。

问：为什么现在都不提倡使用 Vector 了？

答：因为 Vector 实现并发安全的原理是在每个操作方法上加锁，这些锁并不是必须要的，在实际开发中一般都是通过锁一系列的操作来实现线程安全，也就是说将需要同步的资源放一起加锁来保证线程安全，如果多个 Thread 并发执行一个已经加锁的方法，但是在该方法中又有 Vector 的存在，Vector 本身实现中已经加锁了，双重锁会造成额外的开销，即 Vector 同 ArrayList 一样有 fail-fast 问题（即无法保证遍历安全），所以在遍历 Vector 操作时又得额外加锁保证安全，还不如直接用 ArrayList 加锁性能好，所以在 JDK 1.5 之后推荐使用 java.util.concurrent 包下的并发类。此外 Vector 是一个从 JDK1.0 就有的古老集合，那时候 Java 还没有提供系统的集合框架，所以在 Vector 里提供了一些方法名很长的方法（如 addElement(Object obj)，实际上这个方法和 add(Object obj) 没什么区别），从 JDK1.2 以后 Java 提供了集合框架，然后就将 Vector 改为实现 List 接口，从而导致 Vector 里有一些重复的方法。

HashMap 和 HashTable的主要区别？

2. 键值是否能为空：HashMap中键值 允许为空 ，Hashtable 不行

3. 安全性： Hashtable 是同步的线程安全的，HashMap则不具备线程安全特性

4. 默认容积：HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。HashMap默认的初始化大小为16，之后每次扩充为原来的2倍。

，多线程环境中推荐是ConcurrentHashMap。

HashSet和HashMap的区别？

HashMap 底层结构、原理

底层结构原理以及延伸内容比较多，后面再用一个专门文章介绍

閱讀更多 全棧取經之路 的文章

關鍵字: 数据结构 面试 队列