Pinotietorakenne. Tietorakenteet: yleinen käsite, toteutus. Yksinkertaisimmat tietorakenteet: jono, pino. Pinon ja käänteisen puolan merkintätavan käyttäminen

Tunnisteet: Pino, pino C:ssä, pinon toteutus, pino taulukossa, dynaamisesti kasvava pino, pino yksittäiseen järjestelmään

Pino

S tek on luultavasti eniten yksinkertainen rakenne tietoja, joita tutkimme ja joita käytämme jatkuvasti. Pino on tietorakenne, jossa elementit tukevat LIFO-periaatetta ("Last in – first out"): viimeinen sisään, ensin ulos. Tai ensin sisään, viimeisenä ulos.

Pinon avulla voit tallentaa elementtejä, ja se tukee yleensä kahta perustoimintoa:

• TYÖNTÄÄ– asettaa elementin pinon päälle
• POP– poistaa elementin pinon yläosasta ja siirtää yläosan seuraavaan elementtiin

Yleinen on myös PEEK-operaatio, joka saa elementin pinon yläosaan, mutta ei poista sitä sieltä.

Pino on yksi perusrakenteet dataa ja sitä käytetään paitsi ohjelmoinnissa myös piirisuunnittelussa ja yksinkertaisesti tuotannossa toteutusta varten teknisiä prosesseja jne.; Pinoa käytetään aputietorakenteena monissa algoritmeissa ja muissa monimutkaisemmissa rakenteissa.

Olkoon meillä esimerkiksi pino numeroita. Suoritetaan muutama komento. Aluksi pino on tyhjä. Pinon yläosa on osoitin ensimmäiseen elementtiin, se ei osoita mihinkään. C:n tapauksessa se voi olla yhtä suuri kuin NULL.

Pino koostuu nyt yhdestä elementistä, numerosta 3. Pinon yläosa osoittaa numeroon 3.

Pino koostuu kahdesta elementistä, 5 ja 3, ja pinon yläosa osoittaa 5:tä.

Pino koostuu kolmesta elementistä, pinon yläosa osoittaa kohtaan 7.

Palauttaa arvon 7, jolloin pinoon jää arvot 5 ja 3. Yläosa osoittaa seuraava elementti – 5.

Palauttaa 5, jättäen pinoon vain yhden elementin, 3, johon pinon yläosa osoittaa.

Palauttaa 3, pino on tyhjä.

Pinoa verrataan usein lautaspinoon. Jotta saat seuraavan levyn, sinun on poistettava edelliset. Pinon yläosa on lautaspinon yläosa.

Kun työskentelemme pinon kanssa, kaksi pääasiallista ja yleistä virhettä on mahdollista:

• 1. Pinon alivuoto: Yritetään ponnahtaa elementti tyhjästä pinosta
• 2. Pinon ylivuoto: Yritetään laittaa uusi elementti pinoon, joka ei voi enää kasvaa (esimerkiksi ei ole tarpeeksi RAM-muisti)

Ohjelmiston toteutus

Katsotaanpa kolmea yksinkertaiset toteutukset pino:

Kiinteän kokoinen pino, joka on rakennettu taulukkoon

Erottuva piirre on toteutuksen helppous ja suurin nopeus teloitus. Tällaista pinoa voidaan käyttää, kun sen maksimikoko tiedetään etukäteen tai sen tiedetään olevan pieni.

Ensin määritämme taulukon enimmäiskoon ja siihen tallennettavien tietojen tyypin:

#define STACK_MAX_SIZE 20 typedef int T;

Nyt itse rakenne

Typedef struct Stack_tag ( T data; size_t size; ) Pino_t;

Tässä muuttujakoko on elementtien lukumäärä ja samalla osoitin pinon yläosaan. Yläosa osoittaa taulukon seuraavaan elementtiin, joka sisältää arvon.

Laitamme pinoon uuden elementin.

Void push(pino_t *pino, vakio T-arvo) (pino->data = arvo; pino->koko++; )

Ainoa ongelma on, että voit mennä taulukon ulkopuolelle. Siksi sinun tulee aina tarkistaa, ettei pinon ylivuotovirheitä ole:

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push(Pino_t *pino, vakio T-arvo) (if (pino->koko >= STACK_MAX_SIZE) ( exit(STACK_OVERFLOW); ) pino->data = arvo; pino- >koko++ ;

Samoin määritellään Pop-operaatio, joka palauttaa elementin ylhäältä ja siirtyy seuraavaan

T pop(Pino_t *pino) ( if (pino->koko == 0) ( exit(STACK_UNDERFLOW); ) pino->koko--; paluu pino->data; )

JA kurkistustoiminto, palauttaa nykyisen elementin ylhäältä

T peek(const Pino_t *pino) ( if (pino->koko<= 0) { exit(STACK_UNDERFLOW); } return stack->tiedot; )

Toinen tärkeä muistiinpano- Meillä ei ole pinon luontitoimintoa, joten meidän on nollattava koon arvo manuaalisesti

Aputoiminnot pinoelementtien tulostamiseen

Void printStackValue(const T value) ( ​​printf("%d", value); ) void printStack(const Stack_t *pino, void (*printStackValue)(const T)) ( int i; int len ​​= pino- >koko - 1 ; printf("pino %d > ", pino->koko);< len; i++) { printStackValue(stack->data[i]); printf(" | "); ) if (pino->koko != 0) ( printStackValue(pino->data[i]); ) printf("\n"); )

Huomaa, että tulostusfunktiossa käytämme int sijaan size_t, koska len voi muuttua negatiiviseksi. Funktio tulostaa ensin pinon koon ja sitten sen sisällön erottaen elementit |-merkillä

Tutkimus

Stack_t pino; pino.koko = 0; push(&pino, 3); printStack(&pino, printStackValue); push(&pino, 5); printStack(&pino, printStackValue); push(&pino, 7); printStack(&pino, printStackValue); printf("%d\n", pop(&pino)); printStack(&pino, printStackValue); printf("%d\n", pop(&pino)); printStack(&pino, printStackValue); printf("%d\n", pop(&pino)); printStack(&pino, printStackValue); _getch();

Tarkastellaan myös tilanteita, joissa on käyttövirheitä. Alivirtaus

Void main() ( Pino_t pino; pino.koko = 0; push(&pino, 3); pop(&pino); pop(&pino); _getch(); )

Void main() ( Pino_t pino; koko_t i; pino.koko = 0; for (i = 0; i< 100; i++) { push(&stack, i); } _getch(); }

Dynaamisesti kasvava pino taulukossa

Dynaamisesti kasvavaa pinoa käytetään, kun elementtien lukumäärä voi olla merkittävä eikä sitä tiedetä ongelman ratkaisuhetkellä. Pinon enimmäiskokoa voi rajoittaa jokin määrä tai RAM-muistin koko.

Pino koostuu osoittimesta dataan, taulukon koosta (maksimi) ja taulukon elementtien lukumäärästä. Tämä numero ilmaisee myös yläosan.

Typedef struct Stack_tag ( T *tiedot; koko_t koko; koko_t yläosa; ) Pino_t;

Ensin tarvitset jonkin alkuperäisen taulukon koon, olkoon se 10

#define INIT_SIZE 10

Algoritmi toimii näin: tarkistamme, onko topin arvo ylittänyt koon arvon. Jos arvo ylittyy, lisäämme taulukon kokoa. Tässä on useita vaihtoehtoja taulukon kasvattamiseksi. Voit lisätä numeron, voit kertoa jollain arvolla. Kumpi vaihtoehto on parempi, riippuu tehtävän erityispiirteistä. Meidän tapauksessamme kerromme koon numerolla MULTIPLIER

#define KERTOJA 2

Emme aseta enimmäiskokoa. Ohjelma kaatuu, jos pinon ylivuoto tai pinon alivuoto. Toteutamme saman käyttöliittymän (pop, push, peek). Lisäksi, koska taulukko on dynaaminen, teemme joitain aputoimintoja pinon luomiseksi, poistamiseksi ja puhdistamiseksi.

Ensinnäkin toiminnot pinon luomiseen ja poistamiseen sekä muutama virhe

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Pino_t* createStack() ( Pino_t *out = NULL; out = malloc(sizeof(Stack_t)); if (out == NULL) ( exitMORY_OUT); ) out->size = INIT_SIZE out->data = malloc(out->size * sizeof(T)); >top = 0; palauttaa pois;

Kaikki on erittäin yksinkertaista ja selkeää, ei ole temppuja. Luomme pinon alkupituudella ja nollaamme arvot.

Nyt kirjoitetaan aputoiminto koko muuttuu.

Void resize(pino_t *pino) ( pino->koko *= KERTOJA; pino->data = realloc(pino->data, pino->koko * koko(T)); if (pino->data == NULL) ( exit(STACK_OVERFLOW);

Huomaa, että jos ei ollut mahdollista varata tarpeeksi muistia, se poistuu STACK_OVERFLOW:lla.

Push-funktio tarkistaa, olemmeko ylittäneet taulukon rajat. Jos kyllä, niin suurenna sen kokoa

Void push(pino_t *pino, T-arvo) (if (pino->ylä>= pino->koko) (muuta kokoa(pino); ) pino->data = arvo; pino->ylä++; )

Pop- ja peek-toiminnot ovat samankaltaisia ​​kuin kiinteän kokoisen taulukon toiminnot

T pop(Pino_t *pino) ( if (pino->top == 0) ( exit(STACK_UNDERFLOW); ) pino->top--; paluu pino->data; ) T peek(const Stack_t *pino) ( if ( pino-> alkuun<= 0) { exit(STACK_UNDERFLOW); } return stack->tiedot; )

Tarkistetaan

Void main() ( int i; Pino_t *s = createStack(); for (i = 0; i< 300; i++) { push(s, i); } for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); } deleteStack(&s); _getch(); }

Kirjoitetaan toinen funktio, implode, joka pienentää taulukon kokoon, joka on yhtä suuri kuin taulukon elementtien lukumäärä. Sitä voidaan käyttää, kun on jo tiedossa, että mitään elementtejä ei lisätä ja muistia voidaan vapauttaa osittain.

Void implode(pino_t *pino) ( pino->koko = pino->yläosa; pino->data = realloc(pino->data, pino->koko * koko(T)); )

Voimme käyttää meidän tapauksessamme

Sille (i = 0; i< 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }

Tämä pinon yksisäikeinen toteutus käyttää vähän muistia, on melko yksinkertainen ja yleiskäyttöinen, toimii nopeasti ja voidaan tarvittaessa toteuttaa muutamassa minuutissa. Sitä käytetään aina tästä eteenpäin, ellei toisin mainita.

Sillä on epäkohta, joka liittyy menetelmään lisätä muistin kulutusta. Kun kerrotaan kertoimella 2 (tapauksessamme), tarvitaan vähän muistin käyttöä, mutta jokainen myöhempi lisäys voi johtaa virheeseen, varsinkin jos järjestelmän muisti on pieni. Jos käytät lempeämpää menetelmää muistin varaamiseen (esimerkiksi lisäämällä 10 joka kerta), käyttöjen määrä kasvaa ja nopeus laskee. Nykyään muistin koon kanssa ei yleensä ole ongelmia, ja muistinhallintalaitteet ja roskankerääjät (jotka eivät ole C:ssä) toimivat nopeasti, joten aggressiivinen muutos vallitsee (esim. tavallinen kirjasto Java-kieli).

Pinon käyttöönotto yksittäin linkitetyssä luettelossa

Mikä on yksittäin linkitetty luettelo? Lyhyesti: yksitellen linkitetty lista koostuu solmuista, joista jokainen sisältää hyödyllistä tietoa ja linkin seuraavaan solmuun. Viimeinen solmu viittaa NULL.

Ei maksimi- ja minimikoot meillä ei ole (vaikka sisään yleinen tapaus Voi olla). Jokainen uusi elementti luodaan uudelleen. Ensin määritellään solmun rakenne

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Solmun_tunniste ( T arvo; struct Solmutunniste *seuraava; ) Solmu_t;

Ensimmäisen elementin lisääminen on yksinkertainen: luo uusi solmu. Heitämme seuraavan osoittimen vanhaan solmuun. Seuraavaksi siirrämme osoittimen pinon yläosaan äskettäin luotuun solmuun. Pinon yläosa osoittaa nyt uuteen solmuun.

Void push(Solmu_t **head, T-arvo) (Solmu_t *tmp = malloc(sizeof(Solmu_t)); if (tmp == NULL) ( exit(STACK_OVERFLOW); ) tmp->seuraava = *head; tmp- >arvo = arvo *pää = tmp;

Pop-funktio ottaa ensimmäisen elementin (sen, johon kärkipiste osoittaa), heittää osoittimen seuraavaan elementtiin ja palauttaa ensimmäisen. Tässä on kaksi vaihtoehtoa - voit palauttaa solmun tai arvon. Jos palautamme arvon, meidän on poistettava solmu funktion sisällä

Solmu_t* pop1(Solmu_t **head) ( Solmu_t *out; if ((*head) == NULL) ( exit(STACK_UNDERFLOW); ) out = *head; *head = (*head)->seuraava; paluu ulos; )

T pop2(Solmu_t **head) ( Node_t *out; T-arvo; if (*head == NULL) ( exit(STACK_UNDERFLOW); ) out = *head; *head = (*head)->seuraava; arvo = ulos ->arvo vapaa(out);

Nyt taulukon pituuden tarkistamisen sijaan pinon yläosan ja NULL-arvon tarkistusta käytetään kaikkialla.

Yksinkertainen kurkistustoiminto

T peek(const Node_t* head) ( if (head == NULL) ( exit(STACK_UNDERFLOW); ) palauttaa head->value; )

Iteraatio on aika mielenkiintoista. Siirrymme vain solmusta toiseen, kunnes saavutamme lopun

Void printStack(const Node_t* head) ( printf("pino >"); while (head) ( printf("%d ", head->value); head = head->seuraava; ) )

Ja vielä yksi ongelma - nyt et voi vain katsoa pinon kokoa. Sinun on mentävä alusta loppuun ja laskettava kaikki elementit. Esimerkiksi näin

Size_t getSize(const Node_t *head) ( koko_t koko = 0; while (pää) (koko++; pää = pää->seuraava; ) palautuskoko; )

Tietysti voit tallentaa koon erikseen, voit kääriä pinon kaikkine tiedoineen toiseen rakenteeseen jne. Tarkastellaan tätä kaikkea, kun tutkimme luetteloita yksityiskohtaisemmin.

Pino on kokoelma, jonka elementit hankitaan viimeinen sisään, ensimmäinen ulos -periaatteella. (Last-In-First-Out tai LIFO). Tämä tarkoittaa, että meillä on pääsy vain viimeksi lisättyyn elementtiin.

Toisin kuin luettelot, emme voi käyttää pinon mielivaltaista elementtiä. Voimme lisätä tai poistaa elementtejä vain erikoismenetelmin. Pinoilla ei myöskään ole Contains-metodia, kuten listoilla. Pinossa ei myöskään ole iteraattoria. Ymmärtääksemme, miksi tällaiset rajoitukset asetetaan pinolle, katsotaan kuinka se toimii ja miten sitä käytetään.

Yleisin analogia pinon selittämiseen on lautasten pino. Riippumatta siitä, kuinka monta lautasta pinossa on, voimme aina poistaa ylimmän. Puhtaat lautaset asetetaan pinon päälle samalla tavalla ja otamme aina viimeisenä ensimmäisenä asetetun lautasen.

Jos laitamme esimerkiksi punaisen levyn, sitten sinisen ja sitten vihreän, meidän on ensin poistettava vihreä, sitten sininen ja lopuksi punainen. Tärkeintä on muistaa, että lautaset asetetaan aina pinon päälle. Kun joku ottaa lautasen, hän ottaa sen myös pois päältä. Osoittautuu, että levyt puretaan päinvastaisessa järjestyksessä kuin se, johon ne asetettiin.

Nyt kun ymmärrämme, kuinka pino toimii, esitellään muutama termi. Elementin lisäämistä pinoon kutsutaan "pushiksi" ja sen poistamista "pop". Viimeksi lisättyä elementtiä kutsutaan pinon yläosaksi tai "topiksi", ja sitä voidaan tarkastella "peek"-toiminnolla. Tarkastellaan nyt pinon toteuttavan luokan mallia.

Pinoluokka

Pino-luokka määrittää Push-, Pop-, Peek-menetelmät elementtien käyttöä varten ja Count-kentän. Toteutuksessa käytämme LinkedListiä elementtien säilyttämiseen.

Julkinen luokkapino ( LinkedList _items = new LinkedList(); public void Push(T-arvo) ( heittää uusi NotImplementedException(); ) public T Pop() ( heittää uusi NotImplementedException(); ) julkinen T Peek() ( heittää uusi NotImplementedException( ) public int Count ( get; ) )

Push menetelmä

• Käyttäytyminen: Lisää elementin pinon yläosaan.
• Monimutkaisuus: O(1).

Koska käytämme linkitettyä luetteloa elementtien tallentamiseen, voimme yksinkertaisesti lisätä uuden luettelon loppuun.

Public void Push(T-arvo) (_items.AddLast(arvo); )

Pop menetelmä

• Käyttäytyminen: Poistaa elementin pinon yläosasta ja palauttaa sen. Jos pino on tyhjä, antaa InvalidOperationException.
• Monimutkaisuus: O(1).

Push lisää elementtejä luettelon loppuun, joten se ottaa ne myös lopusta. Jos lista on tyhjä, tehdään poikkeus.

Public T Pop() ( if (_items.Count == 0) ( heittää uusi InvalidOperationException("Pino on tyhjä"); ) T result = _items.Tail.Value; _items.RemoveLast(); palauttaa tuloksen; )

Kurkistusmenetelmä

• Käyttäytyminen: Palauttaa pinon ylimmän elementin, mutta ei poista sitä. Jos pino on tyhjä, antaa InvalidOperationException.
• Monimutkaisuus: O(1).

public T Peek() ( if (_items.Count == 0) ( heittää uusi InvalidOperationException("Pino on tyhjä"); ) return _items.Tail.Value; )

Laskumenetelmä

• Käyttäytyminen: Palauttaa pinon elementtien määrän.
• Monimutkaisuus: O(1).

Miksi meidän täytyy tietää kuinka monta elementtiä pinossa on, jos meillä ei ole pääsyä niihin joka tapauksessa? Tällä kentällä voimme tarkistaa, onko pinossa elementtejä vai onko se tyhjä. Tämä on erittäin hyödyllistä ottaen huomioon Pop menetelmä tekee poikkeuksen.

Esimerkki: laskin käänteisellä puolalaisella merkinnällä.

Klassinen esimerkki pinon käytöstä on käänteinen puola- tai postfix-merkintälaskin. Siihen on kirjoitettu operaattori jälkeen heidän operandinsa. Eli kirjoitamme:

<операнд> <операнд> <оператор>

perinteisen sijaan:

<операнд> <оператор> <операнд>

Toisin sanoen "4 + 2" sijaan kirjoitamme "4 2 +". Jos olet kiinnostunut käänteisen puolalaisen merkinnän alkuperästä ja sen nimestä, voit selvittää sen Wikipediasta tai hakukoneesta.

Kuinka käänteinen lasketaan Puolan sisääntulo ja miksi pino on niin hyödyllinen sitä käytettäessä, voidaan selvästi nähdä seuraavasta algoritmista:

Jokaiselle syötetylle arvolle, jos arvo on kokonaisluku, työnnä arvo operandipinoon muuten jos arvo on operaattori pop vasen ja oikeat arvot pinosta arvioivat, että operaattori siirtää tuloksen pinon ponnahdusvastaukseen pinosta.

Eli ilmaisun "4 2 +" toiminnot ovat seuraavat:

Push(4) push(2) push(pop() + pop())

Lopussa pinossa on yksi arvo - 6.

Seuraava on täydellinen koodi yksinkertainen laskin, joka lukee lausekkeen (esimerkiksi 4 2 +) konsolista, jakaa syötteen välilyönneillä (["4", "2", "+"]) ja suorittaa laskenta-algoritmin. Arviointi jatkuu, kunnes sana quit löytyy.

Void RpnLoop() ( while (true) (Console.Write("> "); merkkijono input = Console.ReadLine(); if (input.Trim().ToLower() == "quit") ( break; ) / / Pino arvoja ei vielä käsitelty. Pino arvot = new Stack(); int arvo if (int. TryParse(token, out value)) ( // ... laita se pinoon. arvot.Push(arvo); ) else ( // muuten suorita toiminto... int rhs = arvot .Pop(); int lhs = arvot.Pop(); : arvot.Push(lhs: break;) Jos toiminto ei ole +, -, * tai / heittää uusi ArgumentException(string.Format("Tunnistamaton merkki: (0)", token) ) // Viimeinen elementti pino sisältää tuloksen. Console.WriteLine(arvot.Pop()); ) )

Jonottaa

Jonot ovat hyvin samanlaisia ​​kuin pinot. Ne eivät myöskään anna pääsyä mielivaltaiseen elementtiin, mutta toisin kuin pino, elementit pinotaan (jono) ja kiivetä (jonosta) eri päistä. Tätä menetelmää kutsutaan "ensin sisään, ensin ulos" (First-In-First-Out tai FIFO). Eli otamme elementit jonosta samassa järjestyksessä kuin laitamme ne. Kuten oikea jono tai kuljetin.

Jonoja käytetään usein ohjelmissa puskuriksi, johon tuotteet voidaan sijoittaa myöhempää käsittelyä varten säilyttäen samalla niiden saapumisjärjestyksen. Esimerkiksi, jos tietokanta tukee vain yhtä yhteyttä, voit käyttää säikeiden jonoa, jotka kummallista kyllä ​​odottavat vuoroaan päästäkseen tietokantaan.

Jonoluokka

Jono-luokka, kuten pino, toteutetaan linkitetyn luettelon avulla. Se tarjoaa Enqueue-toiminnon elementin lisäämiseksi, jonon poistamisen sekä Peek- ja Count-menetelmien. Kuten Stack-luokka, se ei toteuta ICollection-liitäntää , koska nämä ovat erikoiskokoelmia.

Julkinen luokkajono ( LinkedList _items = new LinkedList(); public void Enqueue(T-arvo) ( heittä uusi NotImplementedException(); ) public T Dequeue() (heittä uusi NotImplementedException(); ) julkinen T Peek() (heittä uusi NotImplementedException( ) public int Count ( get; ) )

Jonotusmenetelmä

• Käyttäytyminen: Lisää elementin jonoon.
• Monimutkaisuus: O(1).

Uusia jonoelementtejä voidaan lisätä joko listan alkuun tai loppuun. On vain tärkeää, että elementit saavutetaan vastakkaisesta reunasta. Tässä toteutuksessa lisäämme uusia elementtejä sisäisen listan alkuun.

Julkinen void Enqueue(T-arvo) (_items.AddFirst(value); )

Poista jonosta menetelmä

• Käyttäytyminen: Poistaa ensimmäisenä sijoitetun elementin jonosta ja palauttaa sen. Jos jono on tyhjä, antaa InvalidOperationException.
• Monimutkaisuus: O(1).

Koska lisäämme elementtejä luettelon alkuun, poistamme ne lopusta. Jos luettelo on tyhjä, tehdään poikkeus.

Julkinen T Dequeue() ( if (_items.Count == 0) ( heittää uusi InvalidOperationException("Jono on tyhjä"); ) T last = _items.Tail.Value; _items.RemoveLast(); return last; )

Kurkistusmenetelmä

• Käyttäytyminen: Palauttaa elementin, jonka seuraava kutsu palauttaa Dequeue-metodille. Jono pysyy ennallaan. Jos jono on tyhjä, antaa InvalidOperationException.
• Monimutkaisuus: O(1).

public T Peek() ( if (_items.Count == 0) ( heittää uusi InvalidOperationException("Jono on tyhjä"); ) return _items.Tail.Value; )

Laskumenetelmä

• Käyttäytyminen:
• Monimutkaisuus: O(1).

public int Count ( get ( return _items.Count; ) )

Kaksisuuntainen jono

Kaksisuuntainen jono (kaksipäinen jono) tai joulukuu (Deque), pidentää jonon toimintaa. Dequessa voit lisätä tai poistaa elementtejä sekä jonon alusta että lopusta. Tämä toiminta on hyödyllistä monissa tehtävissä, kuten säikeiden ajoituksessa tai muiden tietorakenteiden toteuttamisessa. Myöhemmin tarkastellaan pinon toteuttamista dequen avulla.

Deque luokka

Deque-luokka on helpoin toteuttaa käyttämällä kaksoislinkitettyä listaa. Sen avulla voit tarkastella, poistaa ja lisätä elementtejä luettelon alkuun ja loppuun. Suurin ero kaksisuuntaisen jonon ja tavallisen jonon välillä on se, että Enqueue-, Dequeue- ja Peek-menetelmät on jaettu pareiksi toimiakseen luettelon molemmissa päissä.

Julkinen luokka Deque ( LinkedList _items = new LinkedList(); public void EnqueueFirst(T-arvo) (heittä uusi NotImplementedException(); ) public void EnqueueLast(T-arvo) (heittä uusi NotImplementedException(); ) public T DequeueFirst( ) ( heittää uusi NotImplementedException(); ) public T DequeueLast() ( heittää uusi NotImplementedException(); ) public T PeekFirst() ( heittää uusi NotImplementedException(); ) public T PeekLast() ( heittää uusi NotImplementedException(); ) public int Laske (saa; ) )

EnqueueFirst-menetelmä

• Käyttäytyminen:
• Monimutkaisuus: O(1).

public void EnqueueFirst(T-arvo) (_items.AddFirst(value); )

EnqueueLast -menetelmä

• Käyttäytyminen:
• Monimutkaisuus: O(1).

public void EnqueueLast(T-arvo) (_items.AddLast(arvo); )

DequeueFirst-menetelmä

• Käyttäytyminen: Poistaa elementin jonon etuosasta ja palauttaa sen. Jos jono on tyhjä, antaa InvalidOperationException.
• Monimutkaisuus: O(1).

public T DequeueFirst() ( if (_items.Count == 0) ( heittää uusi InvalidOperationException("DequeueFirst kutsutaan kun deque on tyhjä"); ) T temp = _items.Head.Value; _items.RemoveFirst(); return temp; )

DequeueLast -menetelmä

• Käyttäytyminen:
• Monimutkaisuus: O(1).

public T DequeueLast() ( if (_items.Count == 0) ( heittää uusi InvalidOperationException("DequeueLast kutsutaan, kun deque on tyhjä"); ) T temp = _items.Tail.Value; _items.RemoveLast(); paluulämpötila; )

PeekFirst menetelmä

• Käyttäytyminen: Palauttaa elementin jonon alusta muuttamatta sitä. Jos jono on tyhjä, antaa InvalidOperationException.
• Monimutkaisuus: O(1).

public T PeekFirst() ( if (_items.Count == 0) ( heittää uusi InvalidOperationException("PeekFirst kutsutaan, kun deque on tyhjä"); ) return _items.Head.Value; )

PeekLast menetelmä

• Käyttäytyminen:
• Monimutkaisuus: O(1).

public T PeekLast() ( if (_items.Count == 0) ( heittää uusi InvalidOperationException("PeekLast kutsutaan, kun deque on tyhjä"); ) return _items.Tail.Value; )

Laskumenetelmä

• Käyttäytyminen: Palauttaa jonon elementtien määrän tai 0:n, jos jono on tyhjä.
• Monimutkaisuus: O(1).

public int Count ( get ( return _items.Count; ) )

Esimerkki: Pino-toteutus

Dequeä käytetään usein muiden tietorakenteiden toteuttamiseen. Katsotaanpa esimerkkiä pinon toteuttamisesta sen avulla.

Saatat ihmetellä, miksi ottaa käyttöön pino, joka perustuu jonoon linkitetyn luettelon sijaan. Syitä on kaksi: suorituskyky ja koodin uudelleenkäyttö. Linkitetyn luettelon päämäärä on solmujen luominen, eikä datan sijainnista ole takeita: elementit voivat sijaita missä tahansa muistissa, mikä aiheuttaa suuri määrä puutteet ja suorituskyvyn heikkeneminen prosessoritasolla. Dequen tehokkaampi toteutus vaatii taulukon elementtien tallentamiseen.

Pinon tai jonon toteuttaminen taulukon avulla on kuitenkin ei ole helppo tehtävä, mutta dequen toteuttaminen tällä tavalla ja sen käyttäminen muiden tietorakenteiden perustana antaa meille vakavia suorituskykyetuja ja antaa meille mahdollisuuden käyttää koodia uudelleen. Tämä vähentää tukikustannuksia.

Tarkastelemme jonon muunnelmaa taulukon avulla myöhemmin, mutta katsotaan ensin pinoluokkaa jonon poistamisen avulla:

Julkinen luokkapino ( Deque _items = new Deque(); public void Push(T value) ( ​​_items.EnqueueFirst(value); ) public T Pop() ( return _items.DequeueFirst(); ) public T Peek() ( return _items .PeekFirst( public int Count ( get ( return _items.Count; ) ) )

Huomaa, että Deque-luokka hoitaa nyt kaiken virheenkäsittelyn ja lisäksi mahdollinen jonon optimointi näkyy myös pinossa. Tavallisen edestakaisen jonon toteuttaminen on niin yksinkertaista, että jätämme sen lukijan harjoitukseksi.

Elementtien tallentaminen taulukkoon

Kuten jo mainittiin, jonon toteuttamisella taulukon avulla on etunsa. Se näyttää yksinkertaiselta, mutta itse asiassa on useita vivahteita, jotka on otettava huomioon.

Katsotaanpa mahdollisia ongelmia ja kuinka ne ratkaistaan. Lisäksi tarvitsemme tietoja sisäisen taulukon kasvattamisesta edellisestä dynaamisia taulukoita käsittelevästä artikkelista.

Kun jono luodaan, sen sisään luodaan nollapituinen taulukko. Punaiset kirjaimet "h" ja "t" tarkoittavat vastaavasti _head- ja _tail-osoittimia.

Deque deq = new Deque(); deq.EnqueueFirst(1);

Deq.EnqueueLast(2);

Deq.EnqueueFirst(0);

Huomaa: jonon ”pään” indeksi on hypännyt listan alkuun. Nyt ensimmäinen elementti, joka palautetaan kutsuttaessa DequeueFirst-metodia, on 0 (indeksi 3).

Deq.EnqueueLast(3);

Taulukko on täynnä, joten elementtiä lisättäessä tapahtuu seuraavaa:

• Kasvualgoritmi määrittää uuden taulukon koon.
• Elementit kopioidaan uusi joukko päästä häntään.
• Uusi elementti lisätään.

deq.EnqueueLast(4);

Katsotaan nyt, mitä tapahtuu, kun elementti poistetaan:

Deq.DequeueFirst();

Deq.DequeueLast();

Keskeinen kohta: riippumatta sisäisen taulukon kapasiteetista tai täyteydestä, loogisesti jonon sisältö on elementtejä "päästä" "häntään" ottaen huomioon "pyöreys". Tätä toimintaa kutsutaan myös "rengaspuskuriksi".

Katsotaan nyt toteutusta.

Deque luokka (joukkoa käyttämällä)

Taulukkopohjaisen jonon käyttöliittymä on sama kuin linkitetyn listan toteutuksen tapauksessa. Emme toista sitä. Koska luettelo kuitenkin korvattiin taulukolla, lisäsimme uusia kenttiä - itse taulukon, sen koon ja osoittimet jonon "häntään" ja "päähän".

Julkinen luokka Deque ( T _items = uusi T; // Elementtien lukumäärä jonossa. int _size = 0; // Ensimmäisen (vanhimman) elementin indeksi. int _head = 0; // Viimeisen (uusimman) elementin indeksi int _tail = -1 ... )

Kasvualgoritmi

Kun vapaa paikka sisäisissä taulukon päissä sitä on lisättävä, elementit kopioitava ja osoittimet "häntään" ja "päähän" päivitettävä. Tämä toiminto suoritetaan tarvittaessa lisättäessä elementtiä. StartIndex-parametria käytetään osoittamaan, kuinka monta kenttää tulee jättää tyhjäksi alussa (jos lisätään alkuun).

Huomaa, kuinka tiedot noudetaan, kun joudut hyppäämään taulukon alkuun, kun siirryt päästä häntään.

Yksityinen void allocateNewArray(int startIndex) ( int newLength = (_size == 0) ? 4: _size * 2; T newArray = new T; if (_size > 0) ( int targetIndex = startIndex; // Kopioi sisältö... / / Jos taulukko ei ole silmukka, kopioi elementit // Muussa tapauksessa kopioi alusta loppuun ja sitten taulukon alusta loppuun // Jos tail on pienempi kuin head, siirry alkuun (_häntä.< _head) { // Копируем _items.._items в newArray..newArray[N]. for (int index = _head; index < _items.Length; index++) { newArray = _items; targetIndex++; } // Копируем _items.._items в newArray.. for (int index = 0; index <= _tail; index++) { newArray = _items; targetIndex++; } } else { // Копируем _items.._items в newArray..newArray[N] for (int index = _head; index <= _tail; index++) { newArray = _items; targetIndex++; } } _head = startingIndex; _tail = targetIndex - 1; } else { // Массив пуст. _head = 0; _tail = -1; } _items = newArray; }

EnqueueFirst-menetelmä

• Käyttäytyminen: Lisää elementin jonon alkuun. Tämä elementti otetaan jonosta seuraavaksi, kun DequeueFirst-menetelmää kutsutaan.
• Monimutkaisuus:

public void EnqueueFirst(T item) ( // Tarkista, pitääkö taulukkoa kasvattaa: if (_items.Length == _size) ( allocateNewArray(1); ) // Koska taulukko ei ole täynnä ja _head on suurempi kuin 0, // tiedämme, että taulukon alussa on välilyöntiä if (_head > 0) ( _head--; ) else ( // Muuten meidän on tehtävä silmukka. _head = _items.Length - 1; ) _items[_head] =. item _size++ if ( _size == 1) ( // Jos lisäsimme ensimmäisen elementin tyhjään // jonoon, se on myös viimeinen, joten // meidän on päivitettävä myös _tail. _tail = _head; ) )

EnqueueLast -menetelmä

• Käyttäytyminen: Lisää elementin jonon loppuun. Tämä elementti otetaan jonosta seuraavaksi, kun DequeueLast-metodia kutsutaan.
• Monimutkaisuus: O(1) useimmissa tapauksissa; O(n), kun taulukon laajennusta tarvitaan.

public void EnqueueLast(T item) ( // Tarkista, pitääkö taulukkoa kasvattaa: if (_items.Length == _size) ( allocateNewArray(0); ) // Nyt kun meillä on sopiva taulukko, // jos _tail on lopussa taulukossa, meidän on siirryttävä alkuun if (_tail == _items.Length - 1) ( _tail = 0; ) else ( _tail++; ) _items[_tail] = item (_size == 1) (; // Jos lisäsimme viimeisen elementin tyhjään // jonoon, se on myös ensimmäinen, joten // meidän täytyy päivittää _head = _tail;

DequeueFirst-menetelmä

• Käyttäytyminen: Poistaa elementin jonon alusta ja palauttaa sen. Jos jono on tyhjä, antaa InvalidOperationException.
• Monimutkaisuus: O(1).

public T DequeueFirst() ( if (_size == 0) ( heittää uusi InvalidOperationException("Jäljitys on tyhjä"); ) T arvo = _items[_head]; if (_head == _items.Length - 1) ( // If head on asetettu viimeiseen hakemistoon, siirry taulukon alkuun _head = 0 else ( // Siirry seuraavaan elementtiin. _head++; ) _size--;

DequeueLast -menetelmä

• Käyttäytyminen: Poistaa elementin jonon lopusta ja palauttaa sen. Jos jono on tyhjä, antaa InvalidOperationException.
• Monimutkaisuus: O(1).

public T DequeueLast() ( if (_size == 0) ( heittää uusi InvalidOperationException("Deque on tyhjä"); ) T value = _items[_tail]; if (_tail == 0) ( // Jos häntä on asetettu alkutaulukko, siirry loppuun _tail = _items.Length - 1; else ( // Siirry edelliseen elementtiin. _tail--; ) _size--;

PeekFirst menetelmä

• Käyttäytyminen: Palauttaa elementin jonon alusta muuttamatta sitä. Jos jono on tyhjä, antaa InvalidOperationException.
• Monimutkaisuus: O(1).

public T PeekFirst() ( if (_size == 0) ( heittää uusi InvalidOperationException("Deque on tyhjä"); ) return _items[_head]; )

PeekLast menetelmä

• Käyttäytyminen: Palauttaa elementin jonon lopusta muokkaamatta sitä. Jos jono on tyhjä, antaa InvalidOperationException.
• Monimutkaisuus: O(1).

public T PeekLast() ( if (_size == 0) ( heittää uusi InvalidOperationException("Deque on tyhjä"); ) return _items[_tail]; )

Laskumenetelmä

• Käyttäytyminen: Palauttaa jonon elementtien määrän tai 0:n, jos jono on tyhjä.
• Monimutkaisuus: O(1).

public int Count ( get ( return _size; ) )

Jatkuu

Olemme nyt saaneet päätökseen artikkelisarjamme neljännen osan. Siinä katselimme pinoja ja jonoja. Seuraavalla kerralla siirrymme binäärihakupuihin.

– Igor (järjestelmänvalvoja)

Tässä artikkelissa kerron sinulle mikä on pino, sekä miksi sitä tarvitaan ja missä sitä käytetään.

Suuri määrä tietoon liittyviä ongelmia soveltuu standardoituun ratkaisuun. Siksi ei ole yllättävää, että monille heistä on jo pitkään keksitty menetelmiä, termejä ja kuvauksia. Voit esimerkiksi kuulla usein sanoja, kuten pino. Se kuulostaa erittäin monimutkaiselta, mutta kaikki on paljon yksinkertaisempaa.

Pino- Tämä on tapa esittää samantyyppisiä tietoja (voit kutsua sitä yksinkertaisesti tyypiksi) LIFO-järjestyksessä (Last In - First Out, mikä tarkoittaa "ensimmäinen sisään - viimeinen ulos"). On syytä mainita, että venäläisessä tekniikassa sitä kutsutaan myös "lehdeksi". Ja emme puhu tässä ruokakaupasta, vaan torvista, jossa on patruunat aseita varten, koska periaate on hyvin samanlainen - ensimmäistä asetettua patruunaa käytetään viimeisenä.

Huomautus: On syytä tietää, että tällä sanalla voi olla muita merkityksiä. Siksi, jos puhe ei koske tietokoneita, on järkevää selventää.

Ymmärtääkseni paremmin, annan sinulle esimerkin tosielämästä. Oletetaan, että sinulla on pino lakanoita. Asetat jokaisen kirjoitetun paperiarkin sen viereen ja jokaisen seuraavan muiden päälle. Jos haluat esimerkiksi saada ensimmäisen arkin tuloksena olevasta pinosta, sinun on vedettävä kaikki muut arkit ulos. Tämä on sama periaate, jolla pino on suunniteltu. Toisin sanoen jokaisesta viimeisestä lisätystä elementistä tulee ylin ja saadaksesi esimerkiksi aivan ensimmäisen elementin, sinun on vedettävä kaikki muut pois.

Mitä varten pino on? Päätarkoituksena on ratkaista tyypillisiä ongelmia, joissa on tarpeen ylläpitää jonkin tilasarjaa tai missä tarvitaan tietojen käänteistä esitystä (eli päinvastaiseen suuntaan).

Tietojenkäsittelyssä pinoa käytetään laitteistoissa (kuten prosessorissa), käyttöjärjestelmässä ja monissa ohjelmissa. Jos tarkastellaan esimerkkiä, jonka lähes kaikki ohjelmoineet ovat tuttuja, niin ilman pinorekursiota ei olisi mahdollista, koska joka kerta kun syötät funktion uudelleen, sinun on tallennettava nykyinen tila yläreunaan ja joka kerta kun poistu toiminnosta ja palauta tämä tila nopeasti (eli vain LIFO-sekvenssi). Ja jos kaivetaan vielä syvemmälle, niin periaatteessa koko lähestymistapa ohjelmien käynnistämiseen ja suorittamiseen perustuu pinoperiaatteeseen, jossa ennen kuin seuraava pääohjelmasta käynnistetty ohjelma suoritetaan, edellisen tila työnnetään pinoon, niin, että kun käynnissä oleva sovellus tai aliohjelma lopettaa suorituksen, edellinen Ohjelma jatkoi suoritustaan ​​normaalisti siitä, mihin se pysähtyi.

Mitkä ovat pinon toiminnot? Päätoimintoja on vain kaksi:

1. Elementin lisääminen pinon yläosaan kutsutaan työntää

2. Yläosan poistaminen kutsutaan pop

Mutta voit myös ajoittain törmätä ylimmän elementin lukemisen toteuttamiseen ilman sen purkamista - ns kurkistaa.

Miten pino on järjestetty? Tyypillisesti pino toteutetaan kahdella tavalla:

1. Käyttämällä taulukkoa ja muuttujaa, joka osoittaa pinon yläosassa olevaan soluun

2. Linkitettyjen luetteloiden käyttäminen

Jokaisella näistä kahdesta vaihtoehdosta on hyvät ja huonot puolensa. Esimerkiksi linkitetyt listat ovat turvallisempia käyttää, koska jokainen lisätty elementti sijoitetaan dynaamisesti luotuun rakenteeseen (elementtien lukumäärässä ei ole ongelmia - ei ole turva-aukkoja, jotka sallivat vapaan liikkumisen ohjelmamuistissa). Tallennustilan ja käyttönopeuden kannalta ne ovat kuitenkin vähemmän tehokkaita (ne vaativat lisätilaa osoittimien tallentamiseen; ne ovat hajallaan muistissa eivätkä sijoiteta peräkkäin, kuten taulukoissa).

Nyt tiedät, mikä pino on, sekä miksi sitä tarvitaan ja mihin sitä käytetään.

Pino on ohjelmointiilmiö ja luonnollinen ratkaisu. Stack tuli välittömästi tietokonealalle ja siitä tuli niin "natiivi", ikään kuin siitä kaikki alkoi.

Ilman pinoa prosessori ei toimi, ei ole rekursiota, ja tehokkaiden toimintokutsujen järjestäminen on mahdotonta. Mikä tahansa algoritmi pärjää ilman jonoa, luetteloa, kokoelmaa, taulukkoa tai järjestettyjen objektien järjestelmää, mutta mikään ei toimi ilman muistia ja pinoa, mukaan lukien kaikki edellä mainitut.

Alun kynnyksellä: prosessori, muisti ja pino

Ihanteellinen muisti tarjoaa osoitteen suoraan arvoon - nämä ovat korkean tason kone- ja kielitasoja. Ensimmäisessä tapauksessa prosessori iteroi peräkkäin muistiosoitteita ja suorittaa käskyjä. Toisessa tapauksessa ohjelmoija käsittelee taulukoita. Molemmat jaksot sisältävät:

• osoite = arvo;
• indeksi = arvo.

Osoite voi olla absoluuttinen ja suhteellinen, indeksi voi olla digitaalinen ja assosiatiivinen. Osoite ja indeksi voivat sisältää muun osoitteen kuin arvon, mutta nämä ovat epäsuoran osoittamisen yksityiskohtia. Ilman muistia prosessori ei voi toimia, ja ilman komentojen ja tietojen pinoa se on kuin vene ilman airoja.

Lautaspino on perinteinen tarina pinon olemuksesta: pinon käsitteestä ja käännöksestä yhteisessä tietoisuudessa. Et voi ottaa lautasta alhaalta, voit ottaa sen vain ylhäältä, ja sitten kaikki lautaset ovat ehjiä.

Se mikä tulee pinossa viimeisenä, menee ensin. Täydellinen ratkaisu. Pohjimmiltaan pino toiminnon käännöksenä toiseksi muuttaa idean algoritmista toimintosarjaksi.

Pinon olemus ja käsite

Prosessori ja muisti ovat tietokoneen tärkeimpiä rakennuspalikoita. Prosessori suorittaa käskyjä, käsittelee muistiosoitteita ja hakee ja muuttaa arvoja näissä osoitteissa. Ohjelmointikielessä tämä kaikki muunnetaan muuttujiksi ja niiden arvoiksi. Pinon olemus ja viimeinen sisään ensimmäinen ulos (LIFO) -konsepti pysyvät ennallaan.

Lyhennettä LIFO ei enää käytetä niin usein kuin ennen. Luultavasti siksi, että listat on muunnettu objekteiksi ja FIFO-jonoja käytetään tarpeen mukaan. Tietotyyppien dynamiikka on menettänyt merkityksensä muuttujien kuvauksen yhteydessä, mutta on saanut merkityksensä lausekkeiden suoritushetkellä: tiedon tyyppi määräytyy sen käyttöhetkellä, ja siihen asti voidaan kuvata. mitä tahansa ja miten haluat.

Joten pino - mikä se on? Nyt tiedät, että tämä on sopimaton kysymys. Loppujen lopuksi ilman pinoa ei ole nykyaikaista ohjelmointia. Mikä tahansa funktiokutsu tarkoittaa parametrien ja paluuosoitteen välittämistä. Funktio voi kutsua toista funktiota - tämä taas välittää parametreja ja paluuosoitetta. Arvojen kutsumismekanismin asettaminen ilman pinoa on ylimääräistä työtä, vaikka saavutettavissa oleva ratkaisu on varmasti mahdollinen.

Monet ihmiset kysyvät: "Pino - mikä se on?" Toimintokutsun yhteydessä se koostuu kolmesta toiminnosta:

• palautusosoitteen tallentaminen;
• tallentaa kaikki siirretyt muuttujat tai osoitteet niille;
• toimintokutsu.

Kun kutsuttu toiminto on suorittanut tehtävänsä, se yksinkertaisesti palauttaa ohjauksen palautusosoitteeseen. Funktio voi kutsua mitä tahansa muita toimintoja, koska raja on vain pinon koko.

Pinon ominaisuudet

Pino ei ole abstrakti tietotyyppi, vaan todellinen mekanismi. Prosessoritasolla se on "moottori", joka jalostaa ja täydentää pääprosessorisyklin työtä. Kuten bittiaritmetiikka, pino tallentaa yksinkertaiset ja ilmeiset toimintasäännöt. Se on luotettava ja turvallinen.

Pinon tunnusomaisia ​​ominaisuuksia ovat sen koko ja elementtien pituus. Prosessoritasolla kaiken määrää bittikapasiteetti, muistin osoitus ja siihen pääsyn fysiikka. Mielenkiintoinen piirre ja perinne: pino kasvaa alaspäin eli kohti pieneneviä muistiosoitteita ja ohjelma- ja datamuisti - ylöspäin. Tämä on yleistä, mutta ei pakollista. Merkitys tässä on tärkeä - hän tuli viimeisenä ja lähti ensimmäisenä. Tämän yllättävän yksinkertaisen säännön avulla voit rakentaa mielenkiintoisia algoritmeja, pääasiassa korkean tason kielillä. Nyt et kysy, mikä on pino?

Virheetön laitteistosuorituskyky on jo pitkään ollut normi, mutta tietotekniikan kärjessä pinon idea ottaa vastaan ​​uusia ja jännittäviä sovelluksia.

Pohjimmiltaan sillä ei ole väliä, mikä pino on prosessoritasolla. Se on luonnollinen osa tietokonearkkitehtuuria. Mutta ohjelmoinnissa pino riippuu tietystä sovelluksesta ja ohjelmoijan kyvystä.

Taulukot, kokoelmat, luettelot, jonot... Pino!

Ihmiset kysyvät usein kysymyksen: "Pino - mikä se on?" "Ohjelmointi" ja "järjestelmästäminen" ovat mielenkiintoisia käsitteitä: ne eivät ole synonyymejä, mutta ne liittyvät läheisesti toisiinsa. Ohjelmointi on mennyt niin pitkälle hyvin nopeasti, että saavutetut huiput näyttävät ihanteellisilta. Todennäköisesti näin ei ole. Mutta ilmeisesti jotain muuta.

Ajatus pinosta on tullut tutuksi paitsi eri ohjelmointikielten tasolla, myös niiden suunnittelun ja tietotyyppien luomiskyvyn tasolla. Kaikissa taulukoissa on push ja pop, ja käsitteistä "taulukon ensimmäinen ja viimeinen elementti" on tullut perinteisiä. Aiemmin oli vain taulukkoelementtejä, mutta nykyään niitä on:

• matriisin elementit;
• taulukon ensimmäinen elementti;
• taulukon viimeinen elementti.

Elementin sijoittaminen taulukkoon siirtää osoitinta, ja elementin hakeminen taulukon alusta tai sen lopusta vaikuttaa asiaan. Pohjimmiltaan tämä on sama pino, mutta sitä sovelletaan muihin tietotyyppeihin.

On erityisen huomionarvoista, että suosituilla ohjelmointikielillä ei ole pinorakennetta. Mutta he tarjoavat hänen ideansa kehittäjälle kokonaisuudessaan.

viimeinen sisään - ensimmäinen ulos, "viimeinen sisään - ensimmäinen ulos").

Useimmiten pinon toimintaperiaatetta verrataan lautaspinoon: ottaaksesi toisen ylhäältä, sinun on poistettava ylin.

Joillakin kielillä (esimerkiksi Lisp, Python) mitä tahansa luetteloa voidaan kutsua pinoksi, koska niille on saatavana pop- ja push-toiminnot. C++:ssa vakiokirjastossa on luokka, jossa on toteutettu rakenne ja menetelmät. Jne.

Tietosanakirja YouTube

1 / 3

Tietokone Tiede. Tietorakenteet: Pino. Foxfordin verkko-oppimiskeskus

#9. Pino / 1. Assembler ja menettelyt / Ohjelmointi tyhjästä

Tietoverkkojen perusteet. OSI-malli ja TCP IP-protokollapino. Ethernetin perusteet.

Tekstitykset

Ohjelmistopino

Järjestäminen muistissa

Usein pino toteutetaan yksisuuntaisena listana (jokainen listan elementti sisältää pinoon tallennettujen tietojen lisäksi osoittimen pinon seuraavaan elementtiin).

Mutta pino sijaitsee usein myös yksiulotteisessa taulukossa, jossa on järjestetyt osoitteet. Tämä pinojärjestely on kätevä, jos tietoelementti vie muistissa kiinteän määrän sanoja, esimerkiksi 1 sana. Tämä poistaa tarpeen tallentaa nimenomaista osoitinta pinoelementin seuraavaan pinoelementtiin, mikä säästää muistia. Tässä tapauksessa pinoosoitin ( Pinoosoitin, - SP) on yleensä prosessorirekisteri ja osoittaa pinon pään osoitteeseen.

Oletetaan esimerkiksi, että pinon pää sijaitsee alemmassa osoitteessa, seuraavat elementit sijaitsevat kasvavissa osoitteissa. Joka kerta kun sana työnnetään pinoon, SP:tä pienennetään ensin yhdellä ja sitten SP:n osoite kirjoitetaan muistiin. Joka kerta kun sana pompataan pinosta, se lukee ensin nykyisen osoitteen SP:stä ja lisää sitten SP:n sisältöä yhdellä.

Kun pino järjestetään yksisuuntaiseksi listaksi, pinomuuttujan arvo on osoitin sen yläosaan - yläosan osoitteeseen. Jos pino on tyhjä, osoittimen arvo on NULL.

Esimerkki pinon toteutuksesta C:ssä:

struct pino (char * data; struct pino * seuraava; );

Pinotoiminnot

Pinossa on kolme mahdollista toimintoa: elementin lisääminen (eli työntäminen), elementin poistaminen (pop) ja pääelementin lukeminen (peek).

Työntäessä (push) lisätään uusi elementti, joka osoittaa elementtiin, joka oli aiemmin pää. Uudesta elementistä tulee nyt pääelementti.

Kun elementti poistetaan (pop), ensimmäinen poistetaan ja pääelementistä tulee se, johon tällä objektilla oli osoitin (seuraava elementti). Tässä tapauksessa palautetaan poistetun elementin arvo.

void push (STACK * ps, int x) // Uuden elementin lisääminen pinoon( jos ( ps -> koko == PINON KOKO ) // Onko pino täynnä?( fputs ( "Virhe: pinon ylivuoto \n " , stderr ); keskeytä (); ) else ( ps -> kohteet [ ps -> koko ++ ] = x ; ) ) int pop ( PINO * ps ) // Poista pinosta(jos (ps -> koko == 0) // Onko pino tyhjä?( fputs ( "Virhe: pinon alivuoto \n " , stderr ); keskeytä (); ) else ( palauttaa ps -> kohteet [ -- ps -> koko ]; ) )

Sovellusalue

Pinon ohjelmointinäkymää käytetään tietorakenteiden, kuten puun tai graafin, läpikulkuun. Käyttämällä rekursiiviset funktiot Pinoa käytetään myös, mutta sen laitteistotyyppiä. Näiden lisäksi pinoa käytetään järjestämiseen

Samanlaisia ​​prosesseja tapahtuu laitteistokeskeytyksen aikana (X86-prosessori, jossa laitteiston keskeytys tallentaa lippurekisterin automaattisesti pinoon). Lisäksi kääntäjät sijoittavat pinoon proseduurin paikalliset muuttujat (jos prosessorilla on pääsy satunnaiseen pinon sijaintiin).

Ennen pinon käyttöä se on alustettava siten, että SS:ESP-rekisterit osoittavat pinon pään osoitteeseen fyysisen RAM-muistin alueella ja tarvittava määrä muistisoluja on varattava tietojen tallentamista varten. pino (ilmeisesti, ROM-pinoa ei tietenkään voi järjestää). Sovellusohjelmat, pääsääntöisesti käyttövalmis pino saadaan käyttöjärjestelmästä. Suojatussa prosessoritilassa tehtävän tilasegmentti sisältää neljä pinosegmentin valitsinta (eri käyttöoikeustasoille), mutta vain yhtä pinoa käytetään kerrallaan.