Vrsta (podatkovna struktura)

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Vrsta je seznam, v katerem so elementi urejeni skladno z vrstnim redom dodajanja. Elemente vedno dodajamo na konec seznama in jih vedno brišemo na začetku seznama. Vrsti zato pravimo tudi FIFO (First-In-First-Out). Značilnost vrste je, da bo element, ki je bil vanjo dodan prvi, iz nje tudi prvi izbrisan. Zahtevo lahko ekvivalentno opišemo tudi s tem, da lahko neki element izbrišemo iz vrste šele, ko smo izbrisali vse elemente, 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 poznamo dve različni implementaciji vrste:

Operacije[uredi | uredi kodo]

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

Primer programa v jeziku C++[uredi | uredi kodo]

Primer je vzet iz knjige Ford-a in Topp-a 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[uredi | uredi kodo]

Glavna lastnost 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 postež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[uredi | uredi kodo]

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 vanj ne moremo shraniti poljubno število elementov, kar omejuje tudi kapaciteto vrste.

Glej tudi[uredi | uredi kodo]

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]