Kezdő útmutató a sorok és a prioritási sorok megértéséhez

Programozóként különböző adatstruktúrákkal dolgozhat a projektek hatókörétől függően. Az egyik ilyen koncepció a sor adatstruktúrája; a sorok elengedhetetlenek a diákok számára, és számos fontos algoritmusban használatosak. A sorokhoz hasonlóan a prioritási sorok is hasonló fogalommal rendelkeznek, de néhány alapvető különbséggel rendelkeznek.

Olvassa el, hogy megértse a sorokat és a prioritási sorokat.

Mi az a sor?

A sor egy egyszerű adatstruktúra, amely számos alkalmazással rendelkezik a valós kódolási projektekben. Az adatstruktúrák eleve elvontak, de az egyszerűség kedvéért elképzeljük, hogy egy sor adatstruktúrájának lineáris alakja van, két különböző véggel.

Az idő összetettségét tekintve a sor lehetővé teszi a beillesztést (sorba állítást) és törlést (dequeue) O (1) időben. Aszimptotikus hatékonysága miatt a sorok hatékonyak a nagy adathalmazokhoz. A várólisták FIFO (first-in-first-out) jellegűek, ami azt jelenti, hogy az elsőként beszúrt adatelem lesz először elérhető. Ezzel szemben a veremnek LIFO (last-in-first-out) jellege van, és csak egy nyitott vége van.

Képzelje el a mozis jegysorát; minden új ügyfél, aki érkezik, csatlakozik a sorhoz az egyik végén. Minden ügyfél egyenként vásárol jegyet, és a kezelőfelületről kilép a sorból. A sor adatstruktúrája pontosan úgy működik, mint a valós sorok, és az adatokat az egyik végén beszúrjuk (sorba állítjuk), a másik végén eltávolítjuk (sorba állítjuk). Most remélhetőleg megértheti az érvelést, hogy miért követik a sorok a FIFO módszertanát.

Egy sor rengeteg valós kódolási alkalmazást tartalmaz. Gyakrabban használják olyan alkalmazásokban, ahol az adatokat nem azonnal, hanem FIFO sorrendben kell feldolgozni. A lemezütemezés, az aszinkron adatátvitel, a szemaforok néhány tipikus alkalmazás. Az érkezési sorrend szerinti ütemezési feladatok, például a nyomtatási sorkezelés vagy a beviteli eszköz pufferei szintén várólistát használnak.

Mi az elsőbbségi sor?

A prioritási sor hasonló a sorhoz, de további tulajdonságokkal rendelkezik. Amikor egy adatelem bekerül a prioritási sorba, akkor prioritási számot kap. A szabványos sorok törlésével ellentétben a magas prioritású adatelemek lecsökkennek az alacsony prioritású adatelemek előtt. A prioritás felülírja a prioritási sorba való érkezési sorrendet, ezért a prioritási soroknak nincs konzisztens FIFO jellege.

Összefüggő: Algoritmusok, amelyeket minden programozónak tudnia kell

A programozók több módon is megvalósíthatnak prioritási sort. Egyszerű megvalósítás egy struktúra/osztály adatelemmel rendelkező tömb használata, és az adatelem tartalmazza az egyes adatelemek prioritását és magát az adatot. Egy másik primitív prioritási sor megvalósítás a hivatkozott lista használata. A hivatkozott listákon keresztül megvalósított elsőbbségi sorok működőképesek, de teljesítményük miatt nem ideálisak.

Egy jobb prioritási sort valósíthat meg halommal. Ha visszaemlékszel, a bináris halmok megadják a maximális vagy minimális elemet 0 (1) idő alatt, a beillesztés pedig csak 0 (logN) időt vesz igénybe. A halmok segítségével az elsőbbségi sorok aszimptotikusan jobb teljesítményt nyújtanak a sorokhoz vagy tömbökhöz képest.

A prioritási sornak számos alapvető alkalmazása is van. A prioritási sorok kulcsfontosságúak a gráf -algoritmusokban, mint például a Prim minimális kiterjedésű fa és a Dijkstra legrövidebb út algoritmusa. Ideálisak a számítógépes feldolgozóegység (CPU) folyamatütemezési algoritmusaiban is.

Ismerje meg az adatszerkezeteket

A sorok és a prioritási sorok fontos adatstruktúrák minden kezdő számára. Döntő fontosságú, hogy a diákok kényelmesen tudják megvalósítani ezeket az adatstruktúrákat és használni őket különböző projektekben.

Más adatstruktúrák, például halmok, halmok és fák egyaránt fontosak a diákok és a szakemberek számára. Az is gyakori, hogy az interjúztatók kérdezősködnek a jelentkezőkről az adatstruktúrákról.

Miután elolvasta ezt a cikket, most jó ötlete lehet a sorok és a prioritási sorok működéséről. Ha még mindig kissé homályosnak tűnik minden, akkor ezekkel fog foglalkozni, amint több tapasztalatot szerez a használatukról.

Halom vs. Halom: mi különbözteti meg őket?

Hallott már a Heaps and Stacks -ről, de mikor érdemes egyiket a másikkal szemben használni?

Olvassa tovább

A szerzőről