Fil (datastruktur)
I computing er en fil, også kaldet kø (engelsk hale ), en datastruktur baseret på princippet " først ind, først ud " eller FIFO, der henvises til på engelsk ved akronymet FIFO ( " første ind, først ud " ): Den første elementer, der føjes til køen, fjernes først.
Beskrivelse
Strukturen fungerer som en kø : de første, der ankommer, er de første, der forlader ( PEPS , FIFO på engelsk til First in, first out ). Når den sidste ind er den første ud (LIFO, LIFO Last in, først ud på engelsk) er en stak ( stak ).
De algoritmer, der bruges til at spore aktier, skal være i overensstemmelse med den metode, der anvendes i lagerstyring .
En sammenkædet liste over hvilke kun de addQueue og removeHead operationer bliver brugt udgør en kø. Hvis køen er baseret på en matrix , registrerer strukturen to indekser, den ene svarer til den sidste ankomne, den anden til den næste for at afslutte.
Køer bruges til at organisere den sekventielle behandling af datablokke af forskellig oprindelse.
Den teori om køer , der er udviklet til dimensionering af telefonnet, links antallet af brugere, at antallet af tilgængelige kanaler, den gennemsnitlige benyttelsesperiode af kanalen, og ventetiden forventes.
Metodens begrænsninger
I edb -software , den fordel, at denne planlægning ligger i sin relative enkelhed; dog straffer det processerne med kort udførelsestid: hvis man starter, efter en proces, der kræver meget beregningstid, en lille opgave (for eksempel i en server, der kun administrerer en printer, udskriver en side), den lille opgaven bliver nødt til at vente på slutningen af opgaven, hvilket kræver meget mere tid (udskrivning af hundrede sider), før den udføres. I dagene med maskiner med en processor var dette den mest pålidelige teknik til at sikre, at operationer blev udført i en logisk rækkefølge.
Denne algoritme bruges også som en politik til udskiftning af cache-linje på grund af dens enkle implementering og lave omkostninger. Imidlertid præsenterer det i denne brug en anomali kendt som Belady-anomali : at øge antallet af etager i køen kan have en negativ effekt på ydeevnen.
Ansøgninger
Denne struktur bruges f.eks.
- generelt at midlertidigt gemme transaktioner, som skal vente på at blive behandlet;
- printerserverne, som således behandler anmodningerne i den rækkefølge, de ankommer, og indsætter dem i en kø (også kaldet en kø eller spool );
- visse multitasking- motorer i et operativsystem , der skal tildele maskintid til hver opgave uden at have privilegier;
- en bredde traversalgoritme bruger en kø til at gemme de besøgte noder;
- at oprette alle slags buffere (på engelsk " buffere " );
- I lagerstyring skal algoritmer respektere fysisk lagerstyring for at sikre fysisk konsistens / værdiansættelse.
Primitiver
Her er de primitiver, der ofte bruges til at manipulere køer. Der er ingen standardisering for kømanipulation primitiver. Deres navne er derfor angivet uformelt.
- "Tråd": tilføjer et element i køen. Det tilsvarende engelske udtryk er enqueue .
- "Rul": returnerer det næste element i køen og fjerner det fra køen. Det tilsvarende engelske udtryk er dequeue .
- "Er linjen tom?" ": Returnerer" sandt ", hvis køen er tom, ellers falsk".
- “Antal varer i køen”: returnerer antallet af varer i køen.
Eksempel i C #
Eksempel i 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
}
}
Noter og referencer
-
kø er den engelske term lånt fra fransk, mens filen angiver en fil i dette sprog .
-
Jf. Alfred Aho , John Hopcroft og Jeffrey Ullman ( overs. J.-M. Moreau), datastrukturer og algoritmer , Paris, InterÉditions,1995, 450 s. ( ISBN 978-2-7296-0194-2 ) , “Elementære abstrakte datatyper”, s. 58-62
-
Bachelet 2011 .
-
Michel Fleutry , encyklopædisk elektronikordbog: engelsk-fransk , Paris, ordbogens hus,1991, 1054 s. ( ISBN 2-85608-043-X ) , s. 699 ; (en) RL Brewster , telekommunikationsteknologi , Chichester, UK, Ellis Horwood,1986, s. 45.
-
Jf. “ Køer ” , om Université P. et M. Curie Paris - Computeroperativsystemer
Se også
Bibliografi
Relaterede artikler
eksterne links
- Bruno Bachelet , "Kø" , i datastrukturer ,2011( læs online )