Дефиниране на Char Stack в Java

1. Общ преглед

В този урок ще разгледаме как да създадете Чар комин в Java. Първо ще видим как можем да направим това, като използваме Java API, а след това ще разгледаме някои персонализирани реализации.

Стекът е структура от данни, която следва принципа LIFO (Last In First Out). Някои от най-често срещаните му методи са:

  • push (E item) - избутва елемент в горната част на стека
  • pop () - премахва и връща обекта в горната част на стека
  • peek () - връща обекта в горната част на стека, без да го премахва

2. Char Stack с помощта на Java API

Java има вграден API на име java.util.Stack . Тъй като char е примитивен тип данни , който не може да се използва в генеричните продукти, трябва да използваме класа на обвивката на java.lang.Character, за да създадем стек :

Stack charStack = new Stack();

Сега можем да използваме методите push , pop и peek с нашия стек .

От друга страна, може да бъдем помолени да създадем персонализирана реализация на стека. Затова ще разгледаме няколко различни подхода.

3. Изпълнение по поръчка с помощта на LinkedList

Нека да приложи Чар стека с помощта на LinkedList като нашата структура на гърба в края на данните:

public class CharStack { private LinkedList items; public CharStack() { this.items = new LinkedList(); } }

Създадохме променлива items, която се инициализира в конструктора.

Сега трябва да осигурим изпълнение на методите push , peek и pop :

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

Методите push и peek използват вградените методи на LinkedList . За поп първо използвахме Iterator, за да проверим дали има елемент отгоре или не. Ако е там, премахваме елемента от списъка, като извикаме метода за премахване .

4. Изпълнение по поръчка с помощта на масив

Също така можем да използваме масив за нашата структура от данни:

public class CharStackWithArray { private char[] elements; private int size; public CharStackWithArray() { size = 0; elements = new char[4]; } }

По-горе създаваме масив char , който инициализираме в конструктора с първоначален капацитет 4. Освен това имаме променлива за размер, за да следим колко записа има в нашия стек.

Сега, нека приложим метода push :

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; } }

Докато избутваме елемент в стека, първо трябва да проверим дали нашият масив има капацитета да го съхранява. Ако не, създаваме нов масив и удвояваме размера му. След това копираме старите елементи в новосъздадения масив и го присвояваме на нашата променлива елементи .

Забележка: за обяснение защо искаме да удвоим размера на масива, вместо просто да увеличим размера с един, вижте тази публикация в StackOverflow.

И накрая, нека приложим методите peek и pop :

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]; }

И за двата метода, след като проверим, че стекът не е празен, връщаме елемента в размер на позицията - 1. За pop , освен връщането на елемента, намаляваме размера с 1.

5. Заключение

В тази статия научихме как да направим стек от символи с помощта на Java API и видяхме няколко персонализирани реализации.

Кодът, представен в тази статия, е достъпен в GitHub.