Coada - Utilitatea unei cozi - Inserarea unui element in coada

Coada

Coada este o structura de date abstracta pentru care operatia de inserare a unui element se realizeaza la un capat, in timp ce operatia de extragere a unui element se realizeaza la celalalt capat.

Singurul element din coada la care avem acces este direct cel de la inceput.

Operatii caracteristice

Singurele operatii ce pot fi executate cu o coada sunt:

• crearea unei cozi vide;
• inserarea unui element in coada;
• extragerea unui element din coada;
• accesarea unui element;

Executarea acestor operatii asupra unei cozi presupune cunoasterea inceputului cozii (notat Inc) si a sfarsitului acesteia (notat Sf).

Datorita faptului ca intotdeauna este extras primul element din coada, iar inserarea oricarui nou element se face la sfarsit, coada este definita ca o structura de date care functioneaza dupa principiul FIFO (First In First Out - primul intrat primul iesit).

Utilitatea unei cozi

Utilitatea structurii de tip coada reiese din modul sau de functionare - este necesara uitilizarea unei cozi atunci cand informatiile trebuie prelucrate exact in ordinea in care "au sosit" si ele sunt retinute in coada pana cand pot fi prelucrate. In informatica, cozile sunt utilizate frecvent. De exemplu, sa consideram ca avem o retea de calculatoare si o singura imprimanta. Cand utilizatorii retelei vor da comenzi de tiparire, imprimanta nu poate raspunde tuturor comenzilor in acelasi timp. Prin urmare, comenzile de tiparire primite sunt inregistrate intr-o coada (Print Queue - coada de tiparire). Imprimanta va tipari documentele pe rand, in ordinea in care au fost inregistrate in coada. Un alt exemplu: pentru a mari viteza de executie, microprocesoarele Intel utilizeaza o coada de instructiuni in care sunt memorate instructiunile ce urmeaza a fi executate.

Implementarea unei cozi

coada esteo structura de date abstracte care poate fi implementata in diferite moduri. Ca si in cazul stivei, coada poate fi implementata static, retinand elementele sale intr-un vector.

Sa consideram urmatoarele declaratii care reprezinta o coada cu elemente de tip int alocata static:

#define DimMax 100 //numarul maxim de elemente din coada

typedef int Coada[DimMax]; //tipul coada implementat ca vector

Coada C; //coada

int Inc, Sf; //inceputul si sfarsitul cozii

Elementele cozii sunt memorate in vector de la pozitia Inc pana la pozitia Sf, deci numarul lor este Sf-Inc+1

Crearea unei cozi vide

Pentru a crea o coada vida, trebuie sa initializam variabilele Inc si Sf astfel:

Inc = 0;

Sf = -1;

Se observa ca numarul de elemente din coada este 0, iar pozitia pe care va fi plasat primul element din coada este 0.

Inserarea unui element in coada

Pentru a insera un element x in coada C, trebuie verificat in primul rand daca "este loc", deci daca variabila Sf nu depaseste dimensiunea maxima a vectorului. Daca inserarea se poate face, vom mari valoarea variabilei Sf cu o unitate (coada "creste") si vom plasa la sfarsit noul element.

De exemplu, sa inseram elementul x = 3 in coada din figura urmatoare:

if (sf == DimMax-1) //nu mai este loc

cout<< "Eroare";

else

C[++Sf] = x; inseram elementul x in coada C

Extragerea unui element din coada

Pentru a extrage un element dintr-o coada C, trebuie sa verificam in primul rand daca numarul de elemente din coada este diferit de (coada nu este vida). Daca da, retinem ca elementul de la inceputul cozii intr-o variabila (notata x), dupa care marim cu o unitate inceputul cozii.

De exemplu, sa extragem un element din coada din figura urmatoare:

if (Inc > Sf)

cout<< "Eroare"; //coada este vida

else

x = C[Inc++]; //extragem primul element

Accesarea unui element

Singurul element al unei cozi care poate fi accesat direct este primul. Daca dorim sa aflam valoarea unui alt element, va trebui sa extragem succesiv elemente pana la cel dorit

Accesarea primului element are ca scop determinarea valorii acestuia, valoare care va fi retinuta intr-o variabila denumita x.

x = C[Inc];

Observatie

In acest mod de alocare statica a unei cozi se observa ca, pe masura ce sunt inserate si extrase elemente, atat sfarsitul, cat si inceputul cozii "migreaza" catre limita maxima a vectorului. Dezavantajul este ca in vector raman pozitii neutilizate (de la pana la Inc-1). De exemplu, ar putea sa apara o situatie in care coada contine un element, dar operatia de inserare sa nu fie posibila pentru ca Inc=Sf=DimMax-1. O solutie mai buna ar fi de a reutiliza circular spatiul de memorie alocat cozii. Pentru aceasta, urmatoarea pozitie dupa pozitia i poate fi:

i+1, daca i<DimMax-1

, daca i=DimMax-1

Acest lucru se poate scrie concis: (i+1)%DimMax.