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.