Stivele, cozile, decembrie

Pe baza listelor liniare pot fi construite stive, cozi, punte.

(Conform funcționării metodei de adăugare și ștergerea elementelor)

Stiva Coadă decembrie

Stivă - o listă liniară cu o lungime variabilă, în care toate deleții și accesul la date sunt efectuate pe un singur capăt al listei, numit partea de sus a stivei.

Utilizate alte nume stivă - magazin și porniți printsipuLIFO funcțională (Last-In-First-Out - "ultima in - primul exclus"). Sistem de programare pentru o orientare bloc de limbi (Pascal, C și colab.), folosește stiva pentru care conține variabile și proceduri de alte blocuri de software locale. În fiecare procedură de activare a memoriei pentru variabilele sale locale alocate pe stivă; la încheierea acestei proceduri, memoria este eliberată. Ca întotdeauna atunci când procedura este strict observată cuibărire, în partea de sus a stivei este întotdeauna în memorie, variabilele locale care conțin procedura activă în prezent.

Coadă - aceasta este o listă liniară de lungime variabilă, în care elementul de comutare se realizează cu o singură mână lista (această direcție este adesea numit capătul cozii sau coada), și o excepție - pe de altă parte (denumit începutul cozii sau a capului).

Cozile sunt, de asemenea, numite „spiskamitipaFIFO» (Primul - In - Out întâi la scară mică- - «primul venit - primul exclus").

Inițial, pointerii la punctul de început și de sfârșit la începutul zonei de memorie. Egalitatea dintre cele două indicatoare (în oricare din valoarea lor) este semnul unei cozi de gol.

Decembrie (de la DEQ engleză -. Dublu coadă încheiat, adică o coadă cu două capete), este o structură de date în care pentru a adăuga sau elimina elemente din ambele părți.

Sarcini care necesită structuri de punte găsite în informatică și programare, mult mai puțin decât sarcinile puse în aplicare în structura stivei sau coada. De regulă, întreaga organizare a punții este efectuată de către programator fără mijloace speciale de sprijin sistemic.

Un exemplu de punte poate fi, de exemplu, un terminal, în care comanda de intrare, fiecare dintre acestea se realizează ceva timp. Dacă introduceți această comandă, fără să aștepte până la sfârșitul execuției anterioare, acesta va cădea în linie și va fi executat imediat ce terminale disponibile. Aceasta este o coadă FIFO. În cazul în care, în plus față de a introduce operațiunea anula ultima comandă introdusă, se pare, în decembrie.

înregistrarea formează o expresie aritmetică:

Infixat - înregistrarea, în care se află semnul operației aritmetice dintre operanzi (A + B).

Prefix - notație în care precede operațiune semnul operandului (+ AB).

Postfix - înregistrarea, în care operațiunile de conectare situate în spatele operanzi (AB +).

Notă. forma prefixul nu este o postfix imagine în oglindă. De exemplu:

* -AB + CD - notatia prefix;

AB-CD + * - notatie postfix.

Unul dintre principalele motive care stau la baza apariției unei limbaje de programare de nivel înalt, au fost sarcinile de calcul care necesită un volum mare de calcule de rutină. Prin urmare, limbajele de programare face cereri de înregistrare forme de calcul maxime aproximare a limbajului natural al matematicii. În acest sens, una dintre primele zone ale sistemului de programare a format studiul de moduri de expresii. Există numeroase rezultate obținute, dar cele mai utilizate pe scară largă metoda de difuzare prin RPN (postfix notație), care a sugerat matematician polonez J. Loukachevitch.

Examinați șirul de caractere original, de la stânga la dreapta, operanzii sunt copiate la șirul de ieșire, și semne de funcționare sunt înregistrate în stivă bazat pe următoarele considerente:

Dacă următorul caracter din șirul sursă are paranteze deschise, acesta este împins pe stiva;

Paranteza de închidere împinge toate operațiunile din stivă în linia de ieșire la cea mai apropiată paranteza de deschidere, Pregatindu-se la șirul de ieșire nu este rescris, și anihila reciproc;

operațiune împinge toate operațiile stiva mai mare decât sau egală cu prioritate în șirul de ieșire;

în cazul în care stiva este goală, funcționarea șirului de intrare este suprascris pe stivă.

Procesul de obținere a expresiilor RPN (A + B) * (C + D) -e reprezentat schematic în tabelul