Python学习

一、学前花絮

数据结构是所有的计算机语言中非常重要的一部分，前面文章讲述了“栈”、“链表”的实现和用途。今天我们继续数据结构部分的学习，重点讲述一下另一种线性数据结构“队列”，也以C语言和python进行对比。

二、Python和C语言如何实现“线性数据结构”的队列

2.1 线性数据结构的数组和链表介绍

队列（Queue） 是一种非常基础且重要的线性数据结构。它的核心原则是 FIFO (First In, First Out)，即先进先出。

可以把它想象成现实生活中的排队：

队尾 (Rear)： 新来的人必须站在队伍的最后面（入队）。

队头 (Front)： 服务完一个人后，总是从队伍的最前面开始（出队）。

2.2 Python 实现最简单的队列

在 Python 中，虽然可以用内置的 list 实现，但为了保证高效的出队操作（避免移动元素），我们通常使用标准库中的 collections.deque。

下面是一个封装好的类，逻辑清晰且高效：

上面的类中，分别有初始化、检查队列是否为空、入队、出队、查看队头元素、返回队列大小等方法，这都是队列中最为常用的方法。执行代码：

输出结果：

其实我们可以简单理解这种队列实现的是先进先出，符合很多排队场景。比如我们去医院挂号，排在前面的先挂号，先出去。这和栈的后进先出正好相反。队列和栈是为了满足不同的应用场景而定义的数据结构。

2.3 C 语言实现最简单的队列

在 C 语言中，实现队列最推荐的方式是使用链表。因为如果使用数组，出队时需要移动大量元素，效率很低。

这里我为你实现一个链式队列，包含初始化、入队和出队的核心逻辑：

主程序调用：

输出结果如下：

2.4队列适合哪些场景？

队列的“先进先出”特性决定了它非常适合处理顺序处理和解耦的问题。以下是几个最经典的场景：

1. 任务调度与作业排队

这是队列最直观的应用。

l打印队列： 当多台电脑同时发送打印任务时，打印机按照接收顺序将任务放入队列，依次打印。

lCPU 任务调度： 操作系统将等待执行的进程放入队列，先到达的进程先获得 CPU 时间片。

l消息队列： 在软件架构中（如 RabbitMQ, Kafka），生产者发送的消息被放入队列，消费者按照顺序从队列中取出并处理。

2.广度优先搜索

在图论和树的遍历中，广度优先搜索必须使用队列来实现。

l场景： 计算最短路径（如迷宫寻路）、社交网络中查找“二度人脉”、爬虫抓取网页（先抓取当前页的所有链接，再抓取下一层）。

3. 缓冲处理

当数据的产生速度和处理速度不匹配时，队列作为缓冲区非常有用。

l输入/输出缓冲区： 键盘输入时，你敲击键盘的速度可能比系统处理速度快，字符会先暂存在队列中，系统再慢慢读取。

l网络请求处理： 高并发场景下，服务器将请求放入队列，后端服务按能力从队列中消费请求，防止系统瞬间被压垮。

4.模拟现实生活中的排队

l场景： 银行叫号系统、餐厅排队取餐、电梯调度系统（按楼层请求顺序处理）。

2.5 对于线性数据结构的“升华”

我们通过学习线性数据结构的数组、栈、队列和链表，发现一个问题。比如栈的后进先出、队列的先进先出，链表分为单向、双向和循环，而链表的元素之间无非就是指针的指向。

那么是否可以认为栈和队列就是另外一种形式的链表呢？答案是肯定的。这也是学习的乐趣，在思考中成长。

数据结构本质上就是对“数据存放方式”和“访问/操作规则”的定义。栈 (Stack) 和 队列 (Queue)：是“规则”层面的定义，链表 (Linked List)：是“存储关系”层面的定义。

栈和队列可以看作是“特殊的链表”。

l如果你限制链表只能在一端插入和删除，它就是栈。

l如果你限制链表只能在一端插入、另一端删除，它就是队列。

链表也可以实现数组。创建一个空链表，循环读取数组的每个元素，为每个元素创建一个链表节点，并将其链接到前一个节点后面。虽然它们在物理存储上截然不同：数组是连续内存，链表是离散内存，但在逻辑上，链表可以完美地替代数组来存储一组线性数据。

链表可以看做数据结构中“线性关系”的核心——通过指针将数据串联起来。它不受内存连续性的束缚，是线性结构中最灵活、最能体现“动态”特性的数据结构。理解了链表，你就理解了如何在内存中自由地组织数据，这正是编程的精髓之一。

三、小结

通过数据结构“队列”的学习，并以python和C语言实现进行了对比。到本章为止，我们学习了线性数据结构的数组、栈、队列和链表，经过思考后，我们认为链表是核心。理解了这个核心，有助于我们提升对于数据结构使用方法的认知。

让我们保持学习热情，多做练习。我们下期再见！