刷算法,你应该知道的队列经典应用

简介: 文章介绍了队列的基本特性和经典应用,包括如何用队列实现栈、使用优先级队列解决Top K问题,并通过LeetCode题目示例展示了队列在算法实现中的应用。

一、前言

算法是计算机软件的基础,常见算法是软件开发的核心基本功,今年打算深入学习一些算法,记录一些算法理论以及最佳实践,希望可以坚持下去,关注我,我们一起学习,增强我们的基本功。

二、队列介绍与经典操作

我们应该很熟悉队列的特性,先进先出,和我们生活中排队办事是一样的,先来先服务。 队列底层可以通过数组或者链表来实现。

image.png

1、用队列实战栈

虽然队列特性和栈特性相反,上文分析了栈可以实现队列,其实队列也可以实现栈

image.png

我们有两种方案可以实现。

  • 第一种,通过两个队列实现。

image.png

  • 第二种,通过1个队列实现。

1个队列怎么实现栈呢? 我们每次把除队列尾的全部弹出,并且重新加入队列尾部后面。这样一个队列可以达到栈的目的。

image.png

2、优先级队列,解决topK问题

优先级队列,可以按元素排序,最大或者最小的元素排在队列头部。

比如我们需要从100个数里面找出最大的3个数。我们可以怎么做呢?我们可以维护一个只有三个元素的优先级队列,队头存最小值,队尾存最大值,每次入队做好排序,同时把队头小的元素优先出队,直到所有元素入队完成,最后队列里留下的数都是比其他元素大的数了。

image.png

三、队列实战

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里面的公平锁实现也是通过队列来实现的。

算法知识是我们开发的基本功,有空我们学习探索一些算法知识呀!!

服务端技术栈.png

相关文章
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
【自然语言处理】TF-IDF算法在人工智能方面的应用,附带代码
TF-IDF算法在人工智能领域,特别是自然语言处理(NLP)和信息检索中,被广泛用于特征提取和文本表示。以下是一个使用Python的scikit-learn库实现TF-IDF算法的简单示例,并展示如何将其应用于文本数据。
212 65
|
2月前
|
存储 人工智能 自然语言处理
算法、系统和应用,三个视角全面读懂混合专家(MoE)
【8月更文挑战第17天】在AI领域,混合专家(MoE)模型以其独特结构成为推动大型语言模型发展的关键技术。MoE通过动态选择专家网络处理输入,实现条件计算。稀疏型MoE仅激活部分专家以减少计算负担;软MoE则加权合并专家输出提升模型稳定性。系统层面,MoE优化计算、通信与存储,利用并行化策略提高效率。在NLP、CV、推荐系统等领域展现强大应用潜力,但仍面临训练稳定性、可解释性等挑战。[论文链接: https://arxiv.org/pdf/2407.06204]
187 63
|
7天前
|
存储 算法 前端开发
深入理解操作系统:进程调度与优先级队列算法
【9月更文挑战第25天】在操作系统的复杂世界中,进程调度是维持系统稳定运行的核心机制之一。本文将深入探讨进程调度的基本概念,分析不同的进程调度算法,并着重介绍优先级队列算法的原理和实现。通过简洁明了的语言,我们将一起探索如何优化进程调度,提高操作系统的效率和响应速度。无论你是计算机科学的初学者还是希望深化理解的专业人士,这篇文章都将为你提供有价值的见解。
|
5天前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习中的优化算法及其应用
本文旨在探讨深度学习中常用的优化算法,包括梯度下降、动量方法、AdaGrad、RMSProp和Adam等。通过分析每种算法的原理、优缺点及适用场景,揭示它们在训练深度神经网络过程中的关键作用。同时,结合具体实例展示这些优化算法在实际应用中的效果,为读者提供选择合适优化算法的参考依据。
|
6天前
|
算法 前端开发 机器人
一文了解分而治之和动态规则算法在前端中的应用
该文章详细介绍了分而治之策略和动态规划算法在前端开发中的应用,并通过具体的例子和LeetCode题目解析来说明这两种算法的特点及使用场景。
一文了解分而治之和动态规则算法在前端中的应用
|
12天前
|
算法 调度
贪心算法基本概念与应用场景
尽管贪心算法在许多问题中都非常有效,但它并不总是会产生最优解。因此,在应用贪心算法前,重要的是先分析问题是否适合采用贪心策略。一些问题可能需要通过动态规划或回溯等其他算法来解决,以找到确切的全局最优解。
41 1
WK
|
15天前
|
机器学习/深度学习 算法 数据挖掘
PSO算法的应用场景有哪些
粒子群优化算法(PSO)因其实现简单、高效灵活,在众多领域广泛应用。其主要场景包括:神经网络训练、工程设计、电力系统经济调度与配电网络重构、数据挖掘中的聚类与分类、控制工程中的参数整定、机器人路径规划、图像处理、生物信息学及物流配送和交通管理等。PSO能处理复杂优化问题,快速找到全局最优解或近似解,展现出强大的应用潜力。
WK
18 1
|
24天前
|
机器学习/深度学习 算法 Python
群智能算法:深入解读人工水母算法:原理、实现与应用
近年来,受自然界生物行为启发的优化算法备受关注。人工水母算法(AJSA)模拟水母在海洋中寻找食物的行为,是一种新颖的优化技术。本文详细解读其原理及实现步骤,并提供代码示例,帮助读者理解这一算法。在多模态、非线性优化问题中,AJSA表现出色,具有广泛应用前景。
|
6天前
|
算法 前端开发
一文了解贪心算法和回溯算法在前端中的应用
该文章深入讲解了贪心算法与回溯算法的原理及其在前端开发中的具体应用,并通过分析LeetCode题目来展示这两种算法的解题思路与实现方法。
|
1月前
|
机器学习/深度学习 算法 数据挖掘
R语言中的支持向量机(SVM)与K最近邻(KNN)算法实现与应用
【9月更文挑战第2天】无论是支持向量机还是K最近邻算法,都是机器学习中非常重要的分类算法。它们在R语言中的实现相对简单,但各有其优缺点和适用场景。在实际应用中,应根据数据的特性、任务的需求以及计算资源的限制来选择合适的算法。通过不断地实践和探索,我们可以更好地掌握这些算法并应用到实际的数据分析和机器学习任务中。
下一篇
无影云桌面