streamalism.org

1. Oversikt

I denne opplæringen vil vi diskutere hvordan du lager en røye stable i Java. Vi ser først hvordan vi kan gjøre dette ved hjelp av Java API, og deretter ser vi på noen tilpassede implementeringer.

Stack er en datastruktur som følger LIFO (Last In First Out) -prinsippet. Noen av de vanlige metodene er:

• trykk (E-element) - skyver et element til toppen av bunken
• pop () - fjerner og returnerer objektet øverst i bunken
• kikke () - returnerer objektet på toppen av bunken uten å fjerne det

2. Char Stakk ved hjelp av Java API

Java har et innebygd API-navn java.util.Stack. Siden røye er en primitiv datatype, som ikke kan brukes i generiske legemidler, vi må bruke innpakningsklassen java.lang.Character å lage en Stable:

Stack charStack = ny Stack ();

Nå kan vi bruke trykk, pop, og kikke metoder med vår Stable.

På den annen side kan vi bli bedt om å lage en tilpasset implementering av en stabel. Derfor vil vi se på et par forskjellige tilnærminger.

3. Egendefinert implementering ved hjelp av LinkedList

La oss implementere en røye stable ved hjelp av en LinkedList som vår back-end datastruktur:

offentlig klasse CharStack {private LinkedList-varer; public CharStack () {this.items = new LinkedList (); }}

Vi opprettet en gjenstander variabel som blir initialisert i konstruktøren.

Nå må vi gi en implementering av trykk, kikke, og pop metoder:

public void push (Character item) {items.push (item); } offentlig karaktertitt () {return items.getFirst (); } public Character pop () {Iterator iter = items.iterator (); Tegnelement = iter.next (); if (item! = null) {iter.remove (); returvare; } returner null; }

De trykk og kikke metodene bruker de innebygde metodene til a LinkedList. Til pop, vi brukte først en Iterator for å sjekke om det er en vare på toppen eller ikke. Hvis det er der, fjerner vi elementet fra listen ved å ringe fjerne metode.

4. Egendefinert implementering ved hjelp av en matrise

Vi kan også bruke en matrise for datastrukturen vår:

offentlig klasse CharStackWithArray {private char [] elementer; privat int størrelse; offentlig CharStackWithArray () {størrelse = 0; elementer = ny røye [4]; }}

Ovenfor lager vi en røye array, som vi initialiserer i konstruktøren med en innledende kapasitet på 4. I tillegg har vi en størrelse variabel for å holde rede på hvor mange poster som er tilstede i stakken vår.

La oss nå implementere trykk metode:

public void push (char item) {sikreKapasitet (størrelse + 1); elementer [størrelse] = vare; størrelse ++; } privat tomrom sikre Kapasitet (int newSize) {char newBiggerArray []; hvis (elements.length <newSize) {newBiggerArray = new char [elements.length * 2]; System.arraycopy (elementer, 0, newBiggerArray, 0, størrelse); elementer = newBiggerArray; }}

Mens vi skyver et element til bunken, må vi først sjekke om matrisen vår har kapasitet til å lagre den. Hvis ikke, oppretter vi en ny matrise og dobler størrelsen. Vi kopierer deretter de gamle elementene til den nyopprettede matrisen og tilordner den til vår elementer variabel.

Merk: For en forklaring på hvorfor vi vil doble størrelsen på matrisen, i stedet for å bare øke størrelsen med en, kan du se dette StackOverflow-innlegget.

Til slutt, la oss implementere kikke og pop metoder:

public char peek () {if (size == 0) {throw new EmptyStackException (); } returelementer [størrelse - 1]; } public char pop () {if (size == 0) {throw new EmptyStackException (); } returelementer [- størrelse]; }

For begge metodene, etter å ha validert at stakken ikke er tom, returnerer vi elementet i posisjon størrelse - 1. For pop, i tillegg til å returnere elementet, reduserer vi størrelse innen 1.

5. Konklusjon

I denne artikkelen lærte vi hvordan vi lager en røye stack ved hjelp av Java API, og vi så et par tilpassede implementeringer.

Koden presentert i denne artikkelen er tilgjengelig på GitHub.