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

Kononenko Igor; Robnik Šikonja Marko (2003). Algoritmi in podatkovne strukture 1 (1 izd.). Ljubljana : Fakulteta za računalništvo in informatiko. COBISS 125719552. ISBN 961-6209-37-X.
William Ford; William Topp (2002). Data Structures with C++ and STL (2 izd.). Upper Saddle River, NJ : Prentice Hall. ISBN 0-13-085850-1.

Zunanje povezave