Plik (struktura danych)
W obliczeniowych , wykorzystując plik zwany także kolejka (angielski ogon ) to struktura danych opiera się na zasadzie „ pierwsze weszło, pierwsze wyszło ” lub FIFO, o której mowa w języku angielskim akronimem FIFO ( " pierwsze weszło, pierwsze wyszło » ): Pierwszy elementy dodane do kolejki będą usuwane jako pierwsze.
Opis
Struktura działa jak kolejka : pierwsi, którzy przyjeżdżają, są pierwszymi, którzy wychodzą ( PEPS , FIFO w języku angielskim dla First in, first out ). Kiedy ostatni wchodzący jest pierwszym wychodzącym (LIFO, LIFO Ostatni wchodzący , pierwszy wychodzący w języku angielskim) to stack ( stack ).
Algorytmy stosowane do śledzenia zapasów muszą być zgodne z metodą stosowaną w zarządzaniu zapasami .
Połączone lista których tylko addQueue i removeHead operacje są stosowane stanowi kolejki. Jeśli kolejka jest oparta na tablicy , struktura rejestruje dwa indeksy, jeden odpowiadający ostatniemu, który dotarł, a drugi następnemu do wyjścia.
Kolejki służą do organizowania sekwencyjnego przetwarzania bloków danych o różnym pochodzeniu.
Teoria kolejek , opracowany dla projektowania sieci telefonicznych, linki liczbę użytkowników, liczbę dostępnych kanałów, średni czas zajętości kanału, a czas oczekiwania należy się spodziewać.
Ograniczenia metody
W oprogramowaniu komputerowym zaleta tego szeregowania polega na jego względnej prostocie; jednak karze procesy krótkim czasem wykonania: faktycznie, jeśli uruchamia się po procesie wymagającym dużo czasu obliczeniowego, małym zadaniem (na przykład na serwerze, który zarządza tylko jedną drukarką, drukuje stronę), małe zadanie będzie musiało poczekać na zakończenie zadania, które wymaga znacznie więcej czasu (wydruk stu stron) przed wykonaniem. W czasach komputerów jednoprocesorowych była to najbardziej niezawodna technika zapewniająca wykonywanie operacji w logicznej kolejności.
Algorytm ten jest również używany jako zasada wymiany linii pamięci podręcznej ze względu na prostotę implementacji i niski koszt. Jednak w tym zastosowaniu przedstawia anomalię znaną jako anomalia Belady'ego : zwiększenie liczby pięter w kolejce może mieć negatywny wpływ na wydajność.
Aplikacje
Ta struktura jest używana na przykład:
- ogólnie, do tymczasowego przechowywania transakcji, które muszą czekać na przetworzenie;
- serwery druku, które w ten sposób przetwarzają żądania w kolejności, w jakiej przychodzą, i umieszczają je w kolejce (zwanej również kolejką lub buforowaniem );
- określone silniki wielozadaniowe w systemie operacyjnym , które muszą przydzielać czas maszynowy każdemu zadaniu, bez uprzywilejowania żadnego;
- szerokość przejścia algorytm wykorzystuje kolejce do przechowywania odwiedzanych węzłów;
- tworzenie wszelkiego rodzaju buforów (w języku angielskim „ bufory ” );
- W zarządzaniu zapasami algorytmy muszą uwzględniać zarządzanie zapasami fizycznymi, aby zapewnić fizyczną spójność / wycenę.
Prymitywy
Oto prymitywy powszechnie używane do manipulowania kolejkami. Nie ma standaryzacji prymitywów manipulacji kolejkami. Dlatego ich nazwiska są podawane nieformalnie.
- „Wątek”: dodaje element do kolejki. Odpowiedni termin angielski to enqueue .
- „Scroll”: zwraca następny element w kolejce i usuwa go z kolejki. Odpowiedni termin angielski to dequeue .
- „Czy wiersz jest pusty?” „: Zwraca„ true ”, jeśli kolejka jest pusta,„ false ”w przeciwnym razie.
- „Liczba pozycji w kolejce”: zwraca liczbę pozycji w kolejce.
Przykład w C #
Przykład w 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
}
}
Uwagi i odniesienia
-
queue to angielski termin zapożyczony z francuskiego, podczas gdy plik oznacza plik w tym języku .
-
Por. Alfred Aho , John Hopcroft i Jeffrey Ullman ( tłum. J.-M. Moreau), Struktury danych i algorytmy , Paryż, InterÉditions,1995, 450 pkt. ( ISBN 978-2-7296-0194-2 ) , „Elementary abstract data types”, s. 58-62
-
Bachelet 2011 .
-
Michel Fleutry , Encyklopedyczny słownik elektroniki: angielsko-francuski , Paryż, Dom słownika,1991, 1054 s. ( ISBN 2-85608-043-X ) , str. 699 ; (en) RL Brewster , Telecommunications technology , Chichester, UK, Ellis Horwood,1986, s. 45.
-
Por. „ Kolejki ” na Université P. et M. Curie Paris - Komputerowe systemy operacyjne
Zobacz też
Bibliografia
Powiązane artykuły
Linki zewnętrzne
- Bruno Bachelet , „Queue” , w strukturach danych ,2011( czytaj online )