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.

Secvența 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 cu liste

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:

struct SimplyLinkedListNode {
    char * string;     // pointer la primul caracter din șir, aceasta este valoarea stocată în nod
    struct SimplyLinkedListNode * next; // pointer la nodul următor.
};

#define UNLIMITED_SIZE (unsigned)-1

struct LinkedListQueue {
    struct SimplyLinkedListNode * firstNode;
    struct SimplyLinkedListNode * lastNode;
    unsigned size;
    unsigned maxSize;
};

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 maxSize care va fi inițializat cu valoarea numărului maxim de elemente din coadă, sau -1 dacă coada este nelimitată. -1 este convertit la valoare fără semn pentru a obține cea mai mare valoare de tip unsigned int. 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.

Crearea unei LinkedListQueue

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

/**
 * Funcția alocă memorie și creeaza un nou LinkedListQueue de o dimensiune maximă specificată.
 * @param maxSize numarul maxim de elemente din coadă sau UNLIMITED_SIZE (-1) dacă aceasta 
 *  este nelimitată.
 * @return pointer la o structura de tip LinkedListQueue. 
 */
struct LinkedListQueue * createLinkedListQueue(unsigned maxSize);

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

1. Se alocă memorie pentru o variabilă de tip struct LinkedListQueue.
2. Se inițializează maxSize cu valoarea din size.
3. Se inițializează size cu 0.
4. Se inițializează firstNode și lastNode cu NULL.
5. Se întoarce adresa variabilei de tip struct LinkedListQueue.