【愚公系列】2023年12月 数据结构(五)-队列

举报
愚公搬代码 发表于 2023/12/30 23:56:21 2023/12/30
【摘要】 数据结构是计算机科学中的一个重要概念，它描述了数据之间的组织方式和关系，以及对这些数据的访问和操作。常见的数据结构有：数组、链表、栈、队列、哈希表、树、堆和图。

🏆 作者简介，愚公搬代码
🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。
🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏

🚀前言

数据结构是计算机科学中的一个重要概念，它描述了数据之间的组织方式和关系，以及对这些数据的访问和操作。常见的数据结构有：数组、链表、栈、队列、哈希表、树、堆和图。

  1. 数组（Array）：是一种线性数据结构，它将一组具有相同类型的数据元素存储在一起，并为每个元素分配一个唯一的索引。数组的特点是具有随机访问的能力。

  2. 链表（Linked List）：也是一种线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的引用。链表的特点是可以动态地插入或删除节点，但访问某个节点时需要从头开始遍历。

  3. 栈（Stack）：是一种后进先出（LIFO）的数据结构，它只能在栈顶进行插入和删除操作。栈通常用于实现递归算法、表达式求值和内存管理等场景。

  4. 队列（Queue）：是一种先进先出（FIFO）的数据结构，它可以在队尾插入元素，在队头删除元素。队列通常用于数据的缓存、消息队列和网络通信等场景。

  5. 哈希表（Hash Table）：也称为散列表，它是一种根据关键字直接访问数据的数据结构。哈希表通常由数组和散列函数组成，可以在常数时间内进行插入、删除和查找操作。

  6. 树（Tree）：是一种非线性数据结构，它由一系列的节点组成，每个节点可以有若干个子节点。树的特点是可以动态地插入或删除节点，常见的树结构包括二叉树、平衡树和搜索树等。

  7. 堆（Heap）：是一种特殊的树结构，它通常用于实现优先队列和堆排序等算法。堆分为最大堆和最小堆，最大堆的每个节点的值都大于等于其子节点的值，最小堆则相反。

  8. 图（Graph）：是一种由节点和边组成的非线性数据结构，它可以用来表示各种实体之间的关系，如社交网络、路线图和电路图等。图的遍历和最短路径算法是常见的图算法。

🚀一、队列

🔎1.基本思想

队列是一种线性数据结构，它的基本思想是先进先出（First In First Out，FIFO），即最先进入队列的元素最先被删除。

队列主要包括两个基本操作：入队和出队。入队操作就是将元素插入到队列的尾部，而出队操作则是删除队列的第一个元素。实现队列可以使用数组或链表等不同的数据结构，一般用数组实现的队列称为顺序队列，用链表实现的队列称为链式队列。

队列的应用场景非常广泛，如消息队列、进程调度、路由算法等。队列可以保证先进入队列的元素先被处理，具有较好的时间复杂度和空间复杂度，是一种非常实用的数据结构。

在这里插入图片描述

🔎2.队列常用操作

C#中队列的常用操作包括：

  1. Enqueue(object obj)：将一个元素添加到队列的末尾。

  2. Dequeue()：将队列的第一个元素移除并返回该元素。

  3. Peek()：返回队列的第一个元素，但不移除该元素。

  4. Count属性：获取队列中元素的数量。

以下是C#中使用队列的示例：

using System;
using System.Collections;

class Program
{
    static void Main(string[] args)
    {
        Queue myQueue = new Queue();

        // 向队列中添加元素
        myQueue.Enqueue("C#");
        myQueue.Enqueue("Java");
        myQueue.Enqueue("Python");

        // 获取队列中元素的数量
        Console.WriteLine("队列中元素的数量：{0}", myQueue.Count);

        // 获取并移除队列中的第一个元素
        string firstElement = (string)myQueue.Dequeue();
        Console.WriteLine("第一个元素是：{0}", firstElement);

        // 获取队列中的第一个元素，但不移除该元素
        string peekedElement = (string)myQueue.Peek();
        Console.WriteLine("队列中的第一个元素是：{0}", peekedElement);

        // 遍历队列中的元素
        Console.WriteLine("队列中的元素：");
        foreach (string element in myQueue)
        {
            Console.WriteLine(element);
        }
    }
}

输出结果：

队列中元素的数量：3
第一个元素是：C#
队列中的第一个元素是：Java
队列中的元素：
Java
Python

ConcurrentQueue和Queue的区别

public void Queue()
{
    var test = new ConcurrentQueue<TestModel>();//安全队列
    //var test = Channel.CreateBounded<TestModel>(int.MaxValue);//管道
    //var test = new Stack<TestModel>();//栈
    //var test = new Queue<TestModel>();//队列
    for (int i = 0; i < 1_000_000; i++)
    {
        test.Enqueue(new TestModel());
        //test.Writer.TryWrite(new TestModel()); 
        //test.Push(new TestModel());
        //test.Enqueue(new TestModel()); 
    } 
}

public void QueueIO()
{
    var test = new ConcurrentQueue<TestModel>();
    //var test = Channel.CreateBounded<TestModel>(int.MaxValue);
    //var test = new Stack<TestModel>();
    //var test = new Queue<TestModel>();
    for (int i = 0; i < 1_000_000; i++)
    {
        test.Enqueue(new TestModel());
        //test.Writer.TryWrite(new TestModel()); 
        //test.Push(new TestModel()); 
        //test.Enqueue(new TestModel()); 
    }

    for (int i = 0; i < 1_000_000; i++)
    {
        test.TryDequeue(out var _);
        //test.Reader.TryRead(out var _);
        //test.Pop();
        //test.Dequeue();
    }
}

ConcurrentQueue和Queue的性能差别是纳米级大部分情况下都是使用ConcurrentQueue

🔎3.队列的实现

🦋3.1 基于链表的实现

图解：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

示例：

/* 基于链表实现的队列 */
class LinkedListQueue {
	private ListNode? front, rear; // 头节点 front ，尾节点 rear
	private int queSize = 0;
	public LinkedListQueue() {
		front = null;
		rear = null;
	}
	/* 获取队列的长度 */
	public int size() {
		return queSize;
	}
	/* 判断队列是否为空 */
	public bool isEmpty() {
		return size() == 0;
	}
	/* 入队 */
	public void push(int num) {
		// 尾节点后添加 num
		ListNode node = new ListNode(num);
		// 如果队列为空，则令头、尾节点都指向该节点
		if (front == null) {
			front = node;
			rear = node;
		// 如果队列不为空，则将该节点添加到尾节点后
		} else if (rear != null) {
			rear.next = node;
			rear = node;
		}
		queSize++;
	}
	/* 出队 */
	public int pop() {
		int num = peek();
		// 删除头节点
		front = front?.next;
		queSize--;
		return num;
	}
	/* 访问队首元素 */
	public int peek() {
		if (size() == 0 || front == null)
			throw new Exception();
		return front.val;
	}
	/* 将链表转化为 Array 并返回 */
	public int[] toArray() {
		if (front == null)
			return Array.Empty<int>();
		ListNode node = front;
		int[] res = new int[size()];
		for (int i = 0; i < res.Length; i++) {
			res[i] = node.val;
			node = node.next;
		}
		return res;
	}
}

🦋3.2 基于数组的实现表

图解：
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

示例：

/* 基于环形数组实现的队列 */
class ArrayQueue {
	private int[] nums; // 用于存储队列元素的数组
	private int front; // 队首指针，指向队首元素
	private int queSize; // 队列长度
	public ArrayQueue(int capacity) {
		nums = new int[capacity];
		front = queSize = 0;
	}
	/* 获取队列的容量 */
	public int capacity() {
		return nums.Length;
	}
	/* 获取队列的长度 */
	public int size() {
		return queSize;
	}
	/* 判断队列是否为空 */
	public bool isEmpty() {
		return queSize == 0;
	}
	/* 入队 */
	public void push(int num) {
		if (queSize == capacity()) {
			Console.WriteLine(" 队列已满");
			return;
		}
		// 计算尾指针，指向队尾索引 + 1
		// 通过取余操作，实现 rear 越过数组尾部后回到头部
		int rear = (front + queSize) % capacity();
		// 将 num 添加至队尾
		nums[rear] = num;
		queSize++;
	}
	/* 出队 */
	public int pop() {
		int num = peek();
		// 队首指针向后移动一位，若越过尾部则返回到数组头部
		front = (front + 1) % capacity();
		queSize--;
		return num;
	}
	/* 访问队首元素 */
	public int peek() {
		if (isEmpty())
			throw new Exception();
		return nums[front];
	}
	/* 返回数组 */
	public int[] toArray() {
		// 仅转换有效长度范围内的列表元素
		int[] res = new int[queSize];
		for (int i = 0, j = front; i < queSize; i++, j++) {
			res[i] = nums[j % this.capacity()];
		}
		return res;
	}
}

🔎4.优点和缺点

队列是一种先进先出（FIFO）的数据结构，它的优点和缺点如下：

优点：

  1. 有效管理数据。队列可以帮助有效管理数据，对于需要按照时间顺序进行处理的任务（例如处理网络请求、消息队列等），队列是一个非常有用的工具。
  2. 提高数据处理效率。队列可以在任何时候添加和删除元素，这样可以快速地处理大量的数据。
  3. 实现线程安全。多个线程可以同时使用队列，因为队列是线程安全的，这样可以避免竞态条件（race condition）和其他并发问题。

缺点：

  1. 无法随机访问元素。队列只允许在队列的前端添加元素，在队列的后端删除元素。这种限制意味着无法随机访问元素（例如查找第k个元素）。
  2. 需要额外的空间。队列需要额外的指针或数组来存储队列中的元素，这会导致额外的空间开销。
  3. 队列的长度有限制。队列的长度是有限制的，当队列已经满了时，需要额外的空间来存储更多的元素，这可能导致内存不足或者程序崩溃。

🔎5.应用场景

队列是一种常见的数据结构，其应用场景如下：

  1. 模拟排队和等待，如餐厅排队、电影票排队等。

  2. 网络数据包的传输和处理，如路由器、网络交换机等设备中常使用队列进行数据包的缓存和转发等。

  3. 操作系统进程的调度，如进程的排队、优先级处理等。

  4. 多线程编程中的任务队列，如任务的添加、执行、优先级处理等。

  5. 生产者消费者模型，如生产者向队列中压入数据，消费者从队列中取出数据进行处理等。

  6. 广度优先搜索算法中，通过队列存储待扩展的节点。

在实际开发中，队列还有其他很多的应用场景，使用队列可以方便地实现很多数据结构和算法。

🚀感谢：给读者的一封信

亲爱的读者，

我在这篇文章中投入了大量的心血和时间，希望为您提供有价值的内容。这篇文章包含了深入的研究和个人经验，我相信这些信息对您非常有帮助。

如果您觉得这篇文章对您有所帮助，我诚恳地请求您考虑赞赏1元钱的支持。这个金额不会对您的财务状况造成负担，但它会对我继续创作高质量的内容产生积极的影响。

我之所以写这篇文章，是因为我热爱分享有用的知识和见解。您的支持将帮助我继续这个使命，也鼓励我花更多的时间和精力创作更多有价值的内容。

如果您愿意支持我的创作，请扫描下面二维码，您的支持将不胜感激。同时，如果您有任何反馈或建议，也欢迎与我分享。

在这里插入图片描述

再次感谢您的阅读和支持！

最诚挚的问候， “愚公搬代码”

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据结构 网络
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入