SDA Lucrarea 4

În acest laborator se vor implementa stive și cozi cu vectori și liste înlănțuite.

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.

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 și este definită în header-ul queue:

#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 newString în coadă, se definește următoarea funcție:

/**
 * Functia inserează elementul newString în coadă.
 * @param queue coada la care se adaugă elementul.
 * @param newString elementul ce trebuie adăugat.
 */
void linkedQueuePush(struct LinkedQueue * queue, char * newString);

Adăugarea unui element în coadă se face urmând pașii de mai jos.

1. Dacă coada este plină, se afișează un mesaj de eroare și funcția se încheie.
2. Se alocă memorie pentru un nou nod tmpNode în care tmpNode->next este inițializat cu NULL și tmpNode->string cu newString.
3. Dacă size este 0, firstNode devine tmpNode, altfel lastNode->next devine tmpNode.
4. lastNode devine tmpNode.
5. size se incrementează cu 1.

Extragerea unui element - pop

Pentru extragerea unui element din coadă, se definește următoarea funcție:

/**
 * Functia extrage următorul element din coadă.
 * @param queue coada din care se extrage elementul.
 * @return următorul element din coadă sau NULL dacă coada este goală.
 */
char * linkedQueuePop(struct LinkedQueue * queue);

Extragerea unui element din coadă se face urmând pașii de mai jos.

1. Dacă coada este goală, se afișează un mesaj de eroare și se întoarce NULL.
2. Se definește un pointer la nod numit tmpNode care ia valoarea lui firstNode.
3. firstNode ia valoarea lui firstNode->next.
4. Dacă size este 1, lastNode devine NULL.
5. size se decrementează cu 1.
6. Se definește o variabilă returnString care ia valoarea tmpNode->string.
7. Se dezalocă memoria pentru tmpNode.
8. Se întoarce valoarea returnString.

Vizualizarea primului element din coadă - peek

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

/**
 * Functia întoarce următorul element din coadă, fără a-l extrage.
 * @param queue coada din care se vizualizează elementul.
 * @return următorul element din coadă sau NULL dacă coada este goală.
 */
char * linkedQueuePeek(struct LinkedQueue * queue);

Vizualizarea unui element din coadă se face urmând pașii de mai jos.

1. Dacă coada este goală, se afișează un mesaj de eroare și se întoarce NULL.
2. Se întoarce valoarea firstNode->string.

Ștergerea unui LinkedQueue

Pentru ștergerea unui LinkedQueue se definește următoarea funcție.

/**
 * Functia dezalocă memoria folosită de coada specificată.
 * @param queue coada care trebuie ștearsă.
 */
void deleteLinkedQueue(struct LinkedQueue * queue);

Ștergerea unui LinkedQueue se realizează felul următor:

1. Se utilizează un pointer temporar tmpNode pentru a itera peste toate nodurile din listă.
2. Pentru fiecare nod, se șterge memoria alocată pentru tmpNode->string și pentru nod în sine (cu grijă să nu se piardă legătura la nodul următor).
3. Se dezalocă memoria alocată pentru structura de tip struct LinkedQueue.

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.

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 cu vectori

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.

struct ArrayStack {
    char * array;
    unsigned capacity;
    unsigned aboveHead;
};

Crearea unui ArrayStack

Pentru crearea unei stive noi, se definește următoarea funcție:

/**
 * Funcția alocă memorie și creeaza un nou ArrayStack de o dimensiune maximă specificată.
 * @param capacity numarul maxim de elemente din stivă
 * @return pointer la o structura de tip ArrayStack. 
 */
struct ArrayStack * createArrayStack(unsigned capacity);

Implementarea acestei funcții se face folosind următorul algoritm:

1. Se alocă memorie pentru o variabilă de tip struct ArrayStack.
2. Se inițializează câmpul capacity din structură cu valoarea argumentului capacity.
3. Se inițializează aboveHead cu 0.
4. Se alocă memorie pentru capacity elemente și pointer-ul se memorează în array.
5. Se întoarce adresa variabilei de tip struct ArrayStack.

Interogarea dimensiunii

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

/**
 * Functia intoarce numarul de elemente valide din stiva specificata.
 * @param stack stiva pentru care se cere dimensinea.
 * @return numarul de elemente valide din stiva stack.
 */
unsigned arrayStackSize(struct ArrayStack * stack);

Implementarea acestei funcții se face întorcând direct valoarea câmpului aboveHead din structură.

Pentru a verifica dacă structura este goală se definește următoarea funcție:

/**
 * Functia intoarce 1 dacă stiva specificată este goală.
 * @param stack stiva pentru care se cere dimensiunea.
 * @return 1 dacă stiva este goală, 0 dacă nu
 */
int arrayStackIsEmpty(struct ArrayStack * stack);

Implementarea acestei funcții se face întorcând 1 dacă aboveHead este egal cu 0.

Pentru a verifica dacă structura este plină se definește următoarea funcție:

/**
 * Functia intoarce 1 dacă stiva specificată este plină.
 * @param stack stiva pentru care se cere dimensiunea.
 * @return 1 dacă stiva este plină, 0 dacă nu
 */
int arrayStackIsFull(struct ArrayStack * stack);

Implementarea acestei funcții se face întorcând 1 dacă aboveHead este egal cu capacity.

Adăugarea unui element - push

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

/**
 * Functia inserează elementul newChar în stivă.
 * @param stack stiva la care se adaugă elementul.
 * @param newChar elementul ce trebuie adăugat.
 */
void arrayStackPush(struct ArrayStack * stack, char newChar);

Adăugarea unui element în stivă se face urmând pașii de mai jos.

1. Dacă stiva este plină, se afișează un mesaj de eroare și funcția se încheie.
2. Se scrie newChar pe poziția aboveHead în array.
3. aboveHead se incrementează cu 1.

Extragerea unui element - pop

Pentru extragerea unui element din stivă, se definește următoarea funcție:

/**
 * Functia extrage următorul element din stivă.
 * @param stack stiva din care se extrage elementul.
 * @return următorul element din stivă sau 0 dacă stiva este goală.
 */
char arrayStackPop(struct ArrayStack * stack);

Extragerea unui element din stivă se face urmând pașii de mai jos.

1. Dacă stiva este goală, se afișează un mesaj de eroare și se întoarce 0.
2. Se decrementează aboveHead cu 1.
3. Se întoarce elementul de pe poziția aboveHead din array.

Vizualizarea primului element din stivă - peek

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

/**
 * Functia întoarce următorul element din stivă, fără a-l extrage.
 * @param stack stiva din care se vizualizează elementul.
 * @return următorul element din stivă sau 0 dacă stiva este goală.
 */
char arrayStackPeek(struct ArrayStack * stack);

Vizualizarea unui element din stivă se face urmând pașii de mai jos.

1. Dacă stivă este goală, se afișează un mesaj de eroare și se întoarce 0.
2. Se întoarce valoarea de pe poziția aboveHead - 1 din array.

Ștergerea unui ArrayStack

Pentru ștergerea unui ArrayStack se definește următoarea funcție.

/**
 * Functia dezalocă memoria folosită de stiva specificată.
 * @param stack stiva care trebuie ștearsă.
 */
void deleteArrayStack(struct ArrayStack * stack);

Ștergerea unui ArrayStack se realizează felul următor:

1. Se dezalocă memoria utilizată de array.
2. Se dezalocă memoria alocată pentru structura de tip struct ArrayStack.

Exerciții

Săptămâna 1

1. Se dă fișierul header linkedQueue.h de mai jos:

   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
   
   struct LinkedQueue {
       struct SimplyLinkedNode * firstNode;
       struct SimplyLinkedNode * lastNode;
       unsigned size;
       unsigned maxSize;
   };
   
   /**
    * Funcția alocă memorie și creeaza un nou LinkedQueue de o dimensiune maximă specificată.
    * @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);
   
   /**
    * 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);
   
   /**
    * 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);
   
   /**
    * Functia inserează elementul newString în coadă.
    * @param queue coada la care se adaugă elementul.
    * @param newString elementul ce trebuie adăugat.
    */
   void linkedQueuePush(struct LinkedQueue * queue, char * newString);
   
   /**
    * Functia extrage următorul element din coadă.
    * @return următorul element din coadă sau NULL dacă coada este goală.
    */
   char * linkedQueuePop(struct LinkedQueue * queue);
   
   /**
    * 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);
   
   /**
    * Functia dezalocă memoria folosită de coada specificată.
    * @param queue coada care trebuie ștearsă.
    */
   void deleteLinkedQueue(struct LinkedQueue * queue);
   

   Implementați funcțiile definite în header într-un fișier linkedQueue.c.

2. Scrieți o altă sursă, main.c în care să creați trei cozi: inQueue, shortStringsQueue și longStringsQueue. Citiți conținutul unui fișier text linie cu linie și inserați-le în inQueue. Apoi extrageti elementele din inQueue și dacă ele sunt mai lungi de 10 caractere, inserați-le în longStringQueue iar dacă nu, inserați-le în shortStringsQueue. Apoi extrageți elementele din shortStringsQueue și afișați-le pe ecran, urmate de elementele din longStringsQueue. Observație: În contextul curent, utilizarea cozilor în programul de mai sus nu este necesar. Cozile se utilizează în practică în două situații:
   1. 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ă.
   2. 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).

Săptămâna 2

1. Se dă fișierul header arrayStack.h de mai jos:

   struct ArrayStack {
       char * array;
       unsigned capacity;
       unsigned aboveHead;
   };
   
   /**
    * Funcția alocă memorie și creeaza un nou ArrayStack de o dimensiune maximă specificată.
    * @param capacity numarul maxim de elemente din stivă
    * @return pointer la o structura de tip ArrayStack. 
    */
   struct ArrayStack * createArrayStack(unsigned capacity);
   
   /**
    * Functia intoarce numarul de elemente valide din stiva specificata.
    * @param stack stiva pentru care se cere dimensinea.
    * @return numarul de elemente valide din stiva stack.
    */
   unsigned arrayStackSize(struct ArrayStack * stack);
   
   /**
    * Functia intoarce 1 dacă stiva specificată este goală.
    * @param stack stiva pentru care se cere dimensiunea.
    * @return 1 dacă stiva este goală, 0 dacă nu
    */
   int arrayStackIsEmpty(struct ArrayStack * stack);
   
   /**
    * Functia intoarce 1 dacă stiva specificată este plină.
    * @param stack stiva pentru care se cere dimensiunea.
    * @return 1 dacă stiva este plină, 0 dacă nu
    */
   int arrayStackIsFull(struct ArrayStack * stack);
   
   /**
    * Functia inserează elementul newChar în stivă.
    * @param stack stiva la care se adaugă elementul.
    * @param newChar elementul ce trebuie adăugat.
    */
   void arrayStackPush(struct ArrayStack * stack, char newChar);
   
   /**
    * Functia extrage următorul element din stivă.
    * @param stack stiva din care se extrage elementul.
    * @return următorul element din stivă sau 0 dacă stiva este goală.
    */
   char arrayStackPop(struct ArrayStack * stack);
   
   /**
    * Functia întoarce următorul element din stivă, fără a-l extrage.
    * @param stack stiva din care se vizualizează elementul.
    * @return următorul element din stivă sau 0 dacă stiva este goală.
    */
   char arrayStackPeek(struct ArrayStack * stack);
   
   /**
    * Functia dezalocă memoria folosită de stiva specificată.
    * @param stack stiva care trebuie ștearsă.
    */
   void deleteArrayStack(struct ArrayStack * stack);
   

   Implementați funcțiile definite în header într-un fișier arrayStack.c.

2. Scrieți o altă sursă, main.c în care să citiți un cuvânt de la tastatură și apoi să-l afișați inversat pe ecran, folosind o stivă.