Ieteicams, 2020

Redaktora Izvēle

Starpība starp steku un rindu

Stack un Queue abas ir ne-primitīvās datu struktūras. Galvenās atšķirības starp kaudzēm un rindām ir tas, ka kaudze izmanto LIFO (pēdējais pirmais ārā) metodi, lai piekļūtu un pievienotu datu elementus, savukārt rindā tiek izmantota FIFO (pirmās pirmās ārā) metode, lai piekļūtu un pievienotu datu elementus.

Stekam ir tikai viens gals, kas atvērts, lai datu elementi tiktu izvilkti, bet otrā pusē - rindā ir atvērti abu galu datu elementu enqueuing un dequeuing.

Kaudze un rinda ir datu struktūras, ko izmanto datu elementu glabāšanai un faktiski balstās uz kādu reālu pasaules ekvivalentu. Piemēram, kaudze ir kompaktdisku kaudze, kurā jūs varat izņemt un ievietot kompaktdisku CD kompaktdisku augšpusē. Līdzīgi, rinda ir teātra biļešu rinda, kurā vispirms tiks pasniegta persona, kas stāv pirmajā vietā, ti, rindas priekšā, un jaunā persona, kas ierodas, parādīsies rindas aizmugurē (rindas aizmugurē).

Salīdzinājuma diagramma

Salīdzināšanas pamatsKaudzeRinda
Darbības principsLIFO (pēdējais pirmais)FIFO (pirmais pirmais)
StruktūraTo pašu galu izmanto, lai ievietotu un dzēstu elementus.Viens gals tiek izmantots ievietošanai, ti, aizmugurējais gals un cits gals tiek izmantots elementu dzēšanai, ti, priekšpusē.
Izmantoto norādījumu skaitsViensDivi (vienkāršā rindā)
Veiktās darbībasPush un PopEnqueue un dequeue
Tukša stāvokļa pārbaudeTop == -1Priekšējais == -1 || Front == Aizmugure + 1
Pilna stāvokļa pārbaude
Top == Max - 1Aizmugure == Max - 1
VariantsTam nav variantu.Tajā ir varianti, piemēram, apļveida rinda, prioritātes rinda, divkārši noslēgta rinda.
ĪstenošanaVienkāršākaSalīdzinoši sarežģīts

Steka definīcija

Stack ir ne-primitīva lineāra datu struktūra. Tas ir pasūtīts saraksts, kurā tiek pievienots jauns vienums, un esošais elements tiek izdzēsts tikai no viena gala, ko sauc par kaudze (TOS). Tā kā visa dzēšana un ievietošana kaudzē tiek veikta no kaudzes augšdaļas, pēdējais pievienotais elements būs pirmais, kas tiks noņemts no kaudzes. Tas ir iemesls, kāpēc kaudze tiek saukta par saraksta “LIFO” veidu.

Ņemiet vērā, ka elements, kas bieži ir pieejams kaudzē, ir augšējais elements, bet pēdējais pieejamais elements atrodas kaudzes apakšā.

Piemērs

Daži no jums var ēst cepumus (vai Poppins). Ja jūs domājat, tikai viena vāka puse ir saplēsta, un cepumi tiek paņemti pa vienam. Tas ir tas, ko sauc par popping, un līdzīgi, ja vēlaties kādu laiku saglabāt dažus cepumus, jūs tos ievietosiet atpakaļ iepakojumā, izmantojot to pašu plosītos galus.

Queue definīcija

Rinda ir lineāra datu struktūra nonāk primitīvā tipa kategorijā. Tā ir līdzīga veida elementu kolekcija. Jaunu elementu pievienošana notiek vienā galā, ko sauc par aizmugures galu. Līdzīgi, esošo elementu dzēšana notiek otrā galā, ko sauc par Front-end, un tas ir loģiski saraksta pirmais pirmais ārā (FIFO) veids.

Piemērs

Mūsu ikdienas dzīvē mēs saskaramies ar daudzām situācijām, kurās mēs gaidīsim vēlamo pakalpojumu, tur ir jāgriežas gaidīšanas rindā, lai mūsu kārta tiktu apkalpota. Šo gaidīšanas rindu var uzskatīt par rindu.

Galvenās atšķirības starp skursteni un rindu

  1. Stack seko LIFO mehānisms, no otras puses Queue seko FIFO mehānismam, lai pievienotu un noņemtu elementus.
  2. Stekā to pašu galu izmanto, lai ievietotu un dzēstu elementus. Gluži pretēji, rindā tiek izmantoti divi dažādi mērķi elementu ievietošanai un dzēšanai.
  3. Tā kā kaudzei ir tikai viens atvērts gals, tas ir iemesls, kāpēc tikai viens rādītājs tiek izmantots, lai aplūkotu kaudzes augšdaļu. Bet rindā tiek izmantotas divas norādes, lai norādītu rindas priekšpusi un aizmuguri.
  4. Stack veic divas operācijas, kas pazīstamas kā push un pop, bet rindā tā ir pazīstama kā enqueue un dequeue.
  5. Steka ieviešana ir vieglāka, bet rindas ieviešana ir sarežģīta.
  6. Rindā ir varianti, piemēram, apļveida rinda, prioritātes rinda, divkārši pabeigta rinda utt. Turpretī kaudze nav variantu.

Steka ieviešana

Steku var izmantot divos veidos:

  1. Statiskā īstenošana izmanto blokus, lai izveidotu kaudzi. Statiskā īstenošana ir viegla tehnika, bet tā nav elastīga radīšanas metode, jo kaudzes lieluma deklarācija ir jāveic programmas izstrādes laikā, pēc tam izmēru nevar mainīt. Turklāt statiskā īstenošana nav ļoti efektīva attiecībā uz atmiņas izmantošanu. Tā kā masīvs (steku ieviešanai) ir deklarēts pirms operācijas sākuma (programmas izstrādes laikā). Tagad, ja šķirojamo elementu skaits kaudzē ir mazāks, statiskā iedalītā atmiņa tiks izšķiesta. No otras puses, ja ir vairāk elementu, kas jāglabā kaudzē, tad mēs nevaram mainīt masīva lielumu, lai palielinātu tā ietilpību, lai tā varētu uzņemt jaunus elementus.
  2. Dinamiska ieviešana tiek saukta arī par saistīto sarakstu attēlojumu un izmanto norādes, lai īstenotu datu struktūras steku veidu.

Rindu ieviešana

Rindu var īstenot divos veidos:

  1. Statiskā īstenošana : Ja rinda tiek īstenota, izmantojot masīvus, precīzs elementu skaits, ko vēlamies saglabāt rindā, ir jāpārliecinās, jo masīva lielums ir jādeklarē projektēšanas laikā vai pirms apstrādes sākuma. Šajā gadījumā masīva sākums kļūs par rindas priekšpusi, un rindas pēdējā vieta darbosies kā rindas aizmugure. Turpmāk norādītā attiecība dod rindā visus elementus, ja tos izmanto, izmantojot blokus:
    priekšā - aizmugurē + 1
    Ja “aizmugurē <priekšā”, tad rindā nebūs elementa vai rinda vienmēr būs tukša.
  2. Dinamiska īstenošana : rindu īstenošana, izmantojot norādes, galvenais trūkums ir tas, ka mezgls saistītajā attēlojumā patērē vairāk atmiņas vietas nekā atbilstošs elements masīva attēlojumā. Tā kā katrā mezglā ir vismaz divi lauki datu laukam un citi, lai saglabātu nākamā mezgla adresi, bet saistītajā attēlojumā ir tikai datu lauks. Saistītās attēlojuma izmantošanas priekšrocības kļūst acīmredzamas, ja ir nepieciešams ievietot vai dzēst elementu citu elementu grupas vidū.

Operācijas uz Stack

Pamatdarbības, kas var tikt izmantotas kaudze, ir šādas:

  1. PUSH : kad jaunā elementa pievienošana skursteņa augšdaļai ir pazīstama kā PUSH darbība. Nospiežot elementu stekā, tiek pievienots elements, jo jaunais elements tiks ievietots augšpusē. Pēc katras stumšanas operācijas augšējā daļa tiek palielināta par vienu. Ja masīvs ir pilns, un nav iespējams pievienot jaunu elementu, to sauc par STACK-FULL vai STACK OVERFLOW. PUSH OPERATION - funkcija C:
    Ņemot vērā kaudze tiek deklarēta kā
    int stack [5], top = -1;
    void push()
    {
    int item;
    if (top < 4)
    {
    printf ("Enter the number") ;
    scan ("%d", & item) ;
    top = top + 1;
    stack [top] = item;
    }
    else
    {
    printf (" Stack is full");
    }
    }
  2. POP : kad elements tiek izdzēsts no skursteņa augšdaļas, tas tiek saukts par POP darbību. Pēc katras pop operācijas kaudze tiek samazināta par vienu. Ja kaudzē nav atlikušo elementu un tiek veikta pop, tad tas radīs STACK UNDERFLOW stāvokli, kas nozīmē, ka jūsu kaudze ir tukša. POP OPERATION - funkcijas C:
    Ņemot vērā kaudze tiek deklarēta kā
    int stack [5], top = -1;
    void pop()
    {
    int item;
    if (top >= 4)
    {
    item = stack [top];
    top = top - 1;
    printf ("Number deleted is = %d", item) ;
    }
    else
    {
    printf (" Stack is empty");
    }
    }

Darbības rindā

Pamatdarbības, kuras var veikt rindā, ir šādas:

  1. Enqueue : lai ievietotu elementu rindā.Controlēšanas funkcija C:
    Rinda tiek deklarēta kā
    int queue [5], Front = -1 and rear = -1;
    void add ()
    {
    int item;
    if ( rear < 4)
    {
    printf ("Enter the number") ;
    scan ("%d", & item) ;
    if (front == -1)
    {
    front =0 ;
    rear =0 ;
    }
    else
    {
    rear = rear + 1;
    }
    queue [rear] = item ;
    }
    else
    {
    printf ("Queue is full") ;
    }
    }
  2. Dequeue : lai izdzēstu elementu no rindas.
    Rinda tiek deklarēta kā
    int queue [5], Front = -1 and rear = -1;
    void delete ()
    {
    int item;
    if ( front ! = -1)
    {
    item = queue [ front ] ;
    if (front == rear)
    {
    front =-1 ;
    rear =-1 ;
    }
    else
    {
    front = front + 1;
    printf ("Number deleted is = %d", item) ;
    }
    }
    else
    {
    printf ("Queue is empty") ;
    }
    }

Stack lietojumi

  • Parsēšana kompilatorā.
  • Java virtuālā mašīna.
  • Atsaukt vārdu procesoru.
  • Atpakaļ poga tīmekļa pārlūkprogrammā.
  • Printeru PostScript valoda.
  • Funkciju zvanu ieviešana kompilatorā.

Rindas pieteikumi

  • Datu buferi
  • Asinhronā datu pārsūtīšana (fails IO, caurules, ligzdas).
  • Pieprasījumu piešķiršana kopīgajam resursam (printeris, procesors).
  • Satiksmes analīze.
  • Nosakiet lielveikalu kasieru skaitu.

Secinājums

Kaudze un rinda ir lineāras datu struktūras, kas atšķiras dažos veidos, piemēram, darba mehānisms, struktūra, īstenošana, varianti, bet abi tiek izmantoti saraksta elementu glabāšanai un operāciju veikšanai sarakstā, piemēram, elementu pievienošana un dzēšana. Lai gan ir daži vienkāršā rindas ierobežojumi, kas tiek atgūti, izmantojot cita veida rindas.

Top