Archivo (estructura de datos)
En informática , un archivo también llamado cola ( cola en inglés ) es una estructura de datos basada en el principio " primero en entrar, primero en salir " o FIFO, al que se hace referencia en inglés con el acrónimo FIFO ( " primero en entrar , primero en salir » ): El primero los elementos agregados a la cola serán los primeros en ser eliminados.
Descripción
La estructura funciona como una cola : los primeros en llegar son los primeros en salir ( PEPS , FIFO en inglés para First in, first out ). Cuando el último en entrar es el primero en salir (LIFO, LIFO Último en entrar , primero en salir en inglés) es una pila ( pila ).
Los algoritmos utilizados para rastrear existencias deben ser consistentes con el método utilizado en la gestión de existencias .
Una lista enlazada de la que solo se utilizan las operaciones addQueue y removeHead constituye una cola. Si la cola se basa en una matriz , la estructura registra dos índices, uno correspondiente al último en llegar y el otro al siguiente en salir.
Las colas se utilizan para organizar el procesamiento secuencial de bloques de datos de varios orígenes.
La teoría de las colas , desarrollada para el dimensionamiento de las redes telefónicas, vincula el número de usuarios, el número de canales disponibles, el tiempo medio de ocupación del canal y los tiempos de espera esperados.
Limitaciones del método
En el software de computadora , la ventaja de esta programación radica en su relativa simplicidad; sin embargo penaliza los procesos con un tiempo de ejecución corto: de hecho, si uno se lanza, siguiendo un proceso que requiere mucho tiempo de cálculo, una pequeña tarea (por ejemplo, en un servidor que maneja una sola impresora, imprimir una página), la pequeña La tarea tendrá que esperar al final de la tarea que requiere mucho más tiempo (imprimir cien páginas) antes de ejecutarse. En los días de las máquinas de un solo procesador, esta era la técnica más confiable para garantizar que las operaciones se realizaran en un orden lógico.
Este algoritmo también se utiliza como política de reemplazo de línea de caché debido a su simplicidad de implementación y bajo costo. Sin embargo, en este uso presenta una anomalía conocida como anomalía Belady : aumentar el número de pisos en la cola puede tener un efecto negativo en el rendimiento.
Aplicaciones
Esta estructura se utiliza, por ejemplo:
- en general, para almacenar temporalmente transacciones que deben esperar a ser procesadas;
- los servidores de impresión, que así procesan las solicitudes en el orden en que llegan, y las insertan en una cola (también llamada cola o spool );
- ciertos motores multitarea , en un sistema operativo , que deben asignar tiempo de máquina a cada tarea, sin privilegiar ninguna;
- un algoritmo de recorrido de ancho usa una cola para almacenar los nodos visitados;
- para crear todo tipo de búferes (en inglés " búfer " );
- En la gestión de inventario, los algoritmos deben respetar la gestión de inventario físico para garantizar la coherencia / valoración física.
Primitivas
Aquí están las primitivas que se usan comúnmente para manipular colas. No existe una estandarización para las primitivas de manipulación de colas. Por lo tanto, sus nombres se indican de manera informal.
- "Thread": agrega un elemento a la cola. El término en inglés correspondiente es enqueue .
- "Scroll": devuelve el siguiente elemento de la cola y lo elimina de la cola. El término en inglés correspondiente es dequeue .
- "¿La línea está vacía?" ": Devuelve" verdadero "si la cola está vacía," falso "en caso contrario.
- “Número de elementos en la cola”: devuelve el número de elementos en la cola.
Ejemplo en C #
Ejemplo en C #
using System;
namespace ExempleFile
{
public class File
{
private object[] _File;
private int _PointeurDeTete;
private int _PointeurDeQueue;
private int _Taille;
private int _NbreElements;
#region Constructeur
public File(int Taille)
{
this._Taille = Taille;
this._File = new object[Taille];
this._PointeurDeTete = 0;
this._PointeurDeQueue = 0;
this._NbreElements = 0;
}
#endregion
#region Fonctions
public virtual void Enfiler(object item)
{
lock (this)
{
if (this.EstPleine())
{
throw new Exception("La file est pleine !");
}
else
{
this._File[this._PointeurDeQueue] = item;
this._NbreElements++;
// Pointer sur le prochain elément libre,
// revenir à zéro si on est au bout de la file
this._PointeurDeQueue = this._PointeurDeQueue + 1;
if (this._PointeurDeQueue >= this._File.Length)
{
this._PointeurDeQueue = 0;
}
}
}
}
public virtual object Defiler()
{
lock (this)
{
object item = null;
if (this.EstVide())
{
throw new Exception("La file est vide !");
}
else
{
item = this._File[this._PointeurDeTete];
this._NbreElements--;
// Faire pointer le pointeur de queue sur le prochain élément valide,
// revenir à zéro si on est au bout de la file
this._PointeurDeTete = this._PointeurDeTete + 1;
if (this._PointeurDeTete >= this._File.Length)
{
this._PointeurDeTete = 0;
}
}
return item;
}
}
public virtual bool EstVide()
{
return (this._NbreElements == 0);
}
public virtual bool EstPleine()
{
return (this._NbreElements == this._Taille);
}
public int NbreElements
{
get { return this._NbreElements; }
}
#endregion
}
}
Notas y referencias
-
cola es el término inglés tomado del francés, mientras que archivo designa un archivo en este idioma .
-
Cfr Alfred Aho , John Hopcroft y Jeffrey Ullman ( trad. JM Moreau), estructuras de datos y algoritmos , París, InterÉditions,1995, 450 p. ( ISBN 978-2-7296-0194-2 ) , “Tipos de datos abstractos elementales”, pág. 58-62
-
Bachelet, 2011 .
-
Michel Fleutry , Diccionario enciclopédico de electrónica: inglés-francés , París, La casa del diccionario,1991, 1054 p. ( ISBN 2-85608-043-X ) , pág. 699 ; (en) RL Brewster , tecnología de telecomunicaciones , Chichester, Reino Unido, Ellis Horwood,1986, p. 45.
-
Cf. “ Queues ” , en Université P. et M. Curie Paris - Sistemas operativos de computadora
Ver también
Bibliografía
Artículos relacionados
enlaces externos
- Bruno Bachelet , "Cola" , en Estructuras de datos ,2011( leer en línea )