Java >> Java tutorial >  >> Tag >> char

Definering af en Char Stack i Java

char

1. Oversigt

I denne selvstudie vil vi diskutere, hvordan man opretter en char stak i Java. Vi vil først se, hvordan vi kan gøre dette ved at bruge Java API, og derefter vil vi se på nogle tilpassede implementeringer.

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

  • push(E element) – skubber et element til toppen af ​​stakken
  • pop() – fjerner og returnerer objektet øverst i stakken
  • kig() – returnerer objektet øverst i stakken uden at fjerne det

2. Char Stak ved hjælp af Java API

Java har en indbygget API ved navn java.util.Stack . Siden char er en primitiv datatype , som ikke kan bruges i generiske lægemidler, vi skal bruge indpakningsklassen java.lang.Character for at oprette en stak :

Stack<Character> charStack = new Stack<>();

Nu kan vi bruge push , pop , og kig metoder med vores stak .

På den anden side kan vi blive bedt om at bygge en tilpasset implementering af en stack. Derfor vil vi se nærmere på et par forskellige tilgange.

3. Tilpasset implementering ved hjælp af LinkedList

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

public class CharStack {

    private LinkedList<Character> items;

    public CharStack() {
        this.items = new LinkedList<Character>();
    }
}

Vi oprettede et element variabel, der bliver initialiseret i konstruktøren.

Nu skal vi levere en implementering af push , kig og pop metoder:

public void push(Character item) {
    items.push(item);
}

public Character peek() {
    return items.getFirst();
}

public Character pop() {
    Iterator<Character> iter = items.iterator();
    Character item = iter.next();
    if (item != null) {
        iter.remove();
        return item;
    }
    return null;
}

skub og kig metoder bruger de indbyggede metoder i en LinkedList . Til pop , brugte vi først en Iterator for at kontrollere, om der er et element på toppen eller ej. Hvis det er der, fjerner vi elementet fra listen ved at kalde fjern metode.

4. Brugerdefineret implementering ved hjælp af et array

Vi kan også bruge et array til vores datastruktur:

public class CharStackWithArray {

    private char[] elements;
    private int size;

    public CharStackWithArray() {
        size = 0;
        elements = new 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 push metode:

public void push(char item) {
    ensureCapacity(size + 1);
    elements[size] = item;
    size++;
}

private void ensureCapacity(int newSize) {
    char newBiggerArray[];
    if (elements.length < newSize) {
        newBiggerArray = new char[elements.length * 2];
        System.arraycopy(elements, 0, newBiggerArray, 0, size);
        elements = newBiggerArray;
    }
}

Mens vi skubber et emne til stakken, skal vi først kontrollere, om vores array har kapacitet til at gemme det. Hvis ikke, opretter vi en ny matrix og fordobler dens størrelse. 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 af ​​arrayet i stedet for blot at øge størrelsen med én, se venligst dette StackOverflow-indlæg.

Lad os endelig implementere kig og pop metoder:

public char peek() {
    if (size == 0) {
        throw new EmptyStackException();
    }
    return elements[size - 1];
}

public char pop() {
    if (size == 0) {
        throw new EmptyStackException();
    }
    return elements[--size];
}

For begge metoder returnerer vi elementet ved position størrelse – efter at have valideret, at stakken ikke er tom. 1. Til pop , ud over at returnere elementet, formindsker vi størrelsen inden 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 tilpassede implementeringer.

Koden, der præsenteres i denne artikel, er tilgængelig på GitHub.


Java tag