Diferență între revizuiri ale paginii „SDA Lucrarea 4”

De la WikiLabs
Jump to navigationJump to search
 
(Nu s-au afișat 42 de versiuni intermediare efectuate de același utilizator)
Linia 1: Linia 1:
În acest laborator se vor implementa stive și cozi cu vectori și liste înlănțuite.
+
În acest laborator se vor utiliza stive și cozi din STL pentru rezolvarea de probleme.
  
 
= Coada =
 
= Coada =
Linia 21: Linia 21:
 
# Vizualizarea unui element din coadă fără extragerea acestuia (''peek'').
 
# Vizualizarea unui element din coadă fără extragerea acestuia (''peek'').
  
== Implementarea cozii cu liste ==
+
== Implementarea cozii ==
  
Pentru aplicațiile care folosesc doar funcționalitatea de bază a cozii (operațiile descrise mai sus), nu va necesară utilizarea unei liste dublu înlănțuite. Prin urmare, având o structură în care memorăm ultimul și primul nod dintr-o listă, adăugarea se va face întotdeauna după ultimul nod, iar extragerea va fi întotdeauna din primul nod. Definim în continuare structura de tip nod și structura ce va memora o coadă de șiruri de caractere:
+
Deoarece coada este o particularizare a unei secvențe în care doar o parte din operații sunt expuse utilizatorului, toate implementările de secvențe pot fi utilizate pentru implementări de cozi. Totuși, deoarece STL este implementat pentru eficiență maximă, doar structurile care oferă operații în timp minim sunt expuse pentru utilizarea în cozi: [http://en.cppreference.com/w/cpp/container/list std:list] și [http://en.cppreference.com/w/cpp/container/deque std::deque]. Un deque (Double-Ended Queue) este o structură de date care permite inserția și eliminarea de elemente din ambele capete în timp constant.
  
<syntaxhighlight lang="C">
+
Clasa care implementeaza cozi în STL este [http://en.cppreference.com/w/cpp/container/queue std::queue], este definită în header-ul <code>queue</code> și folosește implicit un <code>std::deque</code> pentru stocarea datelor:
struct SimplyLinkedNode {
 
    char * string;    // pointer la primul caracter din șir, aceasta este valoarea stocată în nod
 
    struct SimplyLinkedNode * next; // pointer la nodul următor.
 
};
 
  
#define UNLIMITED_SIZE (unsigned)-1
+
<syntaxhighlight lang="cpp">
 +
#include <queue>
 +
#include <cstdio>
  
struct LinkedQueue {
+
int main() {
     struct SimplyLinkedNode * firstNode;
+
     std::queue<int> myQueue;
     struct SimplyLinkedNode * lastNode;
+
     myQueue.push(10);
     unsigned size;
+
     myQueue.push(11);
     unsigned maxSize;
+
     myQueue.push(12);
};
+
    printf("Stack head is: %d\n", myQueue.front());
 +
    return 0;
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Se observă că cele două structuri sunt foarte similare cu definițiile pentru secvențele implementate cu liste simplu înlănțuite, diferențele constau în operațiile ce vor fi definite și modul lor de implementare. Ce a apărut în plus este câmpul <code>maxSize</code> care va fi inițializat cu valoarea numărului maxim de elemente din coadă, sau <code>UNLIMITED_SIZE</code> dacă coada este nelimitată. -1 este convertit la valoare fără semn în macro-ul <code>UNLIMITED_SIZE</code> pentru a obține cea mai mare valoare de tip <code>unsigned int</code>. Ne amintim că -1 în complement față de 2 se calculează plecând de la valoarea pozitivă (1) pe care o negăm pe biți și la care adunăm 1, obținând 0xFFFFFFFF, sau 4294967295.
+
Dacă doriți să utilizați o listă dublu înlănțuită pentru implementarea de cozi, sintaxa este următoarea:
  
== Crearea unui <code>LinkedQueue</code> ==
+
<syntaxhighlight lang="cpp">
 +
#include <queue>
 +
#include <list>
 +
#include <cstdio>
  
Pentru crearea unei cozi noi, se definește următoarea funcție:
+
int main() {
 +
    std::queue<int, std::list<int>> myListQueue;
 +
    myListQueue.push(10);
 +
    myListQueue.push(11);
 +
    myListQueue.push(12);
 +
    printf("Stack head of my list implemnted queue is: %d\n", myListQueue.front());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
  
<syntaxhighlight lang="C">
+
== Crearea unui <code>std::queue</code> ==
 +
 
 +
Pentru crearea unei cozi noi, se definește următorul constructor:
 +
 
 +
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Funcția alocă memorie și creeaza un nou LinkedQueue de o dimensiune maximă specificată.
+
  * Constructorul alocă memorie și creeaza un un nou std::queue.
* @param maxSize numarul maxim de elemente din coadă sau UNLIMITED_SIZE dacă aceasta
 
*  este nelimitată.
 
* @return pointer la o structura de tip LinkedQueue.  
 
 
  */
 
  */
struct LinkedQueue * createLinkedQueue(unsigned maxSize);
+
queue();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementarea acestei funcții se face folosind următorul algoritm:
+
Exemplu:
# Se alocă memorie pentru o variabilă de tip <code>struct LinkedQueue</code>.
+
 
# Se inițializează câmpul <code>maxSize</code> din strutură cu valoarea argumentului <code>maxSize</code>.
+
<syntaxhighlight lang="C">
# Se inițializează <code>size</code> cu 0.
+
#include <queue>
# Se inițializează <code>firstNode</code> și <code>lastNode</code> cu <code>NULL</code>.
+
#include <cstdio>
# Se întoarce adresa variabilei de tip <code>struct LinkedQueue</code>.
+
 
 +
using std::queue;
 +
 
 +
int main() {
 +
    queue<float> myQueue;
 +
    myQueue.push(0.1);
 +
    printf("Queue is empty: %d\n", myQueue.empty());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
  
 
== Interogarea dimensiunii ==
 
== Interogarea dimensiunii ==
Linia 68: Linia 89:
 
Pentru interogarea dimensiunii, se definește următoarea funcție:
 
Pentru interogarea dimensiunii, se definește următoarea funcție:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia intoarce numarul de elemente valide din coada specificata.
+
  * Metoda intoarce numarul de elemente din coada.
* @param queue coada pentru care se cere dimensinea.
+
  * @return numarul de elemente din coada.
  * @return numarul de elemente valide din coada queue.
 
 
  */
 
  */
unsigned linkedQueueSize(struct LinkedQueue * queue);
+
uint32_t size();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementarea acestei funcții se face întorcând direct valoarea câmpului <code>size</code> din structură.
+
Exemplu:
  
Pentru a verifica dacă structura este goală se definește următoarea funcție:
+
<syntaxhighlight lang="cpp">
 +
#include <queue>
 +
#include <cstdio>
  
<syntaxhighlight lang="C">
+
int main() {
/**
+
    std::queue<char> charQueue;
* Functia intoarce 1 dacă coada specificată este goală.
+
    charQueue.push('a');
* @param queue coada pentru care se cere dimensiunea.
+
    charQueue.push('b');
* @return 1 dacă coada este goală, 0 dacă nu
+
    charQueue.push('c');
*/
+
    printf("The queue has %u elements!\n", charQueue.size());
int linkedQueueIsEmpty(struct LinkedQueue * queue);
+
    return 0;
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementarea acestei funcții se face întorcând 1 dacă <code>size</code> este egal cu 0.
+
== Adăugarea unui element - push ==
  
Pentru a verifica dacă structura este plină se definește următoarea funcție:
+
Pentru adăugarea unui element '''value''' în coadă, se definește următoarea funcție:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia intoarce 1 dacă coada specificată este plină.
+
  * Metoda inserează elementul value în coadă.
  * @param queue coada pentru care se cere dimensiunea.
+
  * @param value elementul ce trebuie adăugat.
* @return 1 dacă coada este plină, 0 dacă nu
 
 
  */
 
  */
int linkedQueueIsFull(struct LinkedQueue * queue);
+
void push(T value);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementarea acestei funcții se face întorcând 1 dacă <code>size</code> este egal cu <code>maxSize</code>.
+
Exemplu:
  
== Adăugarea unui element - push ==
+
<syntaxhighlight lang="cpp">
 +
#include <queue>
 +
#include <cstdio>
 +
 
 +
int main() {
 +
    std::queue<char> charQueue;
 +
    charQueue.push('a');
 +
    charQueue.push('b');
 +
    charQueue.push('c');
 +
    printf("The queue has %u elements!\n", charQueue.size());
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 
 +
== Eliminarea elementului din vârful cozii - pop ==
  
Pentru adăugarea unui element '''newString''' în coadă, se definește următoarea funcție:
+
Pentru extragerea unui element din coadă, se definește următoarea metodă:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia inserează elementul newString în coadă.
+
  * Metoda elimina următorul element din coadă.
* @param queue coada la care se adaugă elementul.
 
* @param newString elementul ce trebuie adăugat.
 
 
  */
 
  */
void linkedQueuePush(struct LinkedQueue * queue, char * newString);
+
void pop();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Adăugarea unui element în coadă se face urmând pașii de mai jos.
+
Exemplu:
# Dacă coada este plină, se afișează un mesaj de eroare și funcția se încheie.
 
# Se alocă memorie pentru un nou nod <code>tmpNode</code> în care <code>tmpNode->next</code> este inițializat cu <code>NULL</code> și <code>tmpNode->string</code> cu <code>newString</code>.
 
# Dacă <code>size</code> este 0, <code>firstNode</code> devine <code>tmpNode</code>, altfel <code>lastNode->next</code> devine <code>tmpNode</code>.
 
# <code>lastNode</code> devine <code>tmpNode</code>.
 
# <code>size</code> se incrementează cu 1.
 
  
== Extragerea unui element - pop ==
+
<syntaxhighlight lang="cpp">
 +
#include <queue>
 +
#include <cstdio>
  
Pentru extragerea unui element din coadă, se definește următoarea funcție:
+
int main() {
 +
    std::queue<char> charQueue;
 +
    charQueue.push('a');
 +
    charQueue.push('b');
 +
    charQueue.push('c');
  
<syntaxhighlight lang="C">
+
    printf("Next char is: %c\n", charQueue.front());
/**
+
    charQueue.pop();
* Functia extrage următorul element din coadă.
+
    printf("Next char is: %c\n", charQueue.front());
* @return următorul element din coadă sau NULL dacă coada este goală.
+
    charQueue.pop();
*/
+
    printf("Next char is: %c\n", charQueue.front());
char * linkedQueuePop(struct LinkedQueue * queue);
+
    charQueue.pop();
 +
    return 0;
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Extragerea unui element din coadă se face urmând pașii de mai jos.
+
== Vizualizarea primului element din coadă - front ==
# Dacă coada este goală, se afișează un mesaj de eroare și se întoarce <code>NULL</code>.
 
# Se definește un pointer la nod numit <code>tmpNode</code> care ia valoarea lui <code>firstNode</code>.
 
# <code>firstNode</code> ia valoarea lui <code>firstNode->next</code>.
 
# Dacă <code>size</code> este 1, <code>lastNode</code> devine <code>NULL</code>.
 
# <code>size</code> se decrementează cu 1.
 
# Se definește o variabilă <code>returnString</code> care ia valoarea <code>tmpNode->string</code>.
 
# Se dezalocă memoria pentru <code>tmpNode</code>.
 
# Se întoarce valoarea <code>returnString</code>.
 
 
 
== Vizualizarea primului element din coadă - peek ==
 
  
Pentru vizualizarea primului element din coadă, fără a-l extrage, se definește următoarea funcție:
+
Pentru vizualizarea primului element din coadă, fără a-l extrage, se definește următoarea metodă:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia întoarce următorul element din coadă, fără a-l extrage.
+
  * Metoda întoarce următorul element din coadă, fără a-l extrage.
  * @return următorul element din coadă sau NULL dacă coada este goală.
+
  * @return următorul element din coadă
 
  */
 
  */
char * linkedQueuePeek(struct LinkedQueue * queue);
+
T front();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Extragerea unui element din coadă se face urmând pașii de mai jos.
+
Exemplu:
# Dacă coada este goală, se afișează un mesaj de eroare și se întoarce <code>NULL</code>.
 
# Se întoarce valoarea <code>firstNode->string</code>.
 
  
== Ștergerea unui <code>LinkedQueue</code> ==
+
<syntaxhighlight lang="cpp">
 +
#include <queue>
 +
#include <cstdio>
  
Pentru ștergerea unui <code>LinkedQueue</code> se definește următoarea funcție.
+
int main() {
 +
    std::queue<char> charQueue;
 +
    charQueue.push('a');
 +
    charQueue.push('b');
 +
    charQueue.push('c');
  
<syntaxhighlight lang="C">
+
    printf("Next char is: %c\n", charQueue.front());
/**
+
    charQueue.pop();
* Functia dezalocă memoria folosită de coada specificată.
+
    printf("Next char is: %c\n", charQueue.front());
* @param queue coada care trebuie ștearsă.
+
    charQueue.pop();
*/
+
    printf("Next char is: %c\n", charQueue.front());
void deleteLinkedQueue(struct LinkedQueue * queue);
+
    charQueue.pop();
 +
    return 0;
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 
Ștergerea unui <code>LinkedQueue</code> se realizează felul următor:
 
# Se utilizează un pointer temporar <code>tmpNode</code> pentru a itera peste toate nodurile din listă.
 
# Pentru fiecare nod, se șterge memoria alocată pentru <code>tmpNode->string</code> și pentru nod în sine (cu grijă să nu se piardă legătura la nodul următor).
 
# Se dezalocă memoria alocată pentru structura de tip <code>struct LinkedQueue</code>.
 
  
 
= Stiva =
 
= Stiva =
Linia 200: Linia 228:
 
# Vizualizarea unui element din stivă fără extragerea acestuia (''peek'').
 
# Vizualizarea unui element din stivă fără extragerea acestuia (''peek'').
  
== Implementarea stivei cu vectori ==
+
== Implementarea stivei ==
  
Stivele implementate cu vectori sunt de cele mai multe ori limitate, pentru a evita operația de realocare. Vom avea nevoie să stocăm în structura alocată pointer-ul la vector, capacitatea acestuia cât și capul stivei (stack head). Deoarece pentru o stivă goală capul ei este pe poziția -1, pentru a evita definirea tuturor indecșilor cu semn exclusiv pentru acest caz particular, vom salva valoarea ('''head + 1''') în loc de head, vom numi câmpul '''aboveHead''' și îl vom inițializa cu 0. În continuare, ca exemplu vom defini o structură pentru o stivă de caractere.
+
În STL, clasa care implementează stiva este [http://en.cppreference.com/w/cpp/container/stack std::stack]. Ca și coada, această clasă se folosește de o implementare concretă de secvență care poate face operațiile necesare stivei în timp constant. Clasele posibile pentru salvarea datelor unei stive sunt [http://en.cppreference.com/w/cpp/container/vector std::vector], [http://en.cppreference.com/w/cpp/container/list std::list] și [http://en.cppreference.com/w/cpp/container/deque std::deque]. Implicit clasa folosită este <code>std::deque</code>.
  
<syntaxhighlight lang="C">
+
== Crearea unui obiect de tip <code>std::stack</code> ==
struct ArrayStack {
 
    char * array;
 
    unsigned capacity;
 
    unsigned aboveHead;
 
};
 
</syntaxhighlight>
 
  
== Crearea unui <code>ArrayStack</code> ==
+
Pentru crearea unei stive noi, se definește următorul constructor:
  
Pentru crearea unei stive noi, se definește următoarea funcție:
+
<syntaxhighlight lang="cpp">
 
 
<syntaxhighlight lang="C">
 
 
/**
 
/**
  * Funcția alocă memorie și creeaza un nou ArrayStack de o dimensiune maximă specificată.
+
  * Constructorul alocă memorie și creeaza o noua stiva.
* @param capacity numarul maxim de elemente din stivă
 
* @return pointer la o structura de tip ArrayStack.  
 
 
  */
 
  */
struct ArrayStack * createArrayStack(unsigned capacity);
+
stack();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementarea acestei funcții se face folosind următorul algoritm:
+
Exemplu:
# Se alocă memorie pentru o variabilă de tip <code>struct ArrayStack</code>.
 
# Se inițializează câmpul <code>capacity</code> din structură cu valoarea argumentului <code>capacity</code>.
 
# Se inițializează <code>aboveHead</code> cu 0.
 
# Se alocă memorie pentru <code>capacity</code> elemente și pointer-ul se memorează în <code>array</code>.
 
# Se întoarce adresa variabilei de tip <code>struct ArrayStack</code>.
 
  
== Interogarea dimensiunii ==
+
<syntaxhighlight lang="cpp" highlight="6">
 +
#include <stack>
 +
#include <cstdio>
 +
using std::stack;
  
Pentru interogarea dimensiunii, se definește următoarea funcție:
+
int main() {
 +
    stack<char> word;
 +
    word.push('c');
 +
    word.push('a');
 +
    word.push('s');
 +
    word.push('t');
 +
    word.push('r');
 +
    word.push('a');
 +
    word.push('v');
 +
    word.push('e');
 +
    word.push('t');
 +
    word.push('e');
  
<syntaxhighlight lang="C">
+
    while(!word.empty()) {
/**
+
        printf("%c", word.top());
* Functia intoarce numarul de elemente valide din stiva specificata.
+
        word.pop();
* @param stack stiva pentru care se cere dimensinea.
+
    }
* @return numarul de elemente valide din stiva stack.
+
    printf("\n");
*/
+
    return 0;
unsigned arrayStackSize(struct ArrayStack * stack);
+
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementarea acestei funcții se face întorcând direct valoarea câmpului <code>aboveHead</code> din structură.
+
== Interogarea dimensiunii ==
  
Pentru a verifica dacă structura este goală se definește următoarea funcție:
+
Pentru interogarea dimensiunii, se definește următoarea metodă:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia intoarce 1 dacă stiva specificată este goală.
+
  * Metoda intoarce numarul de elemente din stiva.
  * @param stack stiva pentru care se cere dimensiunea.
+
  * @return numarul de elemente din stiva.
* @return 1 dacă stiva este goală, 0 dacă nu
 
 
  */
 
  */
int arrayStackIsEmpty(struct ArrayStack * stack);
+
uint32_t size();
</syntaxhighlight>
 
  
Implementarea acestei funcții se face întorcând 1 dacă <code>aboveHead</code> este egal cu 0.
 
 
Pentru a verifica dacă structura este plină se definește următoarea funcție:
 
 
<syntaxhighlight lang="C">
 
 
/**
 
/**
  * Functia intoarce 1 dacă stiva specificată este plină.
+
  * Metoda intoarce true daca stiva este goala.
  * @param stack stiva pentru care se cere dimensiunea.
+
  * @return true daca stiva este goala.
  * @return 1 dacă stiva este plină, 0 dacă nu
 
 
  */
 
  */
int arrayStackIsFull(struct ArrayStack * stack);
+
bool empty();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementarea acestei funcții se face întorcând 1 dacă <code>aboveHead</code> este egal cu <code>capacity</code>.
+
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="18,20">
 +
#include <stack>
 +
#include <cstdio>
 +
using std::stack;
  
== Adăugarea unui element - push ==
+
int main() {
 +
    stack<char> word;
 +
    word.push('c');
 +
    word.push('a');
 +
    word.push('s');
 +
    word.push('t');
 +
    word.push('r');
 +
    word.push('a');
 +
    word.push('v');
 +
    word.push('e');
 +
    word.push('t');
 +
    word.push('e');
  
Pentru adăugarea unui element '''newChar''' în stivă, se definește următoarea funcție:
+
    printf("The stack has %u elements!\n", word.size());
  
<syntaxhighlight lang="C">
+
    while(!word.empty()) {
/**
+
        printf("%c", word.top());
* Functia inserează elementul newChar în stivă.
+
        word.pop();
* @param stack stiva la care se adaugă elementul.
+
    }
* @param newChar elementul ce trebuie adăugat.
+
    printf("\n");
*/
+
    return 0;
void arrayStackPush(struct ArrayStack * stack, char newChar);
+
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Adăugarea unui element în stivă se face urmând pașii de mai jos.
+
== Adăugarea unui element - push ==
# Dacă stiva este plină, se afișează un mesaj de eroare și funcția se încheie.
 
# Se scrie <code>newChar</code> pe poziția <code>aboveHead</code> în <code>array</code>.
 
# <code>aboveHead</code> se incrementează cu 1.
 
  
== Extragerea unui element - pop ==
+
Pentru adăugarea unui element '''value''' în stivă, se definește următoarea metodă:
  
Pentru extragerea unui element din stivă, se definește următoarea funcție:
+
<syntaxhighlight lang="cpp">
 
 
<syntaxhighlight lang="C">
 
 
/**
 
/**
  * Functia extrage următorul element din stivă.
+
  * Metoda inserează elementul value în stivă.
  * @return următorul element din stivă sau 0 dacă stiva este goală.
+
  * @param value elementul ce trebuie adăugat.
 
  */
 
  */
char arrayStackPop(struct ArrayStack * stack);
+
void push(T value);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Extragerea unui element din stivă se face urmând pașii de mai jos.
+
Exemplu:
# Dacă stiva este goală, se afișează un mesaj de eroare și se întoarce <code>0</code>.
 
# Se decrementează <code>aboveHead</code> cu 1.
 
# Se întoarce elementul de pe poziția <code>aboveHead</code> din <code>array</code>.
 
  
== Vizualizarea primului element din coadă - peek ==
+
<syntaxhighlight lang="cpp" highlight="7-16">
 +
#include <stack>
 +
#include <cstdio>
 +
using std::stack;
  
Pentru vizualizarea primului element din coadă, fără a-l extrage, se definește următoarea funcție:
+
int main() {
 +
    stack<char> word;
 +
    word.push('c');
 +
    word.push('a');
 +
    word.push('s');
 +
    word.push('t');
 +
    word.push('r');
 +
    word.push('a');
 +
    word.push('v');
 +
    word.push('e');
 +
    word.push('t');
 +
    word.push('e');
  
<syntaxhighlight lang="C">
+
    printf("The stack has %u elements!\n", word.size());
/**
+
 
* Functia întoarce următorul element din coadă, fără a-l extrage.
+
    while(!word.empty()) {
* @return următorul element din coadă sau NULL dacă coada este goală.
+
        printf("%c", word.top());
*/
+
        word.pop();
char * linkedQueuePeek(struct LinkedQueue * queue);
+
    }
 +
    printf("\n");
 +
    return 0;
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Extragerea unui element din coadă se face urmând pașii de mai jos.
+
== Eliminarea unui element - pop ==
# Dacă coada este goală, se afișează un mesaj de eroare și se întoarce <code>NULL</code>.
 
# Se întoarce valoarea <code>firstNode->string</code>.
 
  
== Ștergerea unui <code>LinkedQueue</code> ==
+
Pentru eliminarea elementului din vârful stivei, se definește următoarea metodă:
  
Pentru ștergerea unui <code>LinkedQueue</code> se definește următoarea funcție.
+
<syntaxhighlight lang="cpp">
 
 
<syntaxhighlight lang="C">
 
 
/**
 
/**
  * Functia dezalocă memoria folosită de coada specificată.
+
  * Metoda elimina următorul element din stivă.
* @param queue coada care trebuie ștearsă.
 
 
  */
 
  */
void deleteLinkedQueue(struct LinkedQueue * queue);
+
void pop();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Ștergerea unui <code>LinkedQueue</code> se realizează felul următor:
+
Exemplu:
# Se utilizează un pointer temporar <code>tmpNode</code> pentru a itera peste toate nodurile din listă.
 
# Pentru fiecare nod, se șterge memoria alocată pentru <code>tmpNode->string</code> și pentru nod în sine (cu grijă să nu se piardă legătura la nodul următor).
 
# Se dezalocă memoria alocată pentru structura de tip <code>struct LinkedQueue</code>.
 
  
= Exerciții =
+
<syntaxhighlight lang="cpp" highlight="22">
 +
#include <stack>
 +
#include <cstdio>
 +
using std::stack;
  
== Săptămâna 1 ==
+
int main() {
 +
    stack<char> word;
 +
    word.push('c');
 +
    word.push('a');
 +
    word.push('s');
 +
    word.push('t');
 +
    word.push('r');
 +
    word.push('a');
 +
    word.push('v');
 +
    word.push('e');
 +
    word.push('t');
 +
    word.push('e');
  
<ol>
+
    printf("The stack has %u elements!\n", word.size());
<li>Se dă fișierul header <code>linkedQueue.h</code> de mai jos:
 
  
<syntaxhighlight lang="C">
+
    while(!word.empty()) {
struct SimplyLinkedNode {
+
        printf("%c", word.top());
     char * string;     // pointer la primul caracter din șir, aceasta este valoarea stocată în nod
+
        word.pop();
     struct SimplyLinkedNode * next; // pointer la nodul următor.
+
    }
};
+
     printf("\n");
 +
     return 0;
 +
}
 +
</syntaxhighlight>
  
#define UNLIMITED_SIZE (unsigned)-1
+
== Vizualizarea primului element din stivă - top ==
  
struct LinkedQueue {
+
Pentru vizualizarea primului element din stivă, fără a-l extrage, se definește următoarea metodă:
    struct SimplyLinkedNode * firstNode;
 
    struct SimplyLinkedNode * lastNode;
 
    unsigned size;
 
    unsigned maxSize;
 
};
 
  
 +
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Funcția alocă memorie și creeaza un nou LinkedQueue de o dimensiune maximă specificată.
+
  * Metoda întoarce următorul element din stivă, fără a-l extrage.
* @param maxSize numarul maxim de elemente din coadă sau UNLIMITED_SIZE dacă aceasta
+
  * @return următorul element din stivă.
*  este nelimitată.
 
  * @return pointer la o structura de tip LinkedQueue.  
 
 
  */
 
  */
struct LinkedQueue * createLinkedQueue(unsigned maxSize);
+
T top();
 
+
</syntaxhighlight>
/**
 
* Functia intoarce numarul de elemente valide din coada specificata.
 
* @param queue coada pentru care se cere dimensinea.
 
* @return numarul de elemente valide din coada queue.
 
*/
 
unsigned linkedQueueSize(struct LinkedQueue * queue);
 
  
/**
+
Exemplu:
* Functia intoarce 1 dacă coada specificată este goală.
 
* @param queue coada pentru care se cere dimensiunea.
 
* @return 1 dacă coada este goală, 0 dacă nu
 
*/
 
int linkedQueueIsEmpty(struct LinkedQueue * queue);
 
 
 
/**
 
* Functia intoarce 1 dacă coada specificată este plină.
 
* @param queue coada pentru care se cere dimensiunea.
 
* @return 1 dacă coada este plină, 0 dacă nu
 
*/
 
int linkedQueueIsFull(struct LinkedQueue * queue);
 
  
/**
+
<syntaxhighlight lang="cpp" highlight="21">
* Functia inserează elementul newString în coadă.
+
#include <stack>
* @param queue coada la care se adaugă elementul.
+
#include <cstdio>
* @param newString elementul ce trebuie adăugat.
+
using std::stack;
*/
 
void linkedQueuePush(struct LinkedQueue * queue, char * newString);
 
  
/**
+
int main() {
* Functia extrage următorul element din coadă.
+
    stack<char> word;
* @return următorul element din coadă sau NULL dacă coada este goală.
+
    word.push('c');
*/
+
    word.push('a');
char * linkedQueuePop(struct LinkedQueue * queue);
+
    word.push('s');
 +
    word.push('t');
 +
    word.push('r');
 +
    word.push('a');
 +
    word.push('v');
 +
    word.push('e');
 +
    word.push('t');
 +
    word.push('e');
  
/**
+
    printf("The stack has %u elements!\n", word.size());
* Functia întoarce următorul element din coadă, fără a-l extrage.
 
* @return următorul element din coadă sau NULL dacă coada este goală.
 
*/
 
char * linkedQueuePeek(struct LinkedQueue * queue);
 
  
/**
+
    while(!word.empty()) {
* Functia dezalocă memoria folosită de coada specificată.
+
        printf("%c", word.top());
* @param queue coada care trebuie ștearsă.
+
        word.pop();
*/
+
    }
void deleteLinkedQueue(struct LinkedQueue * queue);
+
    printf("\n");
 +
    return 0;
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 
Implementați funcțiile definite în header într-un fișier <code>linkedQueue.c</code>.
 
</li>
 
<li>Scrieți o altă sursă, <code>main.c</code> în care să creați trei cozi: <code>inQueue</code>, <code>shortStringsQueue</code> și <code>longStringsQueue</code>. Citiți conținutul fișierului de mai jos linie cu linie și inserați-le în <code>inQueue</code>. Apoi extrageti elementele din <code>inQueue</code> și dacă ele sunt mai lungi de 10 caractere, inserați-le în <code>longStringQueue</code> iar dacă nu, inserați-le în <code>shortStringsQueue</code>. Apoi extrageți elementele din <code>shortStringsQueue</code> și afișați-le pe ecran, urmate de elementele din <code>longStringsQueue</code>.
 
 
Observație: În contextul curent, utilizarea cozilor în programul de mai sus nu este necesar. Cozile se utilizează în practică în două situații:
 
# Când există două procese sau fire de execuție care funcționează în paralel, și din care unul adaugă elemente în coadă iar celălalt consumă.
 
# Când același proces extrage elemente din coadă dar în același timp generează alte elemente în coadă pentru procesare ulterioră (vom vedea acest lucru la capitolul parcurgeri de arbori).
 
</li>
 
</ol>
 

Versiunea curentă din 13 aprilie 2017 12:41

În acest laborator se vor utiliza stive și cozi din STL pentru rezolvarea de probleme.

Coada

Coada este o structură de date de tip FIFO (First In First Out), care stochează o colecție de elemente în ordinea în care au fost adăugate.

Queue.png

Coada are următoarele proprietăți:

  1. Datele sunt stocate într-o anumită ordine (se poate spune că un element este plasat înaintea sau după un alt element în structură).
  2. Numărul de elemente ce poate fi stocat de structură este nelimitat sau limitat, în funcție de implementare.
  3. Elementele stocate în coadă sunt de același fel.
  4. Elementele pot fi adăugate doar la unul din capete și extrase doar de la celălalt - primul element inserat este primul care este extras.

Coada suportă următoarele operații de bază:

  1. Interogarea numărului de elemente din coadă.
  2. Verificarea dacă coada este goală.
  3. Verificarea dacă coada este plină (pentru cozi limitate).
  4. Adăugarea unui element în coadă (push).
  5. Extragerea unui element din coadă (pop).
  6. Vizualizarea unui element din coadă fără extragerea acestuia (peek).

Implementarea cozii

Deoarece coada este o particularizare a unei secvențe în care doar o parte din operații sunt expuse utilizatorului, toate implementările de secvențe pot fi utilizate pentru implementări de cozi. Totuși, deoarece STL este implementat pentru eficiență maximă, doar structurile care oferă operații în timp minim sunt expuse pentru utilizarea în cozi: std:list și std::deque. Un deque (Double-Ended Queue) este o structură de date care permite inserția și eliminarea de elemente din ambele capete în timp constant.

Clasa care implementeaza cozi în STL este std::queue, este definită în header-ul queue și folosește implicit un std::deque pentru stocarea datelor:

#include <queue>
#include <cstdio>

int main() {
    std::queue<int> myQueue;
    myQueue.push(10);
    myQueue.push(11);
    myQueue.push(12);
    printf("Stack head is: %d\n", myQueue.front());
    return 0;
}

Dacă doriți să utilizați o listă dublu înlănțuită pentru implementarea de cozi, sintaxa este următoarea:

#include <queue>
#include <list>
#include <cstdio>

int main() {
    std::queue<int, std::list<int>> myListQueue;
    myListQueue.push(10);
    myListQueue.push(11);
    myListQueue.push(12);
    printf("Stack head of my list implemnted queue is: %d\n", myListQueue.front());
    return 0;
}

Crearea unui std::queue

Pentru crearea unei cozi noi, se definește următorul constructor:

/**
 * Constructorul alocă memorie și creeaza un un nou std::queue.
 */
queue();

Exemplu:

#include <queue>
#include <cstdio>

using std::queue;

int main() {
    queue<float> myQueue;
    myQueue.push(0.1);
    printf("Queue is empty: %d\n", myQueue.empty());
    return 0;
}

Interogarea dimensiunii

Pentru interogarea dimensiunii, se definește următoarea funcție:

/**
 * Metoda intoarce numarul de elemente din coada.
 * @return numarul de elemente din coada.
 */
uint32_t size();

Exemplu:

#include <queue>
#include <cstdio>

int main() {
    std::queue<char> charQueue;
    charQueue.push('a');
    charQueue.push('b');
    charQueue.push('c');
    printf("The queue has %u elements!\n", charQueue.size());
    return 0;
}

Adăugarea unui element - push

Pentru adăugarea unui element value în coadă, se definește următoarea funcție:

/**
 * Metoda inserează elementul value în coadă.
 * @param value elementul ce trebuie adăugat.
 */
void push(T value);

Exemplu:

#include <queue>
#include <cstdio>

int main() {
    std::queue<char> charQueue;
    charQueue.push('a');
    charQueue.push('b');
    charQueue.push('c');
    printf("The queue has %u elements!\n", charQueue.size());
    return 0;
}

Eliminarea elementului din vârful cozii - pop

Pentru extragerea unui element din coadă, se definește următoarea metodă:

/**
 * Metoda elimina următorul element din coadă.
 */
void pop();

Exemplu:

#include <queue>
#include <cstdio>

int main() {
    std::queue<char> charQueue;
    charQueue.push('a');
    charQueue.push('b');
    charQueue.push('c');

    printf("Next char is: %c\n", charQueue.front());
    charQueue.pop();
    printf("Next char is: %c\n", charQueue.front());
    charQueue.pop();
    printf("Next char is: %c\n", charQueue.front());
    charQueue.pop();
    return 0;
}

Vizualizarea primului element din coadă - front

Pentru vizualizarea primului element din coadă, fără a-l extrage, se definește următoarea metodă:

/**
 * Metoda întoarce următorul element din coadă, fără a-l extrage.
 * @return următorul element din coadă
 */
T front();

Exemplu:

#include <queue>
#include <cstdio>

int main() {
    std::queue<char> charQueue;
    charQueue.push('a');
    charQueue.push('b');
    charQueue.push('c');

    printf("Next char is: %c\n", charQueue.front());
    charQueue.pop();
    printf("Next char is: %c\n", charQueue.front());
    charQueue.pop();
    printf("Next char is: %c\n", charQueue.front());
    charQueue.pop();
    return 0;
}

Stiva

Stiva este o structură de date de tip LIFO (Last In First Out), care stochează o colecție de elemente în ordinea în care au fost adăugate.

Stack.png

Stiva are următoarele proprietăți:

  1. Datele sunt stocate într-o anumită ordine (se poate spune că un element este plasat înaintea sau după un alt element în structură).
  2. Numărul de elemente ce poate fi stocat de structură este nelimitat sau limitat, în funcție de implementare.
  3. Elementele stocate în stivă sunt de același fel.
  4. Elementele pot fi adăugate sau extrase doar dintr-un capăt - ultimul element inserat este primul care este extras.

Stiva suportă următoarele operații de bază:

  1. Interogarea numărului de elemente din stivă.
  2. Verificarea dacă stiva este goală.
  3. Verificarea dacă stiva este plină (pentru stive limitate).
  4. Adăugarea unui element în stivă (push).
  5. Extragerea unui element din stivă (pop).
  6. Vizualizarea unui element din stivă fără extragerea acestuia (peek).

Implementarea stivei

În STL, clasa care implementează stiva este std::stack. Ca și coada, această clasă se folosește de o implementare concretă de secvență care poate face operațiile necesare stivei în timp constant. Clasele posibile pentru salvarea datelor unei stive sunt std::vector, std::list și std::deque. Implicit clasa folosită este std::deque.

Crearea unui obiect de tip std::stack

Pentru crearea unei stive noi, se definește următorul constructor:

/**
 * Constructorul alocă memorie și creeaza o noua stiva.
 */
stack();

Exemplu:

#include <stack>
#include <cstdio>
using std::stack;

int main() {
    stack<char> word;
    word.push('c'); 
    word.push('a');
    word.push('s');
    word.push('t');
    word.push('r');
    word.push('a');
    word.push('v');
    word.push('e');
    word.push('t');
    word.push('e');

    while(!word.empty()) {
        printf("%c", word.top());
        word.pop();
    }
    printf("\n");
    return 0;
}

Interogarea dimensiunii

Pentru interogarea dimensiunii, se definește următoarea metodă:

/**
 * Metoda intoarce numarul de elemente din stiva.
 * @return numarul de elemente din stiva.
 */
uint32_t size();

/**
 * Metoda intoarce true daca stiva este goala.
 * @return  true daca stiva este goala.
 */
bool empty();

Exemplu:

#include <stack>
#include <cstdio>
using std::stack;

int main() {
    stack<char> word;
    word.push('c'); 
    word.push('a');
    word.push('s');
    word.push('t');
    word.push('r');
    word.push('a');
    word.push('v');
    word.push('e');
    word.push('t');
    word.push('e');

    printf("The stack has %u elements!\n", word.size());

    while(!word.empty()) {
        printf("%c", word.top());
        word.pop();
    }
    printf("\n");
    return 0;
}

Adăugarea unui element - push

Pentru adăugarea unui element value în stivă, se definește următoarea metodă:

/**
 * Metoda inserează elementul value în stivă.
 * @param value elementul ce trebuie adăugat.
 */
void push(T value);

Exemplu:

#include <stack>
#include <cstdio>
using std::stack;

int main() {
    stack<char> word;
    word.push('c'); 
    word.push('a');
    word.push('s');
    word.push('t');
    word.push('r');
    word.push('a');
    word.push('v');
    word.push('e');
    word.push('t');
    word.push('e');

    printf("The stack has %u elements!\n", word.size());

    while(!word.empty()) {
        printf("%c", word.top());
        word.pop();
    }
    printf("\n");
    return 0;
}

Eliminarea unui element - pop

Pentru eliminarea elementului din vârful stivei, se definește următoarea metodă:

/**
 * Metoda elimina următorul element din stivă.
 */
void pop();

Exemplu:

#include <stack>
#include <cstdio>
using std::stack;

int main() {
    stack<char> word;
    word.push('c'); 
    word.push('a');
    word.push('s');
    word.push('t');
    word.push('r');
    word.push('a');
    word.push('v');
    word.push('e');
    word.push('t');
    word.push('e');

    printf("The stack has %u elements!\n", word.size());

    while(!word.empty()) {
        printf("%c", word.top());
        word.pop();
    }
    printf("\n");
    return 0;
}

Vizualizarea primului element din stivă - top

Pentru vizualizarea primului element din stivă, fără a-l extrage, se definește următoarea metodă:

/**
 * Metoda întoarce următorul element din stivă, fără a-l extrage.
 * @return următorul element din stivă.
 */
T top();

Exemplu:

#include <stack>
#include <cstdio>
using std::stack;

int main() {
    stack<char> word;
    word.push('c'); 
    word.push('a');
    word.push('s');
    word.push('t');
    word.push('r');
    word.push('a');
    word.push('v');
    word.push('e');
    word.push('t');
    word.push('e');

    printf("The stack has %u elements!\n", word.size());

    while(!word.empty()) {
        printf("%c", word.top());
        word.pop();
    }
    printf("\n");
    return 0;
}