met deze belangrijke methoden uitgelegd, laten we eens kijken naar de uiteindelijke implementatie van onze stack klasse:
de push-en pop-methoden verschijnen precies zoals we verwachten (lijnen 13-32). We kunnen onze push methode gebruiken om een aangepaste initializer te maken met een aantal variadische waarden (regels 7-11). Daarnaast kunnen we controleren op een lege stack door te controleren of onze rootNode een waarde heeft (regels 34-36) en een eenvoudige afdrukmethode hebben die door onze lijst itereert zolang het in staat is om toegang te krijgen tot knooppunten via de volgende eigenschap (regels 38-44).
een basis test van onze stack functionaliteit ziet er als volgt uit:
weten hoe je een stack moet implementeren is één ding, maar nog belangrijker is het herkennen van situaties waarvoor een stack goed geschikt is. In deze volgende paragraaf zullen we kijken naar drie dergelijke gevallen.
Use Case 1: Omgekeerde volgorde
omdat de volgorde van een stapel vast is, kan een omgekeerde volgorde heel gemakkelijk worden bereikt door elementen van de ene stapel en onmiddellijk op een andere te plaatsen. Geen gerommel met het wisselen van indexen!
Use Case 2: het testen van symmetrie
een andere goede use case voor stapels is het testen van symmetrie. In het onderstaande voorbeeld testen we een reeks beugels om er zeker van te zijn dat elke sluitbeugel de juiste tegenhanger is van een eerdere openingsbeugel.
we beginnen met het controleren of het aantal tekens deelbaar is door twee zoals een oneven aantal tekens onmiddellijk door asymmetrisch zou worden (regel 6). Vervolgens controleren we of we geldige invoer hebben door een tekenset van illegale karakters te definiëren en vervolgens te controleren of onze invoerstring een nulbereik van illegale karakters heeft (regels 7-8). Om te controleren of onze sluit-en openingsbeugels overeenkomen, zetten we ze in een woordenboek als sleutelwaardeparen (regel 10). In andere situaties kunt u de inverse waarde berekenen zonder dat u paren in een woordenboek hoeft op te slaan. Dan hebben we onze stack (lijn 11). Het doel van onze stapel in dit geval is om de opening beugels op te slaan. Terwijl we door onze String herhalen, kunnen we controleren of ons karakter een openingshaakje is door te testen of het een sleutel is in ons woordenboek. Als dat zo is, duwen we het op onze stapel. Zodra we onze eerste gesloten beugel vinden, weten we dat we door de tweede helft van ons patroon werken, dus zetten we onze eerste helft Booleaans op onwaar (regel 12). Als we nog meer openingshaken vinden na dit punt kunnen we de boolean controleren en een mislukte test aangeven. Voor elke sluitbeugel, we pop-off de laatste opening beugel en controleren of ze een juiste sleutel-waarde paar. Nogmaals, we hoeven maar één keer door de string te itereren, dus we krijgen veel waarde uit een lineair algoritme.
Use Case 3: Undoing commando ‘ s
tenslotte zullen we een stack gebruiken in combinatie met het opdrachtpatroon, om een bewerkingsgeschiedenis aan te maken. Om te beginnen, laten we eens een kijkje nemen op een eenvoudige bankrekening object. Het heeft een saldo en een debetstand limiet en een aantal eenvoudige methoden voor het storten en opnemen van fondsen:
in plaats van de stortings-en opnamemethoden direct te bellen, kunnen we de relevante informatie opslaan in een opdracht. In het fragment hieronder, specificeren we wat voor soort actie we willen uitvoeren met een enum eigenschap (storting of opname) en een bedrag . We slaan ook een boolean op om aan te geven of het commando kon worden uitgevoerd (regels 4-11). Merk op dat als het verzoek tot opname de limiet overschrijdt, er niets zal gebeuren met de bankrekening en de succesvolle boolean zal onwaar blijven, anders zal het waar worden zodra het commando is voltooid (regels 18-26). We hebben twee methoden voor het aanroepen of ongedaan maken van het commando, elk met een bankrekening als argument (regels 18 & 28). Deze methoden nemen de bankrekening en noemen de instantie methoden die we zagen in het vorige fragment.
teruggaand naar de bankrekening, kunnen we nu onze commandStack-eigenschap introduceren, die is geïnitialiseerd met ons BankAccountType (regel 47). We markeren onze stortings – en opnamemethoden als fileprive, zodat ze alleen toegankelijk zijn voor onze Bankrekeningcommand (lijnen 62 & 66). Nu hebben we twee blootgestelde methoden: process (command:) en undoLastCommand (). De eerste accepteert een commando als invoer, voert het uit met de bankrekening als invoer, en pusht het commando vervolgens op de stack. Ondertussen de undoLastCommand methode, pops het laatste commando van de stack en voert een undo (regels 51-60).
dit is een zeer eenvoudig patroon, en een die zeer krachtig is. De mogelijke toepassingen zijn eindeloos en zorgen voor een bevredigende gebruikerservaring.
en nu laten we het patroon in actie zien:
Wrap Up
In dit artikel hebben we het concept van een stack en LIFO-gedrag onderzocht. We implementeerden onze eigen stack met behulp van een dubbel gelinkte lijst en demonstreerden hoe het geheugen toewijst en dealloceert naarmate de grootte van de stack verandert. We hebben ook gekeken naar drie veel voorkomende use cases voor stapels: omkeren, symmetrie testen en ongedaan maken. Elk van deze drie situaties komen talloze keren voor in projecten in de echte wereld. Ik hoop dat u zult denken van een stack als een geschikte structuur voor het omgaan met die behoeften. Zoals altijd, bedankt voor het lezen!