一、前言
算法是计算机软件的基础，常见算法是软件开发的核心基本功，今年打算深入学习一些算法，记录一些算法理论以及最佳实践，希望可以坚持下去，关注我，我们一起学习，增强我们的基本功。
二、队列介绍与经典操作
我们应该很熟悉队列的特性，先进先出,和我们生活中排队办事是一样的，先来先服务。 队列底层可以通过数组或者链表来实现。
1、用队列实战栈
虽然队列特性和栈特性相反，上文分析了栈可以实现队列，其实队列也可以实现栈。
我们有两种方案可以实现。
- 第一种，通过两个队列实现。
- 第二种，通过1个队列实现。
1个队列怎么实现栈呢？ 我们每次把除队列尾的全部弹出，并且重新加入队列尾部后面。这样一个队列可以达到栈的目的。
2、优先级队列，解决topK问题
优先级队列，可以按元素排序，最大或者最小的元素排在队列头部。
比如我们需要从100个数里面找出最大的3个数。我们可以怎么做呢？我们可以维护一个只有三个元素的优先级队列，队头存最小值，队尾存最大值，每次入队做好排序，同时把队头小的元素优先出队，直到所有元素入队完成，最后队列里留下的数都是比其他元素大的数了。
三、队列实战
leetcode队列实现栈225. 用队列实现栈
- 方案一使用一个队列
class MyStack {
LinkedList<Integer> linkedList = new LinkedList<>();
LinkedList<Integer> linkedList2 = new LinkedList<>();
public MyStack() {
}
public void push(int x) {
linkedList.addLast(x);
}
public int pop() {
int len = linkedList.size();
if(len == 0) {
return 0;
}
int l = len-1;
while(l > 0) {
int v = linkedList.poll();
linkedList2.addLast(v);
l--;
}
int val = linkedList.poll();
linkedList = linkedList2;
linkedList2 = new LinkedList<>();
return val ;
}
public int top() {
return linkedList.peekLast();
}
public boolean empty() {
return linkedList.isEmpty();
}
}
- 方案二使用两个队列
class MyStack {
LinkedList<Integer> linkedList = new LinkedList<>();
public MyStack() {
}
public void push(int x) {
linkedList.addLast(x);
}
public int pop() {
int len = linkedList.size();
if(len == 0) {
return 0;
}
int l = len-1;
while(l > 0) {
int v = linkedList.poll();
linkedList.addLast(v);
l--;
}
return linkedList.poll();
}
public int top() {
return linkedList.peekLast();
}
public boolean empty() {
return linkedList.isEmpty();
}
}
topk问题，347. 前 K 个高频元素
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//先统计频率数量
Map<Integer,Integer> map = new HashMap();
for(int i=0; i<nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i],0) + 1);
}
//只寸k个元素 队列里面保留最大的队头存最小的 从小到大排序 传入比较器
PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>(k, (e1, e2) -> e1.getValue().equals(e2.getValue()) ? 0 : ((e1.getValue()<e2.getValue())? -1 : 1));
//只存两个元素
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
if(queue.size() < k) {
queue.add(entry);
} else {
//超过了k个了，将队列头移除，再入队
Map.Entry<Integer, Integer> e = queue.peek();
//大于队头元素，入队
if(e.getValue() < entry.getValue()) {
queue.poll();
queue.add(entry);
}
}
}
int[] result = new int[k];
int i = 0;
for(Map.Entry<Integer, Integer> q : queue) {
result[i] = q.getKey();
i++;
}
return result;
}
}
四、总结
队列具有先进先出的特性，本文分析了几种常见的使用场景，我们可以通过队列实现栈的能力，也可以实现通过优先级队列解决TopK的问题，其实队列在我们实际开发中使用场景很多的，比如线程池通过队列缓存待执行任务，再比如ReentrantLock里面的公平锁实现也是通过队列来实现的。
算法知识是我们开发的基本功，有空我们学习探索一些算法知识呀！！
