Piszemy gadżet do Bloggera - część 1

Gadżety rozszerzają funkcjonalność naszych blogów. Dla platformy Blogger istnieje już kilkaset gotowych rozwiązań. Nic nie stoi na przeszkodzie, aby napisać samodzielnie taki gadżet. W kilku postach postaram się przybliżyć tematykę pisania gadżetów. Co będzie nam potrzebne:
  • edytor tekstu (z możliwością zapisu w formacie UTF-8, np. Windowsowy notatnik, Notepad++, czy PSPad),
  • serwer na którym zamieścimy nasz gadżet (np. Witryny Google, lub inny dowolny serwer z możliwością wgrywania plików),
  • podstawową znajomość HTML'a i JavaScriptu.
Struktura gadżetu

Gadżety do Bloggera tak samo jak pozostałe gadżety Googli składają się z plików XML (kod gadżetu, pliki językowe itd.). Podstawowa struktura gadżetu została przedstawiona poniżej.
<module>
 <moduleprefs title="Przykładowy gadżet"> 
  // pozostałe ustawienia
 <content type="html">
  <![CDATA[ 
   // zawartość HTML, JavaScript
  ]]>
 </content>
 </moduleprefs>
</module>
Pierwsza linia jest obowiązkowa i informuje o rozpoczęciu pliku w formacie XML. Pozostałe to tagi związane z gadżetami i tak:
  • tag <module> to oznaczenie, że plik będzie zawierał dane gadżetu,
  • tag <moduleprefs> zawiera dodatkowe informacje o gadżecie (autor, tytuł, lokalizacje, używane rozszerzenia itp.)
  • tag <content type="html"> informuje, że zawartością gadżetu będą polecenia HTML'a,
  • sekcja <![CDATA[ rozpoczyna właściwy kod HTML'a (czy JavaScript'u), który będzie wyświetlany przez gadżet,
  • ]]> zamknięcie sekcji CDATA,
  • </content> - tag zamykający,
  • </module> - tag zamykający.
Utwórzmy prosty gadżet wyświetlający napis "Nasz pierwszy gadżet!". Dodatkowo w sekcji <moduleprefs> zamieścimy informacje o autorze. Po wpisaniu kodu do edytora zapiszmy go pod nazwą PierwszyGadzet.xml
<module>
 <moduleprefs author="Devon" title="Przykładowy gadżet"> 
 <content type="html">
  <![CDATA[ 
   Nasz pierwszy gadżet!
  ]]>
 </content>
 </moduleprefs>
</module>
Pozostaje opublikowanie go w sieci. Możemy wykorzystać do tego celu Witryny Googli (więcej informacji o zakładaniu witryny znajdziesz tutaj). Po opublikowaniu (adres mojego gadżetu to: http://sites.google.com/site/kodatnikfiles/xml/PierwszyGadzet.xml), możemy sprawdzić jego działanie. Logujemy się do Bloggera, przechodzimy na Układ/Elementy strony, klikamy Dodaj gadżet, wybieramy Dodaj swoje własne i wpisujemy adres URL naszego gadżetu.



Klikamy Dodaj wg adresów URL i jeśli wszystko przebiegło poprawnie powinniśmy otrzymać takie okienko:



Dajemy Zapisz i nasz gadżet pojawi się na blogu.



W następnych odcinkach pokaże jak skorzystać z dodatkowych opcji, zmienić kolory gadżetu (zgodnie z szablonem bloga), dostać się do danych bloga oraz utworzyć lokalizacje językowe.

Wszystkie gadżety, które utworzymy i dodamy do Bloggera są "cache'owane". Oznacza to, że zmiany które wprowadzimy w kodzie nie będą widoczne od razu w gadżecie (Google "trzyma" wersję zbuforowaną mniej więcej 2 godziny). Jeżeli chcemy sprawdzić od razu zmiany to możemy, albo wyłączyć buforowanie (trochę pracy - modyfikacja szablonu), albo zapisać gadżet pod inną nazwą na serwerze (np. DrugiGadzet.xml) i dodać go od nowa do naszego bloga.

Lista powiązana - własna implementacja

Lista powiązana (ang. linked list) to struktura dynamiczna, której każdy element tak zwany węzeł (ang. node) posiada określoną wartość (lub wartości) oraz referencję do kolejnego węzła. Chcemy napisać prostą listę przechowującą wartości typu String (łańcuchy tekstowe). Pierwszą czynnością jest napisanie odpowiedniej klasy, na podstawie której będziemy tworzyć węzły.

Wieże Hanoi

Wieże Hanoi to problem polegający na przełożeniu z jednego słupka, na drugi, dysków o różnej średnicy. Przy przekładaniu można posługiwać się dodatkowym słupkiem stanowiącym bufor. Nie można kłaść dysku o większej średnicy na dysk o mniejszej średnicy, ani przekładać więcej niż jednego dysku jednocześnie. Chcemy napisać aplikację, która zasymuluje nam kolejne kroki potrzebne do przełożenia dysków. Zastosujemy algorytm rekurencyjny.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Wieże Hanoi - rozwiązanie rekurencyjne
 * @author kodatnik.blogspot.com
 */
public class WiezeHanoi {
 
 // Rekurencyjna metoda przekładająca dyski o parametrach
 // dyski - liczba dysków
 // skad - oznaczenie słupka początkowego
 // dokad - oznaczenie słupka docelowego
 // bufor - oznaczenie słupka pomocniczego
 public static void hanoi(int dyski, char skad, char dokad, char bufor) {
  // jeśli są dyski
  if (dyski > 0 ) {
   // przenieś (rekurencyjnie) n-1 dysków ze słupka A na słupek B posługując się słupkiem C
   hanoi(dyski - 1, skad, bufor, dokad);
   // wyświetl przeniesienie dysku
   System.out.println(skad + " > " + dokad);
   // przenieś (rekurencyjnie) n-1 dysków ze słupka B na słupek C posługując się słupkiem A
   hanoi(dyski - 1, bufor, dokad, skad);
  }
 } 

 public static void main(String args[]) {
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Ile dysków chcesz przełożyć: " );

  // pobieramy od użytkownika liczbę dysków
  int n = sc.nextInt();     
     
  // wywołujemy metodę wyświetlającą kolejne przełożenia dysków
  // ze słupka A na słupek C korzystając ze słupka B
  hanoi(n , 'A', 'C', 'B');     
 }
}
Uruchomiona aplikacja:
Ile dysków chcesz przełożyć: 4
A > B
A > C
B > C
A > B
C > A
C > B
A > B
A > C
B > C
B > A
C > A
B > C
A > B
A > C
B > C

Problem Józefa Flawiusza

Józef Flawiusz podczas wojny żydowsko-rzymskiej wraz 40 towarzyszami został otoczony przez Rzymian. Nie chcąc się poddać postanowili popełnić samobójstwo. Ustawili się w kręgu i co trzecia osoba odbierała sobie życie. Na końcu pozostał przy życiu przyjaciel Flawiusza oraz on sam. Oddali się w ręce wroga. Chcemy napisać aplikację, która zasymuluje nam, w jakiej kolejności ginęli żołnierze oraz, na której pozycji w kręgu ustawił się Flawiusz wraz ze swoim przyjacielem. Do rozwiązania tego problemu wykorzystamy przedstawioną wcześniej klasę Kolejka (Kolejka - implementacja tablicowa).
/**
 * Problem Józefa Flawiusza
 * @author kodatnik.blogspot.com
 */
public class JozefFlawiusz {
    
 public static void main(String[] args) {
  // zmienna przechowuje liczbę żołnierzy (Flawiusz + 40)
  int zolnierze = 41;
  // zmienna określa co który będzie ginął
  int coKtory = 3;

  // tworzymy kolejkę o rozmiarze równych liczbie żołnierzy
  Kolejka k = new Kolejka(zolnierze);
  
  // dodajemy żołnierzy do kolejki (od 1 do 41)
  for (int i = 1; i <= zolnierze; i++)
   k.dodaj(i);
            
  // w pętli dopóki kolejka nie jest pusta
  while ( !k.czyPusta() ) {
   // przestawiamy dwóch żołnierzy z początku na koniec kolejki
   for (int i = 0; i < coKtory - 1; i++)
    k.dodaj(k.usun());

   // eliminujemy trzeciego (usuwamy go z kolejki)
   // i wyświetlamy jego numer ekranie
   System.out.print(k.usun() + " ");
  } 
  System.out.println();
 }
}
Uruchomiona aplikacja:
3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41
7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31
Jak widać na wynikach generowanych przez program, Józef Flawiusz wraz z przyjacielem ustawili się na pozycji 16 i 31.

Kolejka - implementacja tablicowa

Kolejka to struktura danych działająca w oparciu o zasadę FIFO (ang. First In First Out), pierwszy wchodzi, pierwszy wychodzi. Dostęp do kolejki jest możliwy z dwóch stron (początek i koniec). Podstawowe metody związane z kolejką to dodanie elementu do kolejki, na jej koniec (ang. enqueue), usunięcie elementu z kolejki, z jej początku (ang. dequeue), podgląd elementu znajdujacego się na początku (ang. peek). Dodatkowo w większości implementacji istnieje możliwość wyświetlenia zawartości kolejki jak i sprawdzenia czy kolejka jest pusta. Chcemy napisać w oparciu o tablicę prostą klasę Kolejka przechowującą liczby całkowite (dane typu int). Efektywne wykorzystanie tablicy jest możliwe poprzez zawijanie kolejki (dane trafiają na odpowiednie miejsce) . Uzyskanie odpowiednich indeksów w kolejce zawijanej osiągnięmy wykonując operacje modulo rozmiar tablicy dla zmiennych poczatek oraz koniec. Poniżej klasa wraz z przykładowym jej wykorzystaniem.
/**
 * Kolejka liczb całkowitych - implementacja tablicowa
 * @author kodatnik.blogspot.com
 */
public class Kolejka {
 // tablica przechowująca elementy kolejki
 private int[] wektor;
 // początek kolejki (indeks elementu znajdującego się na początku)
 private int poczatek;
 // koniec kolejki (indeks elementu znajdującego się na końcu)
 private int koniec;
 // liczba elementów kolejki (pole pomocnicze)
 private int rozmiarKolejki;
 
 // konstruktor domyślny (tworzy kolejkę 10 elementową)
 public Kolejka() {
  // wywołujemy konstruktor z parametrem int (czyli ten poniżej)
  this(10);
 }
                 
 // konstruktor jednoparametrowy
 public Kolejka(int rozmiar) {
  // tworzymy tablicę o rozmiarze przekazanym jako parametr wywołania
  wektor = new int[rozmiar];
  // ustawiamy początkowe wartości pól (można to pominąć, domyślnie pola będą miały wartość zero)
  poczatek = 0;
  koniec = 0;
  rozmiarKolejki = 0;
 }
 
 // metoda dodaje element do kolejki
 public void dodaj(int liczba) {
  // wpisujemy na koniec kolejki element 
  // (operacja modulo da nam odpowiedni indeks tablicy)
  wektor[koniec % wektor.length] = liczba;
  // zwiększamy indeks końca oraz rozmiar kolejki
  koniec++;
  rozmiarKolejki++;
 }
 
 // metoda usuwa element z kolejki
 public int usun() {
  // pobieramy element z początku kolejki
  // (operacja modulo da nam odpowiedni indeks tablicy)  
  int temp  = wektor[ poczatek % wektor.length];
  // zwiększamy indeks początku kolejki
  poczatek++;
  // zmniejszamy rozmiar kolejki
  rozmiarKolejki--;
  // zwracamy usunięty element
  return temp;
 } 

 // metoda sprawdza czy kolejka jest pusta
 public boolean czyPusta() {
  // zwracamy prawdę lub fałsz
  return (rozmiarKolejki == 0);
 }

 // metoda sprawdza czy kolejka jest pełna
 public boolean czyPelna() {
  // zwracamy prawdę lub fałsz
  return (rozmiarKolejki == wektor.length);
 } 

 // metoda "podgląda" co jest na początku kolejki
 public int zobacz() {
  // zwracamy element z początku (nie modyfikujemy pozostałych zmiennych)
  return wektor[poczatek % wektor.length];
 } 

 // metoda zwraca rozmiar kolejki (liczbę elementów w kolejce) 
 public int rozmiar() {
  return rozmiarKolejki;
 } 
 
 // metoda wyświetla wszystkie elementy w kolejce 
 public void wyswietl(){
  // w pętli od początku do rozmiaru kolejki
  // (również wykorzystujemy modulo)
  for (int i = poczatek % wektor.length; i < poczatek % wektor.length + rozmiarKolejki; i++) 
   // wyświetlamy poszczególne elementy
   System.out.print (wektor[ i % wektor.length] + " ");
  System.out.println ();
 }
}
/**
 * Test kolejki liczb całkowitych
 * @author kodatnik.blogspot.com
 */
public class TestKolejki {

 public static void main(String args[]) {
    
  // zakładamy nową kolejkę o rozmiarze 20
  Kolejka k = new Kolejka(20);
     
  // dodajemy elementy do kolejki
  k.dodaj(12);
  k.dodaj(8);
  k.dodaj(39);
     
  // wyświetlamy zawartość kolejki
  k.wyswietl();
 
  // wyświetlamy element znajdujący się na początku (bez jego usuwania)
  System.out.println(k.zobacz());
     
  // usuwamy element z kolejki
  k.usun();     
      
  // wyświetlamy zawartość kolejki
  k.wyswietl();     
 }
}
Uruchomiona aplikacja:
12 8 39 
12
8 39 
Przedstawiona kolejka jest statyczna, jej 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 kolejki list powiązanych (struktura dynamiczna) oraz wykorzystanie typów generycznych (możliwość tworzenia kolejek przechowujących dowolny typ danych).
Kolejki wykorzystywane są w algorytmice, w programach komputerowych (np. kolejka plików w Winampie), systemach operacyjnych (np. kolejka wydruku).

Sprawdzanie poprawności nawiasów

Do sprawdzenia poprawności umiejscowienia nawiasów w wyrażeniu posłużymy się przedstawioną wcześniej klasą Stos (Stos - implementacja tablicowa). Sam algorytm jest stosunkowo prosty. Bierzemy element wyrażenia, jeśli jest to nawias otwierający odkładamy go na stos, jeśli nawias zamykający ściągamy ze stosu element i porównujemy czy razem stanowią parę, jeśli tak idziemy dalej, jeśli nie kończymy działanie algorytmu. Znaki nie będące nawiasami ignorujemy. Wyrażenie jest poprawne pod względem nawiasów, jeśli po przejściu przez wszystkie elementy stos będzie pusty. Poniżej krótka aplikacja sprawdzająca pobrane od użytkownika wyrażenie. Obsługiwane są nawiasy okrągłe, kwadratowe oraz klamrowe.
// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Sprawdzanie poprawności nawiasów 
 * Wykorzystujemy utworzoną wcześniej klasę Stos
 *
 * @author kodatnik.blogspot.com
 */
public class PoprawnoscNawiasow {
 
 // metoda sprawdza czy nawiasy w przekazanym jako parametr wyrażeniu są poprawne
 // obsługiwane są nawiasy okrągłe, kwadratowe i klamrowe
 // zwraca true dla poprawnych i false dla niepoprawnych
 public static boolean czyPoprawne(String wyrazenie) {
   
  // dwie tablice przechowujące nawiasy otwierające i zamykające
  char[] otwierajace  = {'(', '[', '{'};
  char[] zamykajace   = {')', ']', '}'};
     
  // tworzymy stos o rozmiarze naszego wyrażenia
  Stos stos = new Stos(wyrazenie.length());
        
  // pętla dla każdego znaku znajdującego się w wyrażeniu    
  for (int i = 0; i < wyrazenie.length(); i++) {
   
   // jeżeli znak jest nawiasem otwierającym odkładamy go na stos
   for (int j = 0; j < otwierajace.length; j++ ){
    if ( wyrazenie.charAt(i) == otwierajace[j]) stos.push((int) otwierajace[j]);
   }
         
   // jeżeli znak jest nawiasem zamykającym porównujemy go z wartością ze stosu
   for (int j = 0; j < zamykajace.length; j++ ){
    if ( wyrazenie.charAt(i) == zamykajace[j]) {
     // jeśli stos jest pusty zwracamy fałsz
     if (stos.czyPusty()) return false;
     // jeśli nawiasy nie są tego samego typu zwracamy fałsz
     if (((char) stos.pop()) != otwierajace[j]) return false;
    } 
   }         

   // ignorujemy znaki, które nie są nawiasami

   }
  // zwracamy true albo false (stos pusty - wszystkie nawiasy są poprawne)
  return stos.czyPusty();
 }
 
 public static void main(String[] args) {
        
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj wyrażenie z nawiasami: ");
 
  // pobieramy od użytkownika wyrażenie z nawiasami
  String wyrazenie = sc.nextLine();
        
  // wyświetlamy informacje o poprawności wyrażenia z nawiasami
  System.out.println("Wyrażenie jest " + (czyPoprawne(wyrazenie) ? "poprawne." : "niepoprawne."));
 }
}
Przykładowe uruchomienia aplikacji:
Podaj wyrażenie z nawiasami: (a[b{c}d]e)
Wyrażenie jest poprawne.
Podaj wyrażenie z nawiasami: [a(b{c})
Wyrażenie jest niepoprawne.
Podaj wyrażenie z nawiasami: (([a]b)}
Wyrażenie jest niepoprawne.
Modyfikując tablicę z nawiasami możemy sprawdzać poprawność wyrażeń z dowolnymi znakami otwierającymi i zamykającymi.

Podział łańcucha na części

Pisząc aplikacje spotykamy się z problemem podziału łańcucha tekstowego na części (np. import danych w formacie CSV, rozbicie zdania na wyrazy itd.). Idealną klasą, która pomoże nam podzielić łańcuch tekstowy jest klasa StringTokenizer z pakietu java.util. Jej zadaniem jest podział tekstu na części (tak zwane tokeny) na podstawie znaków rozdzielających (ang. delimiter). Klasa posiada trzy konstruktory, oraz kilka metod umożliwiających pobranie podzielonych już tokenów. Poniższy przykład wykorzystuje konstruktor StringTokenizer(String), dzielący łańcuchy tekstowe na podstawie znaku spacji, tabulacji, nowego wiersza i powrotu karetki. Znaki rozdzielające nie są traktowane jako tokeny.
// wykorzystujemy klasę Scanner oraz StringTokenizer z pakietu java.util
import java.util.*;

/**
 * Podział łańcucha tekstowego na części
 * @author kodatnik.blogspot.com 
 */ 
public class PodzialLancucha {
  
 public static void main (String[] args) {
   
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj łańcuch: ");
   
  // pobieramy od użytkownika łańcuch tekstowy
  String lancuch = sc.nextLine();
   
  // tworzymy nowy obiekt klasy StringTokenizer
  StringTokenizer st = new StringTokenizer(lancuch);
   
  // metoda countTokens() zwróci nam liczbę tokenów (części)
  int liczbaTokenow = st.countTokens(); 
   
  // wyświetlamy na ekranie informacje o liczbie tokenów
  System.out.println("Liczba tokenów w łańcuchu: " + liczbaTokenow);
    
  // w pętli dopóki są jeszcze tokeny (metoda hasMoreTokens())
  while(st.hasMoreTokens()) {
   //wyświetlamy je na ekranie (metoda nextToken())
   System.out.println(st.nextToken());
  }
 }
}
Uruchomiona aplikacja:
Podaj łańcuch: Nie programuj w wigilię... bug się rodzi
Liczba tokenów w łańcuchu: 7
Nie
programuj
w
wigilię...
bug
się
rodzi
Drugi konstruktor StringTokenizer(String, String) umożliwia nam określenie własnych znaków rozdzielających. Możemy na przykład użyć przecinka czy też średnika do podziału linii z pliku CSV. Znaki rozdzielające również nie są traktowane jako tokeny.
StringTokenizer st = new StringTokenizer(lancuch, ";");
Wynik działania programu:
Podaj łańcuch: Kasia;Fikas;ul. Marsowa 12;Katowice
Liczba tokenów w łańcuchu: 4
Kasia
Fikas
ul. Marsowa 12
Katowice
Ostatnie wersja konstruktora StringTokenizer(String, String, boolean) pozwala nam określić czy znaki rozdzielające mają być traktowane jako tokeny. W poniższym przykładzie ustawiamy własne znaki rozdzielające # oraz %, które będą również tokenami.
StringTokenizer st = new StringTokenizer(lancuch, "#%", true);
Wynik działania programu:
Podaj łańcuch: 123#17.5#8%Marek%Kowalski
Liczba tokenów w łańcuchu: 9
123
#
17.5
#
8
%
Marek
%
Kowalski

Stos - implementacja tablicowa

Stos to struktura danych działająca w oparciu o zasadę LIFO (ang. Last In First Out), ostatni wchodzi pierwszy wychodzi. Dostęp do stosu możliwy jest tylko z jednego miejsca tzw. wierzchołka (ang. top). Podstawowe metody związane ze stosem to odłożenie elementu na stos (ang. push), ściągnięcie elementu ze stosu (ang. pop), podgląd elementu znajdującego się na szczycie stosu (ang. peek). Dodatkowo w większości implementacji istnieje możliwość wyświetlenia zawartości stosu jak i sprawdzenia czy stos jest pusty. Chcemy napisać, w oparciu o tablicę, prostą klasę Stos przechowującą liczby całkowite (dane typu int). Poniżej klasa wraz z jej przykładowym wykorzystaniem.
/**
 * 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 8
Powyż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).

Liczby pseudolosowe

Pisząc programy w Javie często potrzebujemy wylosować jakąś wartość. Standardowo mamy dwie możliwości wygenerowania liczby pseudolosowej. Pierwsza, to skorzystanie z klasy Random dostępnej w pakiecie java.util. Klasa ta zawiera szereg przydatnych metod generujących liczby losowe. Wadą tego rozwiązania jest konieczność utworzenia nowego obiektu.
// wykorzystujemy klasę Random z pakietu java.util
import java.util.*;

/**
 * Generowanie liczb pseudolosowych
 * @author kodatnik.blogspot.com 
 */ 
public class LiczbyPseudolosowe {
  
 public static void main (String[] args) {
   
  // tworzymy obiekt klasy Random
  Random rand = new Random();
   
  // metoda nextInt() zwraca liczbę całkowitą (pełny zakres)
  int liczbaCalkowita = rand.nextInt();
      
  // metoda nextInt(int n) zwraca liczbę z zakresu >= 0 do < n-1
  int liczbaCalkowitaZakres = rand.nextInt(10);
   
  // metoda nextDouble() zwraca liczbę rzeczywistą z zakresu >= 0.0 do < 1.0
  double liczbaRzeczywista = rand.nextDouble();   
   
  System.out.println ("Wylosowana liczba całkowita: " + liczbaCalkowita);
  System.out.println ("Wylosowana liczba całkowita z zakresu <0, 10): " + liczbaCalkowitaZakres);   
  System.out.println ("Wylosowana liczba rzeczywista z zakresu <0.0, 1.0): " + liczbaRzeczywista);       
 }
}
Uruchomiona aplikacja:
Wylosowana liczba całkowita: 1133804662
Wylosowana liczba całkowita z zakresu <0, 10): 0
Wylosowana liczba rzeczywista z zakresu <0.0, 1.0): 0.06242174947663559
Drugi sposób to wykorzystanie statycznej metody random() dostępnej w klasie Math. Generuje ona pseudolosową liczbę rzeczywistą z zakresu od 0.0 włącznie do 1.0 wyłącznie. Tak otrzymaną liczbę zazwyczaj musimy przemnożyć przez odpowiednią wartość oraz dokonać rzutowania do pożądanego typu. Na przykład, gdy chcemy uzyskać liczbę z zakresu od 1 do 10, musimy posłużyć się takim kodem:
int liczbaLosowa = (int) (Math.random() * 10 + 1);
Często potrzebujemy liczbę z zadanego zakresu. Poniższa metoda losuj(int, int) generuje liczby losowe całkowite z zakresu przekazanego jako parametry jej wywołania.
/**
 * Generowanie liczb pseudolosowych
 * @author kodatnik.blogspot.com 
 */ 
public class LiczbyPseudolosowe {
  
 // metoda zwraca liczbę całkowitą z zakresu >= min do < max
 public static int losuj(int min, int max) {
  return (int) (Math.random() * (max - min) + min);
 }

 public static void main (String[] args) {
   
  // Losujemy 10 liczb całkowitych z zakresu od 20 do 40
  for (int i = 0; i < 10; i++) 
   System.out.print(losuj(20, 40) + " ");
 }
}
Uruchomiona aplikacja:
25 34 20 22 23 22 36 26 30 34

Wyszukiwanie maksymalnego elementu tablicy

Znalezienie maksymalnego elementu tablicy polega na przypisaniu do zmiennej wartości pierwszego elementu i przejściu przez pozostałe elementy tablicy. W przypadku gdy znajdziemy większy element, staje się on elementem największym. Poniżej prosta metoda znajdzMax(), która dla przekazanej jako parametr tablicy liczb całkowitych zwraca wartość maksymalną.
/**
 * Wyszukiwanie maksymalnego elementu w tablicy
 * @author kodatnik.blogspot.com 
 */ 
public class WyszukiwanieMaksimum {
 
 // metoda zwraca największy element z tablicy przekazanej jako parametr
 public static int znajdzMax(int[] wejscie) {
  
  // przypisujemy zmiennej max wartość pierwszego elementu
  int max = wejscie[0];   
  
  // sprawdzamy pozostałe elementy tablicy
  for (int i = 1; i < wejscie.length; i++) {
   // jeżeli element jest większy od dotychczasowego maksimum to on staje się maksimum
   if (wejscie[i] > max) 
    max = wejscie[i];   
  }
  
  // zwracamy wartość maksymalną
  return max;
 }
 
 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę na ekranie
  pokazTablice(tablica);  
  
  System.out.println ("Największy element tablicy to: " + znajdzMax(tablica));
 }
}
Uruchomiona aplikacja:
4 6 1 2 3 8 7 9 5 
Największy element tablicy to: 9
Często zamiast wartości potrzebujemy znaleźć indeks największego elementu. W przykładowym kodzie metody znajdzMax() zamiast zapamiętywać wartość największego elementu musielibyśmy zapisać indeks, na którym on się znajduje. Zmodyfikowana wersja metody poniżej.
// metoda zwraca indeks największego element z tablicy przekazanej jako parametr
 public static int znajdzMax(int[] wejscie) {
  
  // przypisujemy zmiennej max indeks pierwszego elementu
  int max = 0;   
  
  // sprawdzamy pozostałe elementy tablicy
  for (int i = 1; i < wejscie.length; i++) {
   // jeżeli element jest większy od dotychczasowego maksimum to zapamiętujemy jego indeks
   if (wejscie[i] > wejscie[max]) 
    max = i;   
  }
  
  // zwracamy indeks elementu największego
  return max;
 } 
Uruchomiona aplikacja:
4 6 1 2 3 8 7 9 5 
Indeks największego elementu tablicy to: 7
Dokładnie tak samo można znaleźć element najmniejszy. Wystarczy zmodyfikować warunek porównujący elementy ze sobą.

Popularne posty