Diferència entre pila i cua
Content
- Gràfic de comparació
- Definició de Pila
- Exemple
- Definició de cua
- Exemple
- Implementació de pila
- Implementació de cues
- Operacions en pila
- Operacions en una cua
- Aplicacions de Pila
- Aplicacions de cua
- Conclusió
Stack i Queue són estructures de dades no primitives. Les principals diferències entre la pila i la cua són que la pila utilitza el mètode LIFO (last in first out) per accedir i afegir elements de dades mentre que la cua utilitza el mètode FIFO (First in first out) per accedir i afegir elements de dades.
La pila només té un extrem obert per empènyer i fer aparèixer els elements de dades. D'altra banda, la cua té els dos extrems oberts per obtenir i esborrar els elements de dades.
La pila i la cua són les estructures de dades que s’utilitzen per emmagatzemar elements de dades i es basen en algun equivalent del món real. Per exemple, la pila és una pila de CDs, on podeu treure i inserir un CD a la part superior de la pila de CD. De la mateixa manera, La cua és una cua per a les entrades del teatre on es donarà servei a la persona que es troba en primer lloc, és a dir, es mostrarà la part davantera de la cua i la persona que arribi apareixerà a la part posterior de la cua (extrem posterior de la cua).
- Gràfic de comparació
- Definició
- Diferències claus
- Implementació
- Operacions
- Aplicacions
- Conclusió
Gràfic de comparació
| Bases per a la comparació | Pila | Cua |
|---|---|---|
| Principi de treball | LIFO (últim en primer lloc) | FIFO (Primer a Primera sortida) |
| Estructura | El mateix extrem s’utilitza per inserir i eliminar elements. | Un dels extrems s'utilitza per a la inserció, és a dir, l'extrem posterior i un altre extrem s'utilitza per a la supressió d'elements, és a dir, el frontal. |
| Nombre de punters utilitzats | Un | Dos (En cas de cua simple) |
| Operacions realitzades | Push i Pop | Enqueueu i elimineu |
| Examen de condició buida | Dalt == -1 | Front == -1 || Front == Part posterior + 1 |
| Examen de condició completa | Arriba == Màxim - 1 | Part posterior == Màxim - 1 |
| Variants | No té variants. | Té variants com la cua circular, la cua de prioritat, la cua doblement finalitzada. |
| Implementació | Més senzill | Comparativament complex |
Definició de Pila
Una pila és una estructura de dades lineal no primitiva. És una llista ordenada on s’afegeix el nou element i l’element existent s’elimina només d’un extrem, anomenat com a part superior de la pila (TOS). Com que tota la supressió i inserció en una pila es fa des de la part superior de la pila, l'últim element afegit serà el primer que es tregui de la pila. Per això, la llista s'anomena tipus de llista Last-in-First-out (LIFO).
Tingueu en compte que l'element que s'accedeix sovint a la pila és l'element més alt, mentre que l'últim element disponible es troba a la part inferior de la pila.
Exemple
Alguns de vosaltres podeu menjar galetes (o Poppins). Si se suposa, només es trenca un costat de la coberta i es treuen galetes un per un. Això és el que s’anomena esclatar i, de la mateixa manera, si voleu conservar alguns galets durant un temps després, els introduireu de nou al paquet a través del mateix extrem esquinçat que es diu empeny.
Definició de cua
Una cua és una estructura de dades lineal que entra en la categoria del tipus no primitiu. És un recull d’elements similars. L'addició de nous elements té lloc en un extrem anomenat extrem posterior. De la mateixa manera, la supressió dels elements existents es produeix a l'altre extrem anomenat front-end, i és lògicament un tipus de llista First in first out (FIFO).
Exemple
En el nostre dia a dia ens trobem amb moltes situacions en què esperem el servei desitjat, i així hem de posar-nos en línia d’espera per al nostre torn. Es pot pensar en una cua d'espera com una cua.
- La pila segueix el mecanisme LIFO, d'altra banda, la cua segueix el mecanisme FIFO per afegir i eliminar elements.
- En una pila, s’utilitza el mateix extrem per inserir i eliminar els elements. Per contra, s'utilitzen dos extrems diferents a la cua per inserir i eliminar els elements.
- Com a pila, només hi ha un extrem obert, la qual cosa és la raó per utilitzar un sol punter per referir-se a la part superior de la pila. Però la cua utilitza dos indicadors per referir el final i la part posterior de la cua.
- Stack realitza dues operacions conegudes com a push i pop, mentre que a la cua és conegut com enqueue i dequeue.
- La implementació per pila és més fàcil, mentre que la implementació de cues és complicada.
- La cua té variants com la cua circular, la cua de prioritat, la cua doblada, etc. En canvi, la pila no té variants.
Implementació de pila
La pila es pot aplicar de dues maneres:
- Implementació estàtica utilitza matrius per crear una pila. La implementació estàtica és, encara que, una tècnica sense esforç, però no és una forma flexible de creació, ja que la declaració de la mida de la pila s’ha de fer durant el disseny del programa, després d’aquesta mida no es pot variar. A més, la implementació estàtica no és gaire eficient quant a l'ús de la memòria. Ja que es declara una matriu (per implementar la pila) abans de l'inici de l'operació (en el moment del disseny del programa). Ara si el nombre d’elements que s’han d’ordenar és molt inferior a la pila, es perdrà la memòria assignada estàticament. D’altra banda, si hi ha més nombre d’elements a emmagatzemar a la pila, no podrem canviar la mida de la matriu per augmentar-ne la capacitat, de manera que pugui allotjar elements nous.
- Implementació dinàmica també es diu representació de llistes enllaçades i utilitza els punters per implementar el tipus de pila d'estructura de dades.
Implementació de cues
La cua es pot implementar de dues maneres:
- Implementació estàtica: Si una cua s’implementa mitjançant matrius, el nombre exacte d’elements que volem emmagatzemar a la cua s’ha d’assegurar prèviament, perquè la mida de la matriu s’ha de declarar en el moment del disseny o abans que comenci el processament. En aquest cas, l’inici de la matriu es convertirà en la part davantera de la cua i l’última ubicació de la matriu actuarà com la part posterior de la cua. La relació següent proporciona que els elements sencers existeixen a la cua quan s'implementen mitjançant matrius:
davantera - posterior + 1
Si està "posterior <front", no hi haurà cap element a la cua o la cua sempre estarà buida. - Implementació dinàmica: Implementant cues mitjançant punteros, el principal desavantatge és que un node d'una representació enllaçada consumeix més espai de memòria que un element corresponent a la representació de la matriu. Ja que hi ha almenys dos camps a cada node un per al camp de dades i un altre per emmagatzemar l'adreça del següent node mentre que en representació enllaçada només hi ha un camp de dades. El mèrit d’utilitzar la representació enllaçada es fa evident quan cal inserir o eliminar un element al mig d’un grup d’altres elements.
Operacions en pila
Les operacions bàsiques que es poden operar a la pila són les següents:
- POSAR: quan un nou element s’afegeix a la part superior de la pila es coneix com operació PUSH. En prémer un element a la pila s'inclou l'addició de l'element, ja que el nou element s'inserirà a la part superior. Després de cada operació d’empenta, la part superior s’incrementa un. Si la matriu està plena i no es pot afegir cap element nou, s’anomena condició STACK-FULL o STACK OVERFLOW. FUNCIONAMENT DE PUSH - funció en C:
Es considera pila com a
int stack, top = -1;
void push ()
{
article int;
if (superior <4)
{
f ("Introduïu el número");
exploració ("% d" i element);
superior = superior + 1;
pila = element;
}
més
{
f ("La pila està plena");
}
} - POP: Quan un element s'elimina de la part superior de la pila es coneix com funcionament POP. La pila es redueix un, després de cada operació pop. Si no queda cap element a la pila i es realitza el pop, aleshores es produirà la condició STACK UNDERFLOW, que significa que la pila està buida. FUNCIONAMENT POP - funcions en C:
Es considera pila com a
int stack, top = -1;
void pop ()
{
article int;
if (superior> = 4)
{
ítem = pila;
superior = superior - 1;
f ("El número esborrat és =% d", tema);
}
més
{
f ("La pila està buida");
}
}
Operacions en una cua
Les operacions bàsiques que es poden realitzar a la cua són:
- Enqueue: Per inserir un element en una cua.Encetant la funció d'operació en C:
La cua es declara com a
cua int, Front = -1 i posterior = -1;
void add ()
{
article int;
if (posterior <4)
{
f ("Introduïu el número");
exploració ("% d" i element);
if (front == -1)
{
front = 0;
posterior = 0;
}
més
{
posterior = posterior + 1;
}
cua = element;
}
més
{
f ("La cua està plena");
}
}
- Dequeueu: Per eliminar un element de la cua.Encetant la funció d'operació en C:
La cua es declara com a
cua int, Front = -1 i posterior = -1;
void delete ()
{
article int;
if (davant! = -1)
{
ítem = cua;
if (frontal == posterior)
{
front = -1;
posterior = -1;
}
més
{
frontal = front + 1;
f ("El número esborrat és =% d", tema);
}
}
més
{
f ("La cua està buida");
}
}
Aplicacions de Pila
- Parsatge en un compilador.
- Màquina virtual Java.
- Desfer un processador de textos.
- Botó Enrere en un navegador web.
- Llenguatge PostScript per als principis.
- Implementació de trucades de funció en un compilador.
Aplicacions de cua
- Buffers de dades
- Transferència asíncrona de dades (fitxer IO, canonades, socs).
- Assignació de sol·licituds sobre un recurs compartit (er, processador).
- Anàlisi del trànsit
- Determineu el nombre de caixers que hi ha en un supermercat.
Conclusió
La pila i la cua són estructures de dades lineals que es diferencien de certes maneres com el mecanisme de treball, l'estructura, la implementació, les variants, però ambdues s'utilitzen per emmagatzemar els elements de la llista i realitzar operacions de la llista com l'afegit o l'eliminació dels elements. Tot i que hi ha algunes limitacions de la cua simple que es recupera mitjançant l’ús d’altres tipus de cues.
