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

原创

愚公搬代码

发布于 2023-11-04 21:55:54

2110

发布于 2023-11-04 21:55:54

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

?前言

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

数组（Array）：是一种线性数据结构，它将一组具有相同类型的数据元素存储在一起，并为每个元素分配一个唯一的索引。数组的特点是具有随机访问的能力。
链表（Linked List）：也是一种线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的引用。链表的特点是可以动态地插入或删除节点，但访问某个节点时需要从头开始遍历。
栈（Stack）：是一种后进先出（LIFO）的数据结构，它只能在栈顶进行插入和删除操作。栈通常用于实现递归算法、表达式求值和内存管理等场景。
队列（Queue）：是一种先进先出（FIFO）的数据结构，它可以在队尾插入元素，在队头删除元素。队列通常用于数据的缓存、消息队列和网络通信等场景。
哈希表（Hash Table）：也称为散列表，它是一种根据关键字直接访问数据的数据结构。哈希表通常由数组和散列函数组成，可以在常数时间内进行插入、删除和查找操作。
树（Tree）：是一种非线性数据结构，它由一系列的节点组成，每个节点可以有若干个子节点。树的特点是可以动态地插入或删除节点，常见的树结构包括二叉树、平衡树和搜索树等。
堆（Heap）：是一种特殊的树结构，它通常用于实现优先队列和堆排序等算法。堆分为最大堆和最小堆，最大堆的每个节点的值都大于等于其子节点的值，最小堆则相反。
图（Graph）：是一种由节点和边组成的非线性数据结构，它可以用来表示各种实体之间的关系，如社交网络、路线图和电路图等。图的遍历和最短路径算法是常见的图算法。

?一、队列

?1.基本思想

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

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

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

?2.队列常用操作

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

Enqueue(object obj)：将一个元素添加到队列的末尾。
Dequeue()：将队列的第一个元素移除并返回该元素。
Peek()：返回队列的第一个元素，但不移除该元素。
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）的数据结构，它的优点和缺点如下：

优点：

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

缺点：

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

?5.应用场景

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

模拟排队和等待，如餐厅排队、电影票排队等。
网络数据包的传输和处理，如路由器、网络交换机等设备中常使用队列进行数据包的缓存和转发等。
操作系统进程的调度，如进程的排队、优先级处理等。
多线程编程中的任务队列，如任务的添加、执行、优先级处理等。
生产者消费者模型，如生产者向队列中压入数据，消费者从队列中取出数据进行处理等。
广度优先搜索算法中，通过队列存储待扩展的节点。

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

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

2023腾讯·技术创作特训营第三期

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

2023腾讯·技术创作特训营第三期

登录后参与评论

0 条评论

热度