Batterij

In de informatica, een stapel is een datastructuur gebaseerd op het principe van de 'last in, first out ", wat betekent dat de nieuwste items toegevoegd aan de stapel zal de eerste zijn in te vorderen. De werking is die van een stapel van platen: toevoegen van platen op de stapel en wordt teruggewonnen in omgekeerde volgorde, dus de laatste toegevoegd.

System Battery

De meeste microprocessors native beheren van een stapel. Het komt overeen met een geheugengebied en de processor bevat het adres van het laatste element.

X86

In de 32bit x86, wordt de ESP register gebruikt om het adres van de bovenzijde van een stapel in het RAM geven. Opcodes "push" en "pop" worden respectievelijk gebruikt voor het stapelen en ontstapelen van de gegevens. Opcodes "call" en "ret" gebruiken de stapel om een ​​functie aan te roepen en later vertrekken door terug te keren naar de instructie onmiddellijk na het gesprek.

Indien onderbroken, worden de EFLAGS, CS en EIP registers automatisch gestapeld. In het geval van een prioriteit van verandering op onderbreking, SS en ESP registers zijn ook.

Een andere stack bestaat in de x86 CPU, dat de floating point unit. Specifiek apparaat gebruikt een stapel beperkt tot 8 leden en van de werking is vergelijkbaar met een vat. Het element van de huidige cilinder wordt genoemd st, st de volgende onderdelen N van 1 tot 7. De batterij kan berekeningen uitvoeren op de wijze van een handcalculator, stapelen waarden en vervolgens aanbrengen van een operatie op de laatste waarden gestapelde voorbeeld.

Architectuur, gebaseerd op de stack

Sommige processoren gebruiken geen algemene register, maar de stapel. De instructies dan verwijzen haar eerste elementen. Bijvoorbeeld, Hewlett-Packard calculators, Focus processors of machines in het traject Burroughs B 5000. De instructies worden dan vaak korter, omdat zij niet verwijzen naar registers. De bytecode van Java maakt ook gebruik van deze truc.

Programmeertaal

In de meeste gecompileerde programmeertalen de uitvoering stack wanneer geduwd of alle oproepparameters van procedures en functies. Verder is er ruimte creëert voor lokale variabelen. De batterij wordt dus gevormd bestaande uit stack frames voor elke geneste tijdens een gesprek procedure de parameters, de lokale variabelen en terug te keren punt.

Primitieven

Hier primitieve vaak gebruikt om cellen te manipuleren. Er is geen standaardisatie in primitieve stack manipulatie. Hun namen zijn daarom informeel aangegeven. Alleen de eerste drie daadwerkelijk vereist, kunnen de andere twee worden afgeleid.

  • "Stack": voegt een element op de stack. Overeenkomstige Engels woord "Push".
  • "Unstack" verwijdert een element uit de stapel en geeft het. Overeenkomstige Engels woord "Pop".
  • "Is de batterij leeg? "Geeft true als de stapel leeg is, anders false.
  • 'Veel van de stapel elementen "geeft het aantal elementen in de stapel. Volgens implementaties, kan zowel in constante tijd, hetzij in lineaire tijd.
  • "Wat is het hoofd element? "Geeft het bovenste element zonder ontstapelen. Overeenkomstige Engels woord "Peek".
  • "Lege lijst" ontstapelen alle items. Afhankelijk van de uitvoering kan dit geschieden constante of lineaire tijd. Overeenkomstige Engels woord "Clear".
  • "Dubbele het hoofd element" en "Vervangen van de eerste twee elementen" op calculators actief zijn in omgekeerde Poolse notatie. Overeenkomstige Engels woorden: "Dup" en "Swap" respectievelijk.

Algoritme

Deze implementatie is gebruikt in de processors is eenvoudig en de batterij neemt weinig ruimte in. Een implementatie als een gekoppelde lijst is ook mogelijk om programma's.

Toepassingen

  • In een webbrowser, wordt een stack gebruikt om webpagina's op te slaan bezocht. Het nieuwe adres van elke pagina bezocht wordt gestapeld en gestapelde gebruiker het adres van de vorige pagina door te klikken op de knop "Show vorige pagina."
  • De evaluatie van wiskundige uitdrukkingen in post-vaste notatie maakt gebruik van een stapel.
  • De "Undo typen" van een tekstverwerker slaat de tekst verandert in een stapel.
  • Een grondige zoekalgoritme maakt gebruik van een stapel om de knooppunten bezocht slaan.
  • Zo kan men zeer eenvoudig omkeren van de elementen in een matrix of een tekenreeks met een batterij. Gewoon stapelen de elementen op een stapel en vervolgens reconstrueren de tegenoverliggende tafel désempilant elementen.
  • De recursieve algoritmen impliciet toegegeven door sommige talen gebruiken een call stack. In een niet-recursieve taal, zodat we kunnen altijd simuleren recursie creëren primitieve beheer van een batterij.