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

De la WikiLabs
Jump to navigationJump to search
 
(Nu s-au afișat 76 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 =
  
 
  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 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.
 +
 +
[[Fișier:queue.png]]
  
 
Coada are următoarele proprietăți:
 
Coada are următoarele proprietăți:
Linia 11: Linia 13:
 
# 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.
 
# 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ă:
+
Coada suportă următoarele operații de bază:
 
# Interogarea numărului de elemente din coadă.
 
# Interogarea numărului de elemente din coadă.
 
# Verificarea dacă coada este goală.
 
# Verificarea dacă coada este goală.
Linia 19: 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 ==
 +
 
 +
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.
 +
 
 +
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:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
#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;
 +
}
 +
</syntaxhighlight>
 +
 
 +
Dacă doriți să utilizați o listă dublu înlănțuită pentru implementarea de cozi, sintaxa este următoarea:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
#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;
 +
}
 +
</syntaxhighlight>
 +
 
 +
== Crearea unui <code>std::queue</code> ==
 +
 
 +
Pentru crearea unei cozi noi, se definește următorul constructor:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Constructorul alocă memorie și creeaza un un nou std::queue.
 +
*/
 +
queue();
 +
</syntaxhighlight>
  
−
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:
+
Exemplu:
  
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
−
struct SimplyLinkedListNode {
+
#include <queue>
−
     char * string;    // pointer la primul caracter din șir, aceasta este valoarea stocată în nod
+
#include <cstdio>
−
     struct SimplyLinkedListNode * next; // pointer la nodul următor.
+
 
−
};
+
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 ==
 +
 
 +
Pentru interogarea dimensiunii, se definește următoarea funcție:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda intoarce numarul de elemente din coada.
 +
* @return numarul de elemente din coada.
 +
*/
 +
uint32_t size();
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<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>
 +
 
 +
== Adăugarea unui element - push ==
 +
 
 +
Pentru adăugarea unui element '''value''' în coadă, se definește următoarea funcție:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda inserează elementul value în coadă.
 +
* @param value elementul ce trebuie adăugat.
 +
*/
 +
void push(T value);
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<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 extragerea unui element din coadă, se definește următoarea metodă:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda elimina următorul element din coadă.
 +
*/
 +
void pop();
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
#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;
 +
}
 +
</syntaxhighlight>
 +
 
 +
== Vizualizarea primului element din coadă - front ==
 +
 
 +
Pentru vizualizarea primului element din coadă, fără a-l extrage, se definește următoarea metodă:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda întoarce următorul element din coadă, fără a-l extrage.
 +
* @return următorul element din coadă
 +
*/
 +
T front();
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
#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;
 +
}
 +
</syntaxhighlight>
 +
 
 +
= 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.
 +
 
 +
[[Fișier:stack.png]]
 +
 
 +
Stiva are următoarele proprietăți:
 +
# Datele sunt stocate într-o anumită ordine (se poate spune că un element este plasat înaintea sau după un alt element în structură).
 +
# Numărul de elemente ce poate fi stocat de structură este nelimitat sau limitat, în funcție de implementare.
 +
# Elementele stocate în stivă sunt de același fel.
 +
# 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ă:
 +
# Interogarea numărului de elemente din stivă.
 +
# Verificarea dacă stiva este goală.
 +
# Verificarea dacă stiva este plină (pentru stive limitate).
 +
# Adăugarea unui element în stivă (''push'').
 +
# Extragerea unui element din stivă (''pop'').
 +
# Vizualizarea unui element din stivă fără extragerea acestuia (''peek'').
 +
 
 +
== Implementarea stivei ==
 +
 
 +
Î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>.
 +
 
 +
== Crearea unui obiect de tip <code>std::stack</code> ==
  
−
#define UNLIMITED_SIZE -1
+
Pentru crearea unei stive noi, se definește următorul constructor:
  
−
struct LinkedListQueue {
+
<syntaxhighlight lang="cpp">
−
    struct SimplyLinkedListNode * firstNode;
+
/**
−
    struct SimplyLinkedListNode * lastNode;
+
* Constructorul alocă memorie și creeaza o noua stiva.
−
    unsigned size;
+
*/
−
    unsigned maxSize;
+
stack();
−
};
 
 
</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 -1 dacă coada este nelimitată.
+
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="6">
 +
#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;
 +
}
 +
</syntaxhighlight>
  
−
== Crearea unei <code>LinkedListQueue</code> ==
+
== Interogarea dimensiunii ==
  
−
Pentru crearea unei cozi noi, se definește următoarea funcție:
+
Pentru interogarea dimensiunii, se definește următoarea metodă:
  
−
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 +
/**
 +
* 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();
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="18,20">
 +
#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;
 +
}
 +
</syntaxhighlight>
 +
 
 +
== Adăugarea unui element - push ==
 +
 
 +
Pentru adăugarea unui element '''value''' în stivă, se definește următoarea metodă:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda inserează elementul value în stivă.
 +
* @param value elementul ce trebuie adăugat.
 +
*/
 +
void push(T value);
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="7-16">
 +
#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;
 +
}
 +
</syntaxhighlight>
 +
 
 +
== Eliminarea unui element - pop ==
 +
 
 +
Pentru eliminarea elementului din vârful stivei, se definește următoarea metodă:
 +
 
 +
<syntaxhighlight lang="cpp">
 +
/**
 +
* Metoda elimina următorul element din stivă.
 +
*/
 +
void pop();
 +
</syntaxhighlight>
 +
 
 +
Exemplu:
 +
 
 +
<syntaxhighlight lang="cpp" highlight="22">
 +
#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;
 +
}
 +
</syntaxhighlight>
 +
 
 +
== Vizualizarea primului element din stivă - top ==
 +
 
 +
Pentru vizualizarea primului element din stivă, fără a-l extrage, se definește următoarea metodă:
 +
 
 +
<syntaxhighlight lang="cpp">
 
/**
 
/**
−
  * Funcția alocă memorie și creeaza un nou LinkedListQueue 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 (-1) dacă aceasta
+
  * @return următorul element din stivă.
−
*  este nelimitată.
 
−
  * @return pointer la o structura de tip LinkedListQueue.  
 
 
  */
 
  */
−
struct LinkedListQueue * createLinkedListQueue(unsigned maxSize);
+
T top();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
Implementarea acestei funcții se face folosind următorul algoritm:
+
Exemplu:
−
# Se alocă memorie pentru o variabilă de tip <code>struct LinkedListQueue</code>.
+
 
−
# Se inițializează <code>maxSize</code> cu valoarea din <code>size</code>.
+
<syntaxhighlight lang="cpp" highlight="21">
−
# Se inițializează <code>size</code> cu 0.
+
#include <stack>
−
# Se inițializează <code>firstNode</code> și <code>lastNode</code> cu <code>NULL</code>.
+
#include <cstdio>
−
# Se întoarce adresa variabilei de tip <code>struct LinkedListQueue</code>.
+
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;
 +
}
 +
</syntaxhighlight>

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;
}
Adus de la „http://wiki.dcae.pub.ro/index.php?title=SDA_Lucrarea_4&oldid=5395”