Pilak eta ilarak - OCW€¦ · Datu egitura lineala non: –Atzipena, hasieran txertatutako elementuari murriztua dago (elementu zaharrena) –Elementuak mutur batetik txertatzen

1

Pilak eta ilarak

Datu egiturakDatu egiturak

2

Aurkibidea

• Pilak– Zer dira?– Ezaugarriak– Metodo nagusiak– Adibideak

• Inplementazio adibideak– Array-etan oinarrituta– Zerrendetan oinarrituta

• Ilarak– Zer dira?– Ezaugarriak– Metodo nagusiak– Adibideak

• Inplementazio adibideak– Array-etan oinarrituta– Zerrendetan oinarrituta

3

Pilak


4

PilakZer dira?. Ezaugarriak

• Datu egitura lineala non:– Txertatu den elementu berriena atzitu daiteke

soilik (top edo gailur)– Objektuak mutur batetik txertatzen eta

ezabatzen dira LIFO (Last In First Out) irizpidea jarraituz.

• Egokiak dira:– Azken elementua atzitu behar dugunenan

soilik. – Zerrenda bat alderantzikatu nahi dugunean.

5

PilakAdibidea

6

PilakMetodo nagusiak

• Mutur batetik txertatu (pilaratu): push(x)• Mutur berdinetik atera (despilatu): pop()

Eskuragarri dagoen elementu bakarra azken txertatua da (gailur): top

toppush pop

7

PilakMetodo nagusiak eta metodo laguntzaileak

Pilaren gailurrean dagoen elementua ezabatzen da posizio horretan zegoen elementua itzuliz

T pop()Pilaren gailurrean elementu bat txertatzen davoid push(T elem)EsanahiaMetodo nagusiak

Gailurrean dagoen elementua itzultzen du gailurretik ezabatu gabe.

T top()True pila hutsa bada eta false kontrako kasuanboolean isEmpty()Pilaren tamaina itzultzen duint size()EsanahiaMetodo laguntzaileak

8

PilakAdibideak

• Pilak konpiladoretan:– Sinboloen oreka konprobatzeko– Metodoen deialdiak gordetzeko: Errekurtsioa

• Deialdi bakoitzean gordetzen da:– Metodoen aldagai lokalak (kontextu)– Deialdia egin den lerroa

9

Pilak: metodoen deialdiak gordetzeko1 public class Faktoriala{2 public static void main(String args[]){3 int param = Integer.parseInt(args[0]);4 long emaitza = fakt(param);5 System.out.println( args[0] +"! = " + emaitza);6 }// main amaiera7 public static long fakt(int n){8 if(n

10

PilakAdibide 1: parententesi konprobaketa

• Ondo:– – ()– (()(()))

• Gaizki:– )(– (()– ())

❚ Simboloen oreka konprobatzeko erregelak:❙ Oinarrizkoa: ()❙ Sekuentzia: ()()❙ Habiratuak: (())

11

PilakAdibide 1: Parentesi konprobaketa

• Erregelak:– aurkitzen dugun bakoitzen, pilan

txertatzen dugu.– aurkitzen dugun bakoitzen, gailurrean

dagoen ateratzen dugu – Parentesi katea zuzena da, kate guztia

korritu dugunen pila hutsa badago.

()

(

12

PilakAdibide: Parentesi konprobaketa (()(()())())

(()(()())())

Erregelak:-Parentesi irikia: pilaratu-Parentesi itxia: despilatu

13

(()(()())())

Zuzena: textu guztia korritu dugu eta pila hutsa dago

PilakAdibide 1: Parentesi konprobaketa (()(()())())

14

Pila interfaza

public interface Stack { public int size(); public boolean isEmpty(); public void push(T o); public T pop(); public T top();}

15

Pilak:Inplementazio desberdinak interfaze batentzat

ArrayStack

Stack

LinkedStack

16

Pilak:Array-etan oinarritutako inplementazioa

Array S0 1 2 N-13 4 5

1

top

2

top

3

top

4

top

5

toptop

top = top +1; //top etiketa posizio bat mugitus[top]= o; //top posizio berrian elementua txertatzen da

S array baten bidez inplementatutako pila batean o objektu bat txertatu nahi dugu

17

public class ArrayStack implements Stack{ public static final int CAP=1000; private int capacity; private T s[]; private int top=-1; public ArrayStack(){this(CAP);} public ArrayStack(int cap){capacity=cap; s=new T[capacity]; }}

Pilak:Array-etan oinarritutako inplementazioa

18

public int size(){return (top+1);}

public boolean isEmpty(){return (top

19

public void push(T o) {if (size()

20

Madrid Miami Munich

Pilak:Zerrenda estekatuetan oinarritutako inplementazioa

21

Pilak:Zerrenda estekatuetan oinarritutako inplementazioa

public class LinkedStack implements Stack{ private LinkedList zerrenda;

public LinkedStack() { zerrenda=new LinkedList();}

public int size() { return zerrenda.size()}

public boolean isEmpty() {return(size()==0);}

22Moscú

Madrid Miami Munich

top

Pilak:Zerrenda estekatuetan oinarritutako inplementazioa txertaketa: push()

public void push(T e) { zerrenda.insertFirst(e);}

23

public T top() { if (isEmpty()) return null; else { zerrenda.goFirst() return zerrenda.getActual(); }}

Pilak:Zerrenda estekatuetan oinarritutako inplementazioa atzipena: top()

24

public T pop(){ T temp; if (isEmpty()) return null; else {zerrenda.goFirst(); temp=zerrenda.getActual(); zerrenda.removeFirst(); return temp; }}

Pilak:Zerrenda estekatuetan oinarritutako inplementazioa ezabaketa: pop()

Madrid Miami MúnichMoscú

top

25

Ilarak


26

IlarakZer dira?. Ezaugarriak

Datu egitura lineala non:– Atzipena, hasieran txertatutako elementuari

murriztua dago (elementu zaharrena)– Elementuak mutur batetik txertatzen dira eta

beste muturretik ateratzen dira FIFO (First In First Out) irizpidea jarraituz.

27

Ilarak:Adibideak

• Autobuseko ilara– Lehenengoa sartzen da, lehenengoa

etorri dena. – Ilaran denbora gehiago daramana

• Inpresorako ilara– Azken bidalitako fitxategia, azkenekoa

ateratzen dena izango da.

28

IlarakMetodo nagusiak

• Mutur batetik txertatu (ilaratu): enqueue(x)• Beste muturretik atera (desilaratu): dequeue()

Eskuragarri dago, Ilararen lehen elementua (front).

fron

t

dequeue enqueue

rear

29

IlarakMetodo nagusiak eta metodo laguntzaileak

Ilararen hasierako elementua ezabatzen du eta bere edukia itzultzen du . Hutsa bada, null bueltatuko du.

T dequeue()

Elementu bat txertatzen du ilararen bukaeran. Ilara beteta badago ez du ezer egiten.

void enqueue(T elem)

EsanahiaMetodo nagusiak

Ilararen hasieran dagoen elementua itzultzen du ilaratik atera gabe

T front()true, ilara hutsa bada eta false kontrako kasuanboolean isEmpty()Ilararen tamaina itzultzen duint size()EsanahiaMetodo laguntzaileak

30

IlarakIlararen interfazea

public interface Queue { public int size(); public boolean isEmpty(); public void enqueue(T o) ; public T dequeue() ; public T front() ;}

31

Ilarak:Inplementazio desberdinak interfaze batentzat

ArrayQueue

Queue

LinkedQueue

32

Ilarak:Zerrenda estekatuetan oinarritutako inplementazioa

public class LinkedQueue implements Queue { private LinkedList zerrenda;

public LinkedQueue() { zerrenda=new LinkedList();}

public int size() { return zerrenda.size()}

public boolean isEmpty() {return(size()==0);}

}

33

Ilarak:Zerrenda estekatuetan oinarritutako inplementazioa Txertaketa: enqueue

MoscúMadrid Miami Múnich

top bottom

public void enqueue(T e) { zerrenda.insertLast(e);}

34

Ilarak:Zerrenda estekatuetan oinarritutako inplementazioa Ezabaketa: dequeue

public T dequeue(){ T temp; if (isEmpty()) return null; else { zerrenda.goFirst(); temp=zerrenda.getActual(); zerrenda.removeFirst(); return temp; }}

35

Ilarak:Zerrenda estekatuetan oinarritutako inplementazioa Hasierako elementua: front

public T front(){ if (isEmpty()) return null; else { zerrenda.goFirst(); return(zerrenda.getActual()); }}

36

Interfaze bat Inplementazio desberdin

null

nullnull

null

nullnull

null

nullnull

LinkedList

DoubleLinkedList

Pila Ilarapush popenqueuedequeue

Vector

Array

Egitura

InplementazioaZer? Nola?

Beste egitura linealak

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36

Documents

Pilak eta ilarak - OCW€¦ · Datu egitura lineala non: –Atzipena, hasieran txertatutako elementuari murriztua dago (elementu zaharrena) –Elementuak mutur batetik txertatzen