Biðröð (tölvunarfræði)

Úr Wikipediu, frjálsa alfræðiritinu
Staki bætt í FIFO biðröð
Staki bætti í forgangsbiðröð.
Stökum bætt í tvíendaröð.
Staki ýtt á stafla.

Biðröð í tölvunarfræði er hugtak yfir gagnagrindur sem líkja eftir ýmsum tegundum biðraða sem fyrirfinnast í hinum efnislega heimi. Í bankanum er fólk þjónustað í þeirri röð sem það kemur inn. Slík biðröð er kölluð FIFO (e. First In First Out), eða fyrstur inn fyrstur út. Þegar staki er bætti í FIFO biðröð er öruggt að það verði fjarlægt á undan öllum stökum sem á eftir koma.

Á neyðarmóttöku eru sjúklingar afgreiddir eftir því hversu alvarlega þeir eru slasaðir. Þar er almenna reglan fyrstur inn fyrstur afgreiddur, en hægt er að gefa sjúklingum hærri forgang sem þess þurfa. Þetta er einkenni á forgangsbiðröð (e.priority queue). Þar fær hvert stak vægi sem gjarnar er heiltala. Misjafnt er hvort hærri tala gefur hærri eða lægri forgang. Heiltalan 0 getur táknað hvort sem er lægsti eða hæsti forgangur.

Stafli er tegund af biðröð sem er mikið notuð. Stafli hefur svipaða eiginleika og stafli af diskum sem staflað er hvor ofan á annan. Hvert stak fer efst á staflann, og þegar stak ef fjarlægt af staflanum er það alltaf það stak sem síðast var sett á hann.

Til eru aðrar útgáfur af biðröðum eins og tvíendaröð (e. double ended queue, deque). Í tvíendaröð er hægt að bæta við og fjarlægja stök á báðum endum biðraðarinnar. Tvíendaröð sameinar eiginleika FIFO biðraðar og hlaða.

Fleiri tegundir af biðröðum eru til sem ekki verða nefndar hér, en allar hafa þær þá eiginleika að stökin eru skipulögð sem einföld röð og aðeins er hægt að bæta við og fjarlægja stök af endum raðarinnar.