Vrsta (podatkovna struktura)
Vŕsta je seznam, v katerem so elementi urejeni skladno z vrstnim redom dodajanja. Elementi se vedno dodajajo na konec seznama in se jih vedno briše na začetku seznama. Vrsta se zato imenuje tudi FIFO (First-In-First-Out). Značilnost vrste je, da bo element, ki je bil vanjo dodan prvi, iz nje tudi prvi izbrisan. Zahteva se lahko enakovredno opiše tudi s tem, da se lahko neki element izbriše iz vrste šele, ko so se izbrisali vsi elementi, ki so v vrsto prišli pred njim. Vrsta je primer linearne podatkovne strukture.

Vrste se uporabljajo v računalništvu, transportu, operacijskih raziskavah in ostalih področjih, kjer so različni elementi (podatki, osebe, dogodki, ...) shranjeni za kasnejšo obdelavo.

V računalniških programih obstajata dve različni implementaciji vrste:

 s kazalci 
 s krožnim poljem

Operacije 

Operacije za upravljanje z vrsto v C++ Standard Template Library so naslednje:
bool empty()
vrne true, če je vrsta prazna, drgače vrne false
T& front()
vrne referenco na element na začetku neprazne vrste
void pop()
briše element za začetku neprazne vrste
void push(const T& foo)
vstavi element foo na konec vrste
int size()
vrne število vseh elementov v seznamu

Zgled programa v jeziku C++ 

Zgled je vzet iz knjige Forda in Toppa Data Structures with C++ stran 387.

queue< char > theQueue; // ustvari vrsto znakovnih elementov z imenom "theQueue"
theQueue.push('a');     // v vrsto doda element "a"
theQueue.push('b');     // v vrsto doda element "b", vrsta sedaj vsebuje elemente "a b"
theQueue.push('c');     // v vrsto doda element "c", vrsta sedaj vsebuje elemente "a b c"
cout << "theQueue contains: a b c" << endl << endl;
while( !theQueue.empty() )      // dokler vrsta ni prazna ...
{
    cout << "Size = " << theQueue.size() << endl;   // ... izpiši število elementov v vrsti
    cout << "Value at front = " << theQueue.front() << endl << endl;  // ... izpiši prvi element v vrsti
    theQueue.pop();         // ... in ga odstrani
}

Predstavitev vrste 

Glavna značilnost vrste je možnost dostopa le do prvega in zadnjega elementa strukture. Dodajanje je mogoče le na konec vrste. Omogočeno je brisanje samo prvega elementa v vrsti. Življenjski primeri vrste so lahko ljudje na tekočih stopnicah, deli naprav na proizvodni liniji, vrsta avtomobilov na bencinski črpalki, vrsta ljudi za plačilo dobrin v trgovini, ...

V vseh primerih je objekt na začetku vrste tisti, ki je v vrsto vstopil prvi, medtem ko je na koncu vrste zadnji vstopajoči. Vsak objekt (človek na tekočih stopnicah, avtomobil na bencinski črpalki, ...), ko je postrežen, izstopi iz vrste. Izstop se vedno dogaja na sprednjem delu. Ta dogodek opisuje operacija pop(). Podobno novi objekti prihajajo vedno na konec vrste. Ta dogodek opisuje operacija push(object). Operacija size() pove, koliko objektov je trenutno v vrsti in operacija empty(), če je vrsta prazna.

Dodatne informacije 

Teoretično gledano vrsta nima določene kapacitete. Ne glede na število elementov, ki jih že vsebuje, lahko vedno sprejme nov element. Brisanje pa uspe le v primeru neprazne vrste.

V praksi pa je kapaciteta vrste omejena, odvisno od situacije v kateri je uporabljena. Računalniški pomnilnik je omejen in zato se vanj ne more shraniti poljubnega števila elementov, kar omejuje tudi kapaciteto vrste.

Glej tudi 

 tabela
 sklad – nasprotje od vrste, saj je LIFO (Last-In-First-Out)
 povezani seznam

Viri

Zunanje povezave 

Stack and Queues - Java
Simulacija delovanja vrste

Računalništvo
Vŕsta je seznam , v katerem so elementi urejeni skladno z vrstnim redom dodajanja . Elementi se vedno dodajajo na konec seznama in se jih vedno briše na začetku seznama . Vrsta se zato imenuje tudi FIFO ( First - In - First - Out ) . Značilnost vrste je , da bo element , ki je bil vanjo dodan prvi , iz nje tudi prvi izbrisan . Zahteva se lahko enakovredno opiše tudi s tem , da se lahko neki element izbriše iz vrste šele , ko so se izbrisali vsi elementi , ki so v vrsto prišli pred njim . Vrsta je primer linearne podatkovne strukture . Vrste se uporabljajo v računalništvu , transportu , operacijskih raziskavah in ostalih področjih , kjer so različni elementi ( podatki , osebe , dogodki , \ . . . ) shranjeni za kasnejšo obdelavo . V računalniških programih obstajata dve različni implementaciji vrste : s kazalci s krožnim poljem Operacije Operacije za upravljanje z vrsto v C++ Standard Template Library so naslednje : bool empty ( ) vrne true , če je vrsta prazna , drgače vrne false T & front ( ) vrne referenco na element na začetku neprazne vrste void pop ( ) briše element za začetku neprazne vrste void push ( const T & foo ) vstavi element foo na konec vrste int size ( ) vrne število vseh elementov v seznamu Zgled programa v jeziku C++ Zgled je vzet iz knjige Forda in Toppa Data Structures with C+ + stran queue < char > theQueue ; / / ustvari vrsto znakovnih elementov z imenom " theQueue " theQueue.push ( 'a ' ) ; / / v vrsto doda element " a " theQueue.push ( 'b' ) ; / / v vrsto doda element " b " , vrsta sedaj vsebuje elemente " a b " theQueue.push ( 'c' ) ; / / v vrsto doda element " c " , vrsta sedaj vsebuje elemente " a b c " cout << " theQueue contains : a b c " << endl << endl ; while ( !theQueue . empty ( ) ) / / dokler vrsta ni prazna \ . . . { cout << " Size = " << theQueue.size ( ) << endl ; / / \ . . . izpiši število elementov v vrsti cout << " Value at front = " << theQueue.front ( ) << endl << endl ; / / \ . . . izpiši prvi element v vrsti theQueue.pop ( ) ; / / \ . . . in ga odstrani } Predstavitev vrste Glavna značilnost vrste je možnost dostopa le do prvega in zadnjega elementa strukture . Dodajanje je mogoče le na konec vrste . Omogočeno je brisanje samo prvega elementa v vrsti . Življenjski primeri vrste so lahko ljudje na tekočih stopnicah , deli naprav na proizvodni liniji , vrsta avtomobilov na bencinski črpalki , vrsta ljudi za plačilo dobrin v trgovini , \ . . . V vseh primerih je objekt na začetku vrste tisti , ki je v vrsto vstopil prvi , medtem ko je na koncu vrste zadnji vstopajoči . Vsak objekt ( človek na tekočih stopnicah , avtomobil na bencinski črpalki , \ . . . ) , ko je postrežen , izstopi iz vrste . Izstop se vedno dogaja na sprednjem delu . Ta dogodek opisuje operacija pop ( ) . Podobno novi objekti prihajajo vedno na konec vrste . Ta dogodek opisuje operacija push ( object ) . Operacija size ( ) pove , koliko objektov je trenutno v vrsti in operacija empty ( ) , če je vrsta prazna . Dodatne informacije Teoretično gledano vrsta nima določene kapacitete . Ne glede na število elementov , ki jih že vsebuje , lahko vedno sprejme nov element . Brisanje pa uspe le v primeru neprazne vrste . V praksi pa je kapaciteta vrste omejena , odvisno od situacije v kateri je uporabljena . Računalniški pomnilnik je omejen in zato se vanj ne more shraniti poljubnega števila elementov , kar omejuje tudi kapaciteto vrste . Glej tudi tabela sklad – nasprotje od vrste , saj je LIFO ( Last - In - First - Out ) povezani seznam Viri Zunanje povezave Stack and Queues - Java Simulacija delovanja vrste Računalništvo