streamalism.org

1. Prehľad

V tomto výučbe si povieme, ako vytvoriť char zásobník v Jave. Najskôr si ukážeme, ako to dokážeme pomocou rozhrania Java API, a potom sa pozrieme na niektoré vlastné implementácie.

Stack je dátová štruktúra, ktorá sa riadi princípom LIFO (Last In First Out). Niektoré z jeho bežných metód sú:

• push (položka E) - posúva položku do hornej časti stohu
• pop () - odstráni a vráti objekt v hornej časti stohu
• nahliadnuť () - vráti objekt v hornej časti stohu bez jeho odstránenia

2. Char Skladanie pomocou Java API

Java má zabudované API s názvom java.util.Stack. Odkedy char je primitívny údajový typ, ktoré nemožno použiť v generike, musíme použiť obalovú triedu java.lang.Postava vytvoriť Stoh:

Stack charStack = nový Stack ();

Teraz môžeme použiť tam, popa nakuknúť metódy s našou Stoh.

Na druhej strane môžeme byť požiadaní, aby sme vytvorili vlastnú implementáciu zásobníka. Preto sa pozrieme na niekoľko rôznych prístupov.

3. Používanie vlastnej implementácie LinkedList

Implementujme a char stoh pomocou a LinkedList ako naša back-endová dátová štruktúra:

verejná trieda CharStack {súkromné ​​položky LinkedList; public CharStack () {this.items = new LinkedList (); }}

Vytvorili sme položky premenná, ktorá sa inicializuje v konštruktore.

Teraz musíme zabezpečiť implementáciu tam, nakuknúťa pop metódy:

public void push (znaková položka) {items.push (položka); } public Character peek () {return items.getFirst (); } public Znak pop () {Iterator iter = items.iterator (); Položka znaku = iter.next (); if (item! = null) {iter.remove (); vrátiť položku; } return null; }

The tam a nakuknúť metódy používajú vstavané metódy a LinkedList. Pre pop, najskôr sme použili Iterátor skontrolovať, či je položka v hornej časti alebo nie. Ak tam je, odstránime položku zo zoznamu zavolaním na odstrániť metóda.

4. Vlastná implementácia pomocou poľa

Môžeme tiež použiť pole pre našu dátovú štruktúru:

public class CharStackWithArray {private char [] prvky; veľkosť súkromného int; public CharStackWithArray () {size = 0; prvky = nový znak [4]; }}

Hore tvoríme a char pole, ktoré inicializujeme v konštruktore s počiatočnou kapacitou 4. Dodatočne máme a veľkosť premenná na sledovanie toho, koľko záznamov je v našom zásobníku.

Teraz poďme implementovať tam metóda:

public void push (char položka) {zaistiť kapacitu (veľkosť + 1); prvky [veľkosť] = položka; veľkosť ++; } private void ensureCapacity (int newSize) {char newBiggerArray []; if (elements.length <newSize) {newBiggerArray = new char [elements.length * 2]; System.arraycopy (prvky, 0, newBiggerArray, 0, veľkosť); elements = newBiggerArray; }}

Pri posúvaní položky do stohu musíme najskôr skontrolovať, či má naše pole kapacitu na jej uloženie. Ak nie, vytvoríme nové pole a zdvojnásobíme jeho veľkosť. Potom skopírujeme staré prvky do novo vytvoreného poľa a priradíme ho k nášmu prvkov premenná.

Poznámka: Vysvetlenie, prečo chceme veľkosť poľa zdvojnásobiť, a nie jednoducho zväčšiť veľkosť o jednu, nájdete v tomto príspevku StackOverflow.

Nakoniec poďme implementovať nakuknúť a pop metódy:

public char peek () {if (size == 0) {throw new EmptyStackException (); } návratové prvky [veľkosť - 1]; } public char pop () {if (size == 0) {throw new EmptyStackException (); } návratové prvky [- veľkosť]; }

U oboch metód po overení, že zásobník nie je prázdny, vrátime prvok na pozíciu veľkosť - 1. Pre pop, okrem vrátenia prvku znížime veľkosť o 1.

5. Záver

V tomto článku sme sa naučili, ako vyrobiť char stack pomocou Java API a videli sme niekoľko vlastných implementácií.

Kód uvedený v tomto článku je k dispozícii na GitHub.