Requisito previo: Stack
Queue en Perl es una estructura de datos abstracta lineal que sigue el orden FIFO (primero en entrar, primero en salir). Se asemeja a las propiedades de la cola que encontramos en nuestra vida diaria donde la persona que llega primero será servida primero. Está abierto en ambos extremos. A diferencia de la pila, donde la operación de inserción y eliminación ocurre en el mismo extremo llamado la parte superior de la pila, en la cola estas operaciones ocurren en diferentes extremos llamados el extremo anterior y posterior de la cola.
Operaciones en cola:
Las siguientes operaciones básicas se realizan en una cola:
- Poner en cola (inserción): añade un elemento a la cola. Se produce una condición de desbordamiento si la cola está llena.
- Dequeue (eliminación): elimina un elemento de la cola. Se produce una condición de subdesbordamiento si la cola está vacía.
- Anverso: Obtener el elemento frontal de la cola.
- Posterior: Obtener el último elemento de la cola.
Crear una cola
Crear una cola en Perl es muy simple. Se puede hacer declarando una array que puede estar vacía o inicializada con algunos datos precargados.
@queue; # Queue is empty. @queue = (1, 2, 3); # Queue with initialized values.
Tipos de colas
En base al criterio de Inserción y eliminación, las colas pueden ser de los siguientes tipos:
cola sencilla
Simple Queue es simplemente una cola en la que la inserción tiene lugar al principio y la eliminación tiene lugar al final de la cola.
En Perl, las operaciones de una cola se pueden implementar utilizando funciones de inserción y desplazamiento .
La función push se usa para agregar uno o más valores al final de la cola.
La función de desplazamiento moverá la cola una unidad hacia la izquierda eliminando (haciendo estallar) el primer elemento. Devolverá undef en caso de cola vacía.
Ejemplos:
Perl
#!/usr/bin/perl use strict; use warnings; # Intitialising the Queue my @queue = (1, 2, 3); # Original queue print "Original Queue: @queue"; # Pushing values into queue push(@queue, (4, 5, 6)); # Updated Queue after # Push operation print("\nUpdated Queue after Push: @queue"); # Popping values from queue my $val1 = shift(@queue); print("\nElement popped is: $val1"); my $val2 = shift(@queue); print("\nElement popped is: $val2"); # Updated Queue after # Pop operations print("\nUpdated Queue after Pop: @queue");
Original Queue: 1 2 3 Updated Queue after Push: 1 2 3 4 5 6 Element popped is: 1 Element popped is: 2 Updated Queue after Pop: 3 4 5 6
cola circular
En la cola circular, la última posición de la cola está conectada a la primera posición para hacer un círculo, también llamado Ring Buffer . Si la cola está vacía desde el frente pero llena al final, también podemos insertar elementos en la cola circular, lo que no es el caso en la cola simple. La cola circular será de tamaño fijo , a diferencia de una cola normal.
Además de las funciones de empujar y cambiar , la cola circular también tiene dos variables delantera y trasera para almacenar las posiciones delantera y trasera de la cola.
Ejemplo:
Perl
#!/usr/bin/perl use strict; use warnings; # Intitialising the Queue my @queue = (1, 2, 3); my $size = 7; # No. of elements to be stored in queue # Initially queue has three elements my $front = 0; my $rear = 2; # Original queue print "Original Queue: @queue"; # Pushing values into queue $rear = ($rear + 1) % $size; my $val = 4; while(1) { if ($rear == $front) { print("\nQueue is full."); last; } else { print("\nPushed $val in queue"); $queue[$rear] = $val; $rear = ($rear + 1) % $size; $val += 1; } } # Updated Queue after # Push operation print("\nUpdated Queue after Push: @queue"); # Popping values from queue my $val1 = $queue[$front]; $queue[$front] = -1; $front = ($front + 1) % $size; print("\nElement popped is: $val1"); my $val2 = $queue[$front]; $queue[$front] = -1; $front = ($front + 1) % $size; print("\nElement popped is: $val2"); # Updated Queue after # Pop operations print("\nUpdated Queue after Pop: @queue"); while(1) { if ($rear % $size == $front) { print("\nQueue is full."); last; } else { print("\nPushed $val in queue"); $queue[$rear] = $val; $rear += 1; $val += 1; } } print("\nUpdated Queue after Push: @queue");
Original Queue: 1 2 3 Pushed 4 in queue Pushed 5 in queue Pushed 6 in queue Pushed 7 in queue Queue is full. Updated Queue after Push: 1 2 3 4 5 6 7 Element popped is: 1 Element popped is: 2 Updated Queue after Pop: -1 -1 3 4 5 6 7 Pushed 8 in queue Pushed 9 in queue Queue is full. Updated Queue after Push: 8 9 3 4 5 6 7
cola de prioridad
En la cola de prioridad, cada elemento tiene una prioridad definida asociada. Un elemento que tenga la menor prioridad será el primero en ser eliminado de la cola de prioridad. Los elementos con la misma prioridad se tratarán en el orden de su
posición en la cola.
Ejemplos:
Perl
#!/usr/bin/perl use strict; use warnings; # Initialising queue with priority my @queue = ([1, 3], [2, 7], [4, 3], [5, 2]); sub pull_highest_prio { my $max = 0; for (my $i = 0; $i < scalar(@queue); $i++) { if ($queue[$i][1] > $queue[$max][1]) { $max = $i; } } print("\nPopped item: $queue[$max][0], ", "Priority: $queue[$max][1]"); splice @queue, $max, 1; } # Driver Code print("\nOriginal Queue is "); for (my $i = 0; $i < 4; $i++) { print("$queue[$i][0] "); } push(@queue, [11, 9]); push(@queue, [7, 0]); print("\nUpdated Queue after push is "); for (my $i = 0; $i < 6; $i++) { print("$queue[$i][0] "); } pull_highest_prio; pull_highest_prio; pull_highest_prio; pull_highest_prio; print("\nUpdated Queue after pop is "); for (my $i = 0; $i < 2; $i++) { print("$queue[$i][0] "); }
Original Queue is 1 2 4 5 Updated Queue after push is 1 2 4 5 11 7 Popped item: 11, Priority: 9 Popped item: 2, Priority: 7 Popped item: 1, Priority: 3 Popped item: 4, Priority: 3 Updated Queue after pop is 5 7
Deque (Cola de doble terminación)
La cola doblemente terminada es solo una versión generalizada de la cola simple, excepto que las operaciones de inserción y eliminación se pueden realizar tanto en el extremo frontal como en el trasero de la cola. Es un tipo de estructura de datos muy importante, ya que se puede utilizar como pila o como cola.
Ejemplos:
Perl
#!/usr/bin/perl use strict; use warnings; # Intitialising the Queue my @queue = (1, 2, 3); my $front = 0; my $rear = 2; sub insert_front { my $val = $_[0]; unshift(@queue, $val); $rear += 1; } sub insert_rear { my $val = $_[0]; push(@queue, $val); $rear += 1; } sub delete_front { print("\nElement popped is: $queue[0]"); splice @queue, 0, 1; $rear -= 1; } sub delete_rear { print("\nElement popped is: $queue[$rear]"); splice @queue, scalar(@queue) - 1, 1; $rear -= 1; } # Original queue print "Original Queue: @queue"; # Pushing values into queue &insert_rear(4); &insert_rear(3); print("\nRear element is $queue[$rear]"); &insert_front(1); &insert_front(7); print("\nFront element is $queue[$front]"); # Updated Queue after # Push operation print("\nUpdated Queue after Push: @queue"); # Popping values from queue delete_rear; delete_front; print("\nFront element is $queue[$front]"); &insert_front(20); delete_rear; print("\nRear element is $queue[$rear]"); # Updated Queue after # Pop operations print("\nUpdated Queue after Pop: @queue");
Original Queue: 1 2 3 Rear element is 3 Front element is 7 Updated Queue after Push: 7 1 1 2 3 4 3 Element popped is: 3 Element popped is: 7 Front element is 1 Element popped is: 4 Rear element is 3 Updated Queue after Pop: 20 1 1 2 3
Implementación abstracta
Abstracto significa ocultar la funcionalidad de las operaciones del usuario normal, es decir, proporcionar la funcionalidad operativa sin definir la lógica detrás de la función.
En Perl, la implementación abstracta de la cola se puede lograr utilizando el módulo integrado de Perl Thread::Queue , que proporciona colas FIFO seguras para subprocesos a las que se puede acceder mediante cualquier cantidad de subprocesos.
Métodos básicos:
- new(list) : crea una nueva cola con la lista de elementos proporcionada o, si no aparece en la lista, crea una nueva cola vacía.
- enqueue (lista) : agrega una lista de elementos al final de la cola.
- dequeue (COUNT) : elimina la cantidad solicitada de elementos del encabezado de la cola, los devuelve y, si no se menciona, elimina un elemento de la cola.
- pendiente() : devuelve la cantidad de elementos que aún quedan en la cola o podemos decir que básicamente devuelve el tamaño de la cola.
- end() : declara que no se agregarán más elementos a la cola.
Ejemplos:
Perl
#!/usr/bin/perl use strict; use warnings; use Thread::Queue; # A new pre-populated queue my $q = Thread::Queue->new(1, 2, 3); sub head { if ($q->pending() == 0) { print("\nThe queue is empty."); } else { my $item = $q->dequeue(); print("\nHead of the Queue is $item."); } } my $isize = $q->pending(); print("Initial size of the queue is $isize"); # insert three items at the back of the queue $q->enqueue(5, 6, 7); &head(); my $size = $q->pending(); print("\nThe size of the queue is $size"); # delete the head item of the queue $q->dequeue(); &head(); # delete two items from the front $q->dequeue(2); my $size2 = $q->pending(); print"\nThe size of the queue is $size2"; &head(); &head(); $q->end();
size of the queue is 3 Head of the Queue is 1. The size of the queue is 5 Head of the Queue is 3. The size of the queue is 1 Head of the Queue is 7. The queue is empty.
Procesamiento paralelo o asíncrono
La palabra Parallel significa simultáneamente o al mismo tiempo y Asynchronous se refiere a continuo o sin bloqueo. Las operaciones de implementación de una cola son de bloqueo, es decir, mientras se realiza una operación, la otra operación tiene que esperar a que finalice primero y luego se ejecuta. Esto está bien para una pequeña cantidad de tareas, pero para una gran cantidad de tareas u operaciones, este tipo de procesamiento es un poco agitado y requiere mucho tiempo.
Para superar este problema, Perl proporciona alguna forma de realizar un procesamiento paralelo o asíncrono para que estas operaciones puedan ejecutarse simultáneamente o sin esperar a que finalicen otras. Las dos soluciones principales para esto son roscar y bifurcar.. Forking es crear exactamente la misma copia de algún proceso y luego estos dos procesos se ejecutan en paralelo sin mucha conexión entre sus variables, aunque manipulan o trabajan sobre las mismas variables (copia). Se hace usando la función fork() .
Ejemplos:
Perl
#!/usr/bin/perl use strict; use warnings; use 5.010; say "PID $$"; my $pid = fork(); die if not defined $pid; say "PID $$ ($pid)";
PID 22112 PID 22112 (22113) PID 22113 (0)
Antes de llamar a fork() , obtuvimos un PID (22112) que es el ID del proceso actual, después de bifurcar obtuvimos dos líneas. La primera línea impresa provino del mismo proceso que el actual (tiene el mismo PID), la segunda línea impresa provino del proceso hijo (con PID 63779). El primero recibió un $pid de la bifurcación que contenía el número del proceso secundario. El segundo, el proceso secundario, obtuvo el número 0.
Perl también es compatible con la programación basada en eventos a través del marco POE .
Publicación traducida automáticamente
Artículo escrito por BhavikBothra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA