streamalism.org

1. Oversigt

I denne vejledning diskuterer vi, hvordan du opretter en char stak i Java. Vi ser først, hvordan vi kan gøre dette ved hjælp af Java API, og derefter ser vi på nogle brugerdefinerede implementeringer.

Stack er en datastruktur, der følger LIFO (Last In First Out) -princippet. Nogle af dens almindelige metoder er:

• tryk (E-vare) - skubber et emne til toppen af ​​stakken
• pop () - fjerner og returnerer objektet øverst i stakken
• kigge () - returnerer objektet øverst i stakken uden at fjerne det

2. Char Stak ved hjælp af Java API

Java har en indbygget API med navnet java.util.Stack. Siden char er en primitiv datatype, som ikke kan bruges i generiske stoffer, vi skal bruge indpakningsklassen af java.lang.Character at oprette en Stak:

Stak charStack = ny stak ();

Nu kan vi bruge skubbe, popog kigge metoder med vores Stak.

På den anden side kan vi blive bedt om at oprette en brugerdefineret implementering af en stak. Derfor vil vi se på et par forskellige tilgange.

3. Brugertilpasset implementering LinkedList

Lad os implementere en char stak ved hjælp af en LinkedList som vores back-end datastruktur:

offentlig klasse CharStack {private LinkedList-emner; offentlig CharStack () {this.items = ny LinkedList (); }}

Vi oprettede en genstande variabel, der initialiseres i konstruktøren.

Nu skal vi give en implementering af skubbe, kiggeog pop metoder:

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

Det skubbe og kigge metoder bruger de indbyggede metoder til a LinkedList. Til pop, vi brugte først en Iterator for at kontrollere, om der er en vare øverst eller ej. Hvis det er der, fjerner vi elementet fra listen ved at ringe til fjerne metode.

4. Brugerdefineret implementering ved hjælp af en matrix

Vi kan også bruge et array til vores datastruktur:

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

Ovenfor opretter vi en char array, som vi initialiserer i konstruktøren med en startkapacitet på 4. Derudover har vi en størrelse variabel for at holde styr på, hvor mange poster der er til stede i vores stak.

Lad os nu implementere skubbe metode:

public void push (char item) {sikreCapacity (størrelse + 1); elementer [størrelse] = vare; størrelse ++; } privat tomrum sikre Kapacitet (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 skubber et element til stakken, skal vi først kontrollere, om vores array har kapacitet til at gemme det. Hvis ikke, opretter vi et nyt array og fordobler størrelsen. Vi kopierer derefter de gamle elementer til det nyoprettede array og tildeler det til vores elementer variabel.

Bemærk: For en forklaring på, hvorfor vi ønsker at fordoble størrelsen på arrayet i stedet for blot at øge størrelsen med en, se venligst dette StackOverflow-indlæg.

Lad os endelig implementere kigge og pop metoder:

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

Efter begge validering af, at stakken ikke er tom, returnerer vi elementet på begge måder størrelse - 1. For popud over at returnere elementet mindsker vi også størrelse ved 1.

5. Konklusion

I denne artikel lærte vi, hvordan man laver en char stak ved hjælp af Java API, og vi så et par tilpasset implementering.

Koden præsenteret i denne artikel er tilgængelig på GitHub.