Java Data Structure

[marko euroband]

Drusto imam problem da konceptualno razumem list, linked lists, stacks, queues...

znam sta svako od njih podrzava i na koju foru memorija funkcionise ali... recimo imamo klasican array, kad taj array stavimo u recimo lists ili neku drugu strukturu, STA SE ONDA DESAVA. Profesor mi je dao neke kodove ali oni su dosta teski za moj nivo i ne razumem kako nesto sto je vec lista podataka( array) ubacujemo u List? sta dobijamo time, vise funkcija, brzi odziv, bolju pretragu... evo primer-a..

public class Stack<E> {
private Object data[]; // ovde u Stack class pravimo array, kako sad taj array funkcionise u Stack-u?? ostalo su samo methods, ovo mi je bitno da razumem
private int top;

public Stack() {
data = new Object[100];
top = 0;
}

public void push(E myButtons) {
if (top > data.length)
throw Fit(); // comment this out to compile
else
data[top++] = myButtons;
}

public E pop() {
if (top < 1)
throw Fit();
else {
return ((E)(data[--top]));
}
}

public E top() {
if (top < 1)
throw Fit();
else {
return ((E)(data[top-1]));
}
}
}

 

[WebWolf]

Nisi razumeo bas kako valja. Ovo sto si ti stavio je klasa Stack. Tebi je stek implementiran uz pomoc niza, taj niz jeste stek, a ne niz u steku. Funkcionise tako sto kada ubacujes elemente u niz, ubacujes ih na prvo prazno mesto u nizu (sto bi se reklo, ako imas pet elemenata, ubacujes ga na sesto), a citas taj niz tako sto citas od poslednjeg unesenog (znaci sesti, pa peti, pa cetvrti...), pa do prvog i samo tako smes da radis. Shvati to kao niz sa ogranicenjima u nacinu citanja i upisa, ako ti je lakse 🙂 . Sam niz kao niz je ni po cemu poseban. Niz je enkapsuliran u tu klasu tako da mu mozes pristupati samo uz pomoc te dve funkcije Push() i Pop().

x <- 
x
x
x

Neka ovo bude neki niz, koji je prazan i ova strelica ti pokazuje prvo prazno mesto. Pozoves push(5). Upises 5 na to prvo prazno mesto i pomeris strelicu dalje

5
x <- 
x
x

Push(3)
5
3
x <-
x

Pop() //funcija vraca trojku

5
3 <-
x
x

Sada kao sto vidis, ovo mesto gde pokazuje strelica nije prazno (nedefinisano) tu je trojka, ali pri narednom upisu ona ce biti prebrisana

To je cela filozofija, upis na kraj niza i citanje sa istog. Strelica je samo virtuelna, u tvom slucaju to je promenjiva top koja pamti broj na kome se nalazis, njegovim povecanjem ili smanjenjem ti setas strelicu. Nadam se da je jasnije, bas ovako rade ove metode klase koje si napisao 🙂
Evo ti jedan lep applet, da ti bude jasnije.
http://www.cosc.canterbury.ac.nz/mukundan/dsal/StackAppl.html

Na slicne nacine mozes implementirati i Linked List. Stek takodje mozes implementirati i uz pomoc Linked List 😀 .

 

[marko euroband]

"Tebi je stek implementiran uz pomoc niza, taj niz jeste stek, a ne niz u steku. " mislim da je ovo deo koji meni stvarao zabunu.. znam kako funkcionise pop,push,... i koristim to ali cekaj sad ovako... to su properties od Stack klase, a sta je sa array properties-ma? ako sam te razumeo, ti hoces da kazes da mi recimo imamo array velicine 10 i sad kad trebamo da stavimo odredjene elemente na svaki index, mi korisitimo push, pull... tj, funkcije Stack-a da "napunimo" taj array(niz) ? Jel sam te dobro razumeo?

ako je tako, to onda znaci da mi u stvari koristimo " niz" samo kao neki prostor koji smo naznacili(ogradili) ali u njega stavljamo i kontrolisemo podatke u zavisnosti od DATA STRUCTURE-e koje koristimo. U ovom slucaju STACK...

 

[WebWolf]

Da, bas tako. Osobine niza neces (i ne treba) da vidis van klase.

 

[marko euroband]

Ok, to mi je logicno e sad... Kad imamo recimo linked lists ili double lists... Kad ih implementiramo sa Array-em, da li onda npr, memorija double lista, koja ima next i previous pored data place, zauzima jedan index array-a? jel sam na pravom putu?? =/

 

[ivan90BG]

Linked listu i double linked listu ne možeš da implementiraš uz pomoć niza, jer da bi ona radila kako nalaže specifikacija linked liste raspored u memoriji mora da bude drugačiji nego što je kod običnog niza. Ali zato recimo Stack može da se implementira preko niza ili preko Linked liste.

Zamisli ovako. Niz i Linked lista su ti dve osnovne kategorije koje ne možeš da implementiraš preko nečeg drugog. U Javi Linked listu možeš da implementiraš sam koristeći ono što java ima, a to su objekti. Niz u Javi ne može da se implementira. može samo da se koristi onaj koji je već dostupan u Javi (*** Java je takva)

 

[Nothingman]

Naravno da moze listu da implementira preko niza. Druga stvar je sto to nije efikasno za insertovanje.

 

[marko euroband]

Linked listu i double linked listu ne možeš da implementiraš uz pomoć niza, jer da bi ona radila kako nalaže specifikacija linked liste raspored u memoriji mora da bude drugačiji nego što je kod običnog niza. Ali zato recimo Stack može da se implementira preko niza ili preko Linked liste.

Zamisli ovako. Niz i Linked lista su ti dve osnovne kategorije koje ne možeš da implementiraš preko nečeg drugog. U Javi Linked listu možeš da implementiraš sam koristeći ono što java ima, a to su objekti. Niz u Javi ne može da se implementira. može samo da se koristi onaj koji je već dostupan u Javi (*** Java je takva)

Ovo mi je trebalo... sad je vec jasnije.. znaci u prvobitnoj prici odnos STACK/ARRAY je moguc zbog njihove uzajamne saradnje, e sad, linked list bi u tom slucaju menjao poziciju array-a a ne Stack-a kako sam ja mislio!!! Onda mi je jasno zasto recimo stack ne moze da se implementira za linked list ili double, jer njihov memorijski raspored je drugaciji i ne moze da radi sa recimo Stack or Queue... ok, odoh ja sad da ucim i prelistavam kodove, pa cu se javiti sa novim pitanjima... HVALA I MNOGO STE MI POMOGLI.

 

[Bahati [SiD]]

imas u jednoj "grupi" niz i listu, a u drugoj stack (LIFO buffer) i queue (FIFO buffer).

razlika izmedju niza i liste je sto u prvom elementi zauzimaju kontinualan memorijski prostor (elementi su jedan za drugim u memoriji, sto omogucava pointer aritmetiku), a lista moze da bude rastrkana po memoriji jer svaki element sadrzi vezu na sledeci. ili prethodni, ili oba, ili kod kruzne liste "poslednji" sadrzi vezu na prvi, itd...

LIFO i FIFO karakteristike su jasne iz njihovih naziva, a kako ce zaista biti implementirani zavisi od potreba.

dakle, poenta u prvoj grupi je kako su informacije smestene u memoriji sto implicira nacin manipulisanja, a poenta u drugoj grupi je nacin manipulacije, a smestanje zavisi od implementacije.

 

[Nothingman]

@Bahati [SiD]

Ili krace, ta "druga grupa" se zove interfejs, a "prva grupa" se zove implementacija 🙂

 

[Bahati [SiD]]

ne znam da se ti izrazi koriste na taj nacin u ovom kontekstu. mozda u javi? ono sto sam napisao je nacelno...

mada mi svakako ne zvuce odgovarajuce. 🙂

 

[Nothingman]

Nije vezano za jezik, svejedno da li je java, C ili nesto drugo u pitanju. Ako apstrahujemo dovoljno, interfejsom nazivamo servise koje nam neki entitet pruza, bez obzira na nacin na koji to radi. Zato kad kazemo da je neki entitet FIFO ili LIFO mi smo upravo oznacili kakve nam mogucnosti daje taj entitet. Klasicna crna kutija, ne znam kako radi, ali znamo sta radi. Ako pocnemo da se zanimamo kako nesto radi (npr. pocnemo da razmisljamo o rasporedu u memoriji) zasli smo duboko u implementaciju 🙂

 

[marko euroband]

Uh,ok jel ovo dobro sad?
STACKS, List and QUEUE se implentiraju koristeci (arrays, linked lists,dlist..

 

[WebWolf]

@Nothingman
Mislim da ti izrazi bas i ne leze kada su u pitanju strukture podataka, jer se one ne posmatraju kao klase i objekti vec bas kao strukture podataka. No, nebitno, bitno da se razumemo.

@marko
I stek mozes da implementiras uz pomoc niza ili listi.

 

[marko euroband]

Shvatio sam ti. Hvala na pomoci, jos me samo buni to sto lists nije u istoj grupi kao linked list i double(nadam se da sam u pravu?) zato sto list je nacin manipulisanja(citanje, brisanje..) a linked i double su nacin funkcionisanja memorije elemenata..

 

[Nothingman]

@Nothingman
Mislim da ti izrazi bas i ne leze kada su u pitanju strukture podataka, jer se one ne posmatraju kao klase i objekti vec bas kao strukture podataka. No, nebitno, bitno da se razumemo.

Pa i ne govorim o klasama i objektima, rekoh vec da klase ne moraju ni da postoje, mozes posmatrati nezavisno od jezika, ili u bilo kom jeziku, cak i asembleru. Strukture podataka i nisu nista drugo nego cista apstrakcija 🙂

Ali kao sto vec rece, razumemo se, to je najbitnije 🙂

 

[yooyo]

Svi tacno govrite samo razlicitim jezicima pa se ne razumete dovoljno. Klasika za programere 🙂
Ja bih to objasnio na sledeci nacin... Neku kolicinu podataka treba sacuvati u memoriji. U zavisnisti od toga kakve operacije i manipulacije nad tim podacima treba da radimo, treba ih smestiti u kontejnere. Postoji vise vrsta kontejnera i skoro svi imaju slican interface ali im se implementacije prilicno razlikuju. To su nizovi, redovi, stekovi, liste, double-linked liste, mape (hash), multimape, skupovi, ... Nacin implementacije ovih kontejnera nije tajna, ali programer nije u obavezi da zna svaki detalj. Bitno je da shvati razlike izmedju kontejnera i da izabere pravi ili cak da iskombinuje vise kontejnera.
Svaki od navedenih kontejnera moze da se implementira kao niz, ali to uopste nije pametno. Interface kontejnera je tu da sakrije implementaciju i servira trazene podatke, odnosno da ih cuva.