Perl 实现一个队列
Perl中的 队列 是一种线性的抽象数据结构,它遵循 先进先出 的顺序。它类似于我们在日常生活中遇到的队列的特性,即谁先来谁就先得到服务。它在两端都是开放的。与堆栈不同的是,插入和删除的操作发生在被称为堆栈 顶部 的同一端,在队列中,这些操作发生在被称为队列 前端 和 后 端的不同一端。
对队列的操作
以下是对队列的基本操作。
- Enqueue(插入): 向队列中添加一个项目。如果队列满了,会出现 溢出 条件。
- Dequeue(删除): 从队列中删除一个项目。如果队列是空的,会发生 下溢 条件。
- Front(前): 从队列中获取前面的项目。
- rear: 从队列中获取最后一个项目。
创建一个队列
在Perl中创建一个队列非常简单。它可以通过声明一个数组来完成,这个数组可以是空的,也可以用一些预先填充的数据进行初始化。
队列的类型
根据插入和删除的标准,队列可以有以下类型。
简单队列
简单队列是一个简单的队列,插入发生在队列的前端,删除发生在队列的末端。
在Perl中,队列的操作可以用 push 和 shift 函数来实现。
push 函数用来在队列的末端添加一个或多个值。
shift 函数将队列向左移动一个单位,删除(弹出)第一个元素。在队列为空的情况下,它将返回 undef 。
例子
输出
循环队列
在圆形队列中,队列的最后一个位置与第一个位置相连,形成一个圆形,也被称为 环形缓冲区。 如果队列的前端是空的,但末端是满的,那么我们也可以在循环队列中插入元素,这在简单队列中是不存在的。圆形队列的 大小是固定的 ,与普通队列不同。
除了 push 和 shift 函数外,圆形队列还有两个变量 front 和 rearrow 来存储队列的前部和后部位置。
例子
输出
优先级队列
在优先级队列中,每个项目都有一个定义的 优先级 与之相关。优先级最低的项目将首先被从优先级队列中删除。具有相同优先级的项目将按照它们在队列中的顺序进行处理,
。
例子
输出
Deque(Doubly Ended Queue)
双端队列只是简单队列的一个通用版本,除了插入和删除操作,可以在队列的 前端 和 后端 都进行。它是一种非常重要的数据结构类型,因为它既可以作为堆栈也可以作为队列使用。
例子
输出
抽象实现
在Perl中,队列的抽象实现可以通过Perl的内置模块 Thread::Queue 来实现,它提供了线程安全的FIFO队列,可以被任意数量的线程访问。
基本方法 。
- new(list) – 用提供的项目列表创建一个新队列,如果没有列出,则创建一个新的空队列。
- enqueue(list) – 在队列的末端添加一个项目列表。
- dequeue(COUNT) – 从队列头部移除所要求的项目数量,并返回它们,如果没有提到,它从队列中取消一个元素。
- pending() – 返回队列中还剩下的项目数,或者我们可以说,它基本上返回队列的大小。
- end() – 声明不再有项目被添加到队列中。
例子
输出
平行或异步处理
并行 的意思是同时或在同一时间,而 异步 的意思是连续或无阻塞的。队列的执行操作是阻塞的,即在执行一个操作时,其他操作必须先等待它结束,然后再执行。这对于少量的任务来说是没有问题的,但是对于大量的任务或操作来说,这种处理方式就显得有点忙乱和费时了。
为了克服这个问题,Perl提供了一些进行并行或异步处理的方法,这样这些操作就可以同时运行或不需要等待其他操作结束。这方面的两个主要解决方案是 线程 和 分叉。 分叉是指创建完全相同的某个进程的副本,然后这两个进程平行地执行,尽管它们操作或处理相同的变量(副本),但它们的变量之间没有什么联系。这是用 fork() 函数完成的。
例子
输出
在调用 fork() 之前,我们得到了一个PID(22112),这是当前进程的进程ID,在分叉之后,我们得到了两行。第一行是来自与当前进程相同的进程(它有相同的PID),第二行是来自子进程(PID为63779)。第一行从fork收到一个$pid,包含子进程的编号。第二个,子进程得到的数字是0。
Perl也通过POE框架支持事件驱动的编程。