Simularea unei cozi folosind două stive implementate prin clase

Coada reprezintă o structură abstractă de date în care inserarea unui nou element se face într-o parte a cozii, iar eliminarea se face din capătul celălalt. Conceptul de coadă apare în orice sistem în care obiectele sunt servite în ordinea sosirii.

Cele două capete ale cozii îşi iau numele din această paralelă cu rândul de asteptare. Mai precis, capătul de la care sunt eliminate articolele se numeşte cap (head) iar capătul la care se adaugă elementele se numeşte coadă (tail); pentru a evita confuziile, vom folosi în acest scop termenii de început şi sfârşit.

Stiva reprezintă de asemenea o structură abstractă de date, în care singura deosebire faţă de coadă este că inserarea şi eliminarea se fac de la acelaşi capăt.

Principiul folosit pentru a simula o coadă folosindu-ne de cele două stive este următorul:

Considerăm că inserarea, eliminarea şi citirea se fac la capătul de la începutul stivei. Tot ce avem de făcut acum este să încercăm să definim operaţiile de inserare, eliminare şi citire pentru coadă folosindu-ne de cele pentru stivă.

pentru operaţia de inserare consideram că se inserează la începutul cozii deci putem folosi direct funcţia de inserare ( push () ) de la stivă.

pentru operaţiile de eliminare şi citire va trebui să mutăm elementele din prima stivă în cea de-a doua stivă. Pentru a avea o perspectivă cât mai clară în legătură cu această mutare urmăriţi exemplul de mai jos.

acum că avem elementul care trebuie eliminat sau citit apelăm funcţiile referitoare la citire sau eliminare ( top(), pop() ) de la stive.

Pentru fiecare nod din stivă avem nevoie de o structură cu două câmpuri în care un câmp va conţine informaţia din nodul respectiv, iar celălalt va conţine legatura către următorul nod.

typedef int Type; 

//asociem tipului int aliasul Type 

//de asemenea putem asocia orice tip de dată pentru Type 

//singura modificare se va face aici

 typedef struct NodeStack {
 Type info; //informatia continuta in nod
 struct NodeStack *next; //legatura catre nodul urmator
 } NodeStack;

Pentru a nu exista neclarităţi la nivelul codului mai creem o structură care va conţine pointer către primul nod din stivă şi numărul elementelor din stivă.

typedef struct Stack {
 NodeStack *prim; //pointer catre primul element din lista
 int nrElt;  //numarul de elemente in lista
} Stack;

Acum că avem structura definită pentru stivă, trecem la implementarea clasei ce va conţine ca şi metode, operaţiile caracteristice pentru stivă - push(), pop(), top().

class MyStack
{
public:
 MyStack(void);  //constructor
 ~MyStack(void); //destructor
 void pop();       //metodele referitoare la operatiile cu stive
 void push(Type);  //si de asemenea Getters && Setters pentru elementele stivei
 Type top();
 bool isEmpty();
 void setNrElt(int);
 void setPrim(NodeStack*);
 NodeStack* getPrim();
 int getNrElt();
private:
 Stack stack;
};

Având definită clasa MyStack, începem simularea cozii. Pentru aceasta avem nevoie de două obiecte de tip MyStack.

MyStack *stack1 = new MyStack(), *stack2= new MyStack();

Vom stoca informaţiile primite în obiectul stack1 iar obiectul stack2 va fi folosit pentru mutarea elementelor în cazul unei eliminări sau citiri.

Pentru funcţia de înserare în coadă se va folosi funcţia de inserare în stivă:

Type e;
printf("Dati elementul: \n");
scanf("%d",&e);
stack2->push(e);

Pentru funcţiile de eliminare sau citire din coadă avem nevoie sa mutăm elementele din primul obiect în cel de-al doilea şi să afisăm/eliminăm elementul utilizând această secvenţă de cod:

while(!stack1->isEmpty())
{
 stack2->push(stack1->top());
 stack1->pop();
}
printf("Elementul eliminat este %d ",stack2->top());
stack2->pop();
//sau pentru citire
printf("Elementul cel mai vechi este %d",stack2->top());

În cazul în care coada este goala se va afişa un mesaj corespunzător.