Ogled vira Vrsta (podatkovna struktura)

'''Vŕsta''' je [[seznam (računalništvo)|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 [[podatkovna struktura|podatkovne strukture]].

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

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

* s [[kazalec (računalništvo)|kazalci]] 
* s [[krožno polje|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.

<syntaxhighlight lang="cpp">
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
}
</syntaxhighlight>

== 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 (računalništvo)|tabela]]
* [[sklad (računalništvo)|sklad]] – nasprotje od vrste, saj je [[LIFO]] (''Last-In-First-Out'')
* [[povezani seznam]]

== Viri ==
* {{navedi knjigo |author1=Kononenko Igor|author2=Robnik Šikonja Marko |year=2003 |title=Algoritmi in podatkovne strukture 1|edition=1 |publisher=Ljubljana : Fakulteta za računalništvo in informatiko |isbn=961-6209-37-X |cobiss=125719552 |pages=}}
* {{navedi knjigo |author1=William Ford|author2=William Topp |year=2002 |title=Data Structures with C++ and STL|url=https://archive.org/details/datastructureswi0000ford|edition=2 |publisher=Upper Saddle River, NJ : Prentice Hall |isbn=0-13-085850-1 |cobiss= |pages=}}

== Zunanje povezave ==

*[http://www.javacoffeebreak.com/books/extracts/javanotesv3/c11/s3.html Stack and Queues - Java]
*[http://www.educa.fmf.uni-lj.si/www375/2000/Algoritmi/Java-examples/Queue/Queue.html Simulacija delovanja vrste]

[[Kategorija:Računalništvo]]