/** * Stos liczb całkowitych - implementacja tablicowa * @author kodatnik.blogspot.com */ class Stos { // tablica przechowująca elementy stosu private int[] wektor; // wierzchołek stosu private int top; // konstruktor domyślny (tworzy stos 10 elementowy) public Stos() { // wywołujemy konstruktor z parametrem int (czyli ten poniżej) this(10); } // konstruktor jednoparametrowy public Stos(int rozmiar) { // tworzymy tablicę o rozmiarze przekazanym jako parametr wywołania wektor = new int[rozmiar]; // ustawiamy wartość początkową wierzchołka stosu top = -1; } // metoda odkładająca na stosie elementy public void push(int element) { // wpisujemy na odpowiedniej pozycji element oraz zwiększamy wierzchołek wektor[++top] = element; } // metoda ściąga ze stosu element public int pop() { // zwracamy element z wierzchołka stosu oraz zmniejszamy wierzchołek return wektor[top--]; } // metoda sprawdza czy stos jest pusty public boolean czyPusty() { // zwracamy prawdę lub fałsz return (top == -1); } // metoda sprawdza czy stos jest pełny public boolean czyPelny() { // zwracamy prawdę lub fałsz return (top == wektor.length); } // metoda "podgląda" co jest na wierzchołku stosu public int peek() { // zwracamy element z wierzchołka stosu (nie modyfikujemy zmiennej top) return wektor[top]; } // metoda wyświetla wszystkie elementy stanowiące stos public void wyswietl() { // w pętli do wierzchołka stosu for(int i = 0; i <= top; i++) // wyświetlamy poszczególne elementy System.out.print(wektor[i] + " "); System.out.println(); } // metoda zwraca rozmiar stosu (liczbę jego elementów) public int rozmiar() { return top + 1; } }
/** * Test kolejki liczb całkowitych * @author kodatnik.blogspot.com */ public class TestKolejki { public static void main(String args[]) { // zakładamy nowy stos o rozmiarze 20 Stos s = new Stos(20); // odkładamy kolejne wartości na stos s.push(12); s.push(8); s.push(39); // wyświetlamy zawartość stosu s.wyswietl(); // wyświetlamy element znajdujący się na szczycie (bez jego ściągania) System.out.println(s.peek()); // ściągamy element ze stosu s.pop(); // wyświetlamy zawartość stosu s.wyswietl(); } }Uruchomiona aplikacja:
12 8 39 39 12 8Powyższy stos jest statyczny, jego rozmiar ustalamy podczas tworzenia obiektu (nie mamy możliwości jego zmiany w trakcie działania). Przechowujemy dane tylko jednego typu (int), co w większości zastosowań może okazać się niewystarczające. Lepszym rozwiązaniem jest zastosowanie do implementacji stosu list powiązanych (struktura dynamiczna) oraz wykorzystanie typów generycznych (możliwość tworzenia stosów przechowujących dowolny typ danych).
Stos jest często wykorzystywany w algorytmice jak również w większości aplikacji, z którymi pracujemy codziennie (np. operacja cofnij w edytorach tekstu czy grafiki).
3 Komentarze - Stos - implementacja tablicowa
Kawał dobrej roboty, dziękuje Ci bardzo ;)
linia 46. zamiast 'return (top == wektor.length);' powinno być return (top == wektor.length - 1);
Wiąże się to z tym, że metoda length zwraca rozmiar tablicy (max Index + 1) a nie maxymalny indeks.
czyli tak sie to robi
Prześlij komentarz
Możesz użyć niektórych tagów HTML, takich jak <b>, <i>, <u>, <a> Nie spamuj :)