Stive si Cozi - Creare. Inserare. Stergere.

Stive si Cozi - Creare. Inserare. Stergere.

A. Stive

• O stiva permite accesul la un singur element: cel care a fost inserat ultimul.
• Daca eliminam un element, atunci putem avea acces la elementul de langa el si asa mai departe.
• Stiva este o structura de tip LIFO ( Last in First out).

Sa se creeze clasa CStiva care sa contina urmatoarele metode:

- inserare element in varf;

- afisare si eliminare element din varf ;

- afisare element din varf;

- verificare daca stiva este vida, respectiv daca este plina.

import java.io.*;

class CStiva

//inserare element in varful stivei

public void adauga(int elem)

//extrage element din varful stivei

public int sterge()

//citeste elementul din varful stivei

public int citeste()

//intoarce true daca stiva este vida

public boolean esteVida()

//intoarce true daca stiva este plina

public boolean estePlina()

class stivaAplicatie1

System.out.println();

}

Inversarea unui sir de caractere.

Initial se extrag caracterele, unul cate unul, din sirul de intrare si se introduc intr-o stiva. Apoi, se extrag caracterele din stiva si se afiseaza.

import java.io.*;

class CStiva

//inserare element in varful stivei

public void adauga(char elem)

//extrage element din varful stivei

public char sterge()

//citeste elementul din varful stivei

public char citeste()

//intoarce true daca stiva este vida

public boolean esteVida()

//intoarce true daca stiva este plina

public boolean estePlina()

class stivaAplicatie2

public static void main(String[] args) throws IOException

sir_out='';

while (!stiva.esteVida())

System.out.println();

System.out.println('Ati introdus sirul '+sir_in +'. ');

System.out.println( 'Sirul citit in ordine inversa este '+sir_out);

System.out.println();

}

Imperecherea caracterelor de delimitare.

Caracterele de delimitare considerate sunt si Fiecare delimitator de deschidere trebuie sa se imperecheze cu un delimitator de inchidere. De asemenea, delimitatorii de deschidere care apar mai tarziu in sirul de caractere se inchid inaintea celor care apar mai devreme.

Exemplu: a

Se citeste sirul de intrare caracter cu caracter, iar delimitatorii se introduc intr-o stiva. La citirea unui delimitator de inchidere din sirul de intrare, se extrage delimitatorul de deschidere din varful stivei si se verifica daca se imperechiaza. Daca delimitatorii nu sunt de acelasi tip atunci sirul de intrare este gresit. De asemenea, daca nu exista nici un delimitator de deschidere in stiva pentru a efectua imperechierea sau daca un delimitator de deschidere ramane desperechiat, rezulta ca sirul este eronat.

import java.io.*;

class CStiva

//inserare element in varful stivei

public void adauga(char elem)

//extrage element din varful stivei

public char sterge()

//citeste elementul din varful stivei

public char citeste()

//intoarce true daca stiva este vida

public boolean esteVida()

//intoarce true daca stiva este plina

public boolean estePlina()

class stivaAplicatie3

public static void main(String[] args) throws IOException

':

case ']':

case ')':

if (!stiva.esteVida())

')) || ((c=='[') &&

(ch!=']')) || ((c=='(') && (ch!=')')))

System.out.println('Eroare: '+ch+' la '+i);

}

else //stiva se goleste prematur

System.out.println('Stiva golita prematur. Eroare:

'+ch+' la '+i);

break;

default: //celelalte caractere sunt ignorate

break;

}

}

if (!stiva.esteVida())

System.out.println('Eroare: delimitator dezperechiat');

System.out.println();

}

B. Cozi

• O coada este o structura similara stivei.
• Primul element inserat este si primul care va fi sters.
• Coada este o structura de tip FIFO (First in First aut).
• Cozi circulare: pentru a evita situatia cand nu se mai pot insera elemente noi, desi coada nu este plina, ne putem intoarce catre inceputul tabloului.

Exemplu:

Inserez intr-o coada de dimensiune 5 elementele 10, 20, 30 si 40. Apoi sterg primele 3 elemente (10, 20 si 30). Coada nu este plina, dar la sfarsit am o singura pozitie disponibila. Inserez alte 4 elemente: 50,60,70 si 80.

primul =

ultimul = 3;

Spate

Fata

primul=3;

ultimul=3;

Spate

Fata

primul=3;

ultimul=2;

Spate

Fata

• Cozi cu prioritati: elementele sunt ordonate dupa valoarea unei chei, astfel incat elementul cu cheia minima se afla intotdeauna in fata. Elementele sunt inserate in pozitiile corespunzatoare, astfel incat ordinea sa fie pastrata.

Sa se creeze clasa CCoada (coada circulara) care sa contina urmatoarele metode:

- inserare element la sfarsitul cozii;

- afisare si eliminare element de la inceputul cozii;

- afisare primul element din coada;

- verificare cand coada este vida, respectiv cand este plina.

import java.io.*;

class CCoada

//inserare element la sfarsitul (in spatele) cozii

public void adauga(int elem)

//sterge elementul din fata cozii

public int sterge()

//citeste primul element din coada

public int citeste()

//intoarce true cand coada este vida

public boolean esteVida()

//intoarce true cand coada este plina

public boolean estePlina()

//nr de elemente din coada

public int dimensiune()

class CoadaAplicatie1

System.out.println();

System.out.println('Coada are '+coada.dimensiune()+' elemente');

}

Sa se creeze clasa CCoadaP (coada cu prioritati) care sa contina urmatoarele metode:

- inserare element;

- afisare si eliminare elementul minim;

- afisare elementul minim din coada;

- verificare cand coada este vida, respectiv cand este plina.

import java.io.*;

class CCoadaP

//inserare element

public void adauga(int elem)

VCoada[i+1]=elem;

nr_elem++;

}

}

//sterge elementul minim

public int sterge()

//intoarce valoarea elementului minim

public int citeste()

//intoarce true cand coada este vida

public boolean esteVida()

//intoarce true cand coada este plina

public boolean estePlina()

//nr de elemente din coada

public int dimensiune()

class coadaAplicatie2

System.out.println();

System.out.println('Coada are '+coada.dimensiune()+' elemente');

}