Coda (informatică)
Această intrare sau secțiune despre limbaje de programare nu menționează sursele necesare sau cei prezenți sunt insuficienți . |
În informatică, o coadă înseamnă un FIFO tip structură de date , F ima I n F ima O ut (primul care a intrat este primul exit).
Un exemplu practic îl reprezintă cozile pe care le faceți pentru a obține un serviciu, cum ar fi să plătiți la supermarket sau să vă tundeți de coafor: în mod ideal sunteți servit în aceeași ordine în care sunteți prezentat. Exact așa funcționează o coadă FIFO.
Acest tip de structură de date este utilizat pe scară largă în informatică , de exemplu în gestionarea operațiunilor care trebuie efectuate de un sistem de operare ( programator ) și este fundamental în telecomunicații , în special în rețelele cu comutare de pachete , unde descrie gestionarea pachetelor așteaptă să fie transmis prin intermediul unui link de la un server la un client . Proprietățile matematico-statistice ale cozilor sunt studiate în teoria cozilor .
Descriere
Operațiune pe o coadă
- În așteptarea unui articol
- De asemenea , numit de operare Puneți în coadă, este folosit la coadă un element.
- Verificați un articol
- De asemenea , numit operațiunea dequeue, este utilizat pentru a elimina un element din capul cozii.
Tipuri de implementare
O listă legată este utilizată în mod normal pentru a implementa o coadă.
Fiecare element al listei este un element al cozii, și din moment ce coada este un FIFO structură de date, F ima I n F irst O ut, inserarea unui element apare in coada listei (adică după ultimul element) pentru operația de coadă, în timp ce îndepărtarea unui element are loc pe cap (primul element) pentru operația de coadă. Pentru a realiza acest comportament, lista conține două indicii, unul pentru cap și unul pentru coadă. Când lista are un singur element cap și coadă coincid.
Un alt tip de implementare a structurii de date a cozii utilizează o matrice circulară. Matricea circulară este indexată printr-un index de start și un index de sfârșit, sau printr-un index de start și offset-ul sfârșitului de la început, care sunt actualizate prin aritmetică modulară pentru a crea o structură circulară în care ultimul element este contigu cu primul.
Implementarea cozii în java prin listă legată
Iată o implementare simplă a cozii cu o listă legată:
class Node < E > { // clasă de nod generică a listei
element E privat ;
nod privat următor ;
nod public ( element E ) {
acesta ( element , nul );
}
nod public ( element E , nod următor ) {
aceasta . element = element ;
aceasta . next = next ;
}
public void setNext ( nodul următor ) {
aceasta . next = next ;
}
public ȘI getElement () {
element de returnare ;
}
nod public getNext () {
întoarce-te în continuare ;
}
public String toString () {
element return ( String ) ;
}
}
clasă LinkedList < E > {
capul nodului privat , coada ; // noduri santinelă unul pentru cap și celălalt pentru coadă
dimensiunea int protejată ;
public LinkedList () { // constructor
cap = coadă = nul ;
dimensiune = 0 ;
}
public void addToTail ( element E ) { // adaugă la coadă
Nod Nod = nou nod (elementul);
if ( tail == nul )
{
cap = coadă = nod ;
}
altceva
{
coada . setNext ( nod );
coada = nod ;
}
dimensiune ++ ;
}
public ȘI removeToHead () {
E element = nul ;
if ( dimensiune == 0 ) Sistem . afară . println ( "eroare de coadă goală" ); // eroare de imprimare;
altceva {
element = ( E ) cap . getElement ();
cap = cap . getNext ();
dimensiune - ;
}
element de returnare ;
}
public String toString () {
StringBuilder str = new StringBuilder ();
if ( dimensiune ! = 0 ) {
Nod tmp = cap ;
while ( tmp ! = nul ) {
str . append ( tmp . toString ());
tmp = tmp . getNext ();
}
}
return str . toString ();
}
}
coadă de clasă publică < E > {
listă privată LinkedList < E > ;
coadă publică () {
list = new LinkedList < E > ();
}
dimensiunea int public () {
lista de returnare . dimensiune ;
}
void publice Puneți în coadă (elementul E) {
listă . addToTail ( element );
}
public E dequeue () {
lista de returnare . removeToHead ();
}
public String toString () {
lista de returnare . toString ();
}
}
Implementarea codei în java cu matrice circulară
Iată o simplă implementare Java a unei cozi cu o matrice circulară. Folosește o matrice și doi indici, unul pentru cap și unul pentru coadă, astfel încât primul și ultimul element inserat să poată fi luat în considerare. Când un index ajunge la sfârșitul matricei, acesta este readus în poziția [0] pentru a crea o structură circulară.
// CAP <- O <- O <- O <- O <- O COADA
// Enqueue (inserarea cozii)
// Dequeue (extragerea din cap)
// head = tail -> Coadă goală
public class ArrayQueue < E >
{
private int cap , coadă ;
private int size , n ;
privat static final int CAPACITATE = 1000 ;
privat E [] q ;
public ArrayQueue () {
aceasta ( CAPACITATE );
}
public ArrayQueue ( capacitate int )
{
cap = coadă = 0 ;
dimensiune = 0 ;
n = capacitate ;
q = ( E [] ) Obiect nou [ capacitate ] ;
}
coadă de gol public ( element E )
{
if ( dimensiune == n ) {
Sistem . afară . println ( "eroare completă la coadă" );
întoarcere ;
}
q [ coada ] = element ;
coadă = ( coadă + 1 ) % n ; // (utilizați modulul pentru a gestiona indexurile într-o manieră circulară - sdf)
dimensiune ++ ;
}
public E dequeue ()
{
if ( dimensiune == 0 ) {
Sistem . afară . println ( "eroare de coadă goală" );
returnare nulă ;
}
Și tmp = q [ cap ] ;
q [ cap ] = nul ;
head = ( head + 1 ) % n ; // (utilizați modulul pentru a gestiona indexurile într-o manieră circulară - sdf)
dimensiune - ;
retur tmp ;
}
public boolean isEmpty ()
{
retur dimensiune == 0 ;
}
public String toString ()
{
StringBuilder str = new StringBuilder ( "" );
int cont = 0 ;
pentru ( element E : q )
{
if ( element ! = nul )
{
str . append ( element ); cont ++ ;
if ( cont < dimensiune )
str . append ( "\ n" );
}
}
return str . toString ();
}
}
Elemente conexe
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere în coadă
