Pilas y Colas

Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.

en pocas palabras…

Pila:

Estructura lineal

Acceso de inserción y eliminación  por un solo extremo

Manipulacion:

Meter por un extremo: push(x)
Sacar por el mismo extremo: pop()Representación gráfica de una pila

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.

En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.

Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

Las pilas suelen emplearse en los siguientes contextos:

**Pila como tipo abstracto de datos 😀

A modo de resumen tipo de datos, la pila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop (o desapilar). ‘Push’ añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. ‘Pop’ elimina y devuelve el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería con muelle de pila. En esa serie, sólo la primera placa es visible y accesible para el usuario, todas las demás placas permanecen ocultas. Como se añaden las nuevas placas, cada nueva placa se convierte en la parte superior de la pila, escondidos debajo de cada plato, empujando a la pila de placas. A medida que la placa superior se elimina de la pila, la segunda placa se convierte en la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: En primer lugar la última salida es un principio, la segunda es que el contenido de la pila está oculto. Sólo la placa de la parte superior es visible, por lo que para ver lo que hay en la tercera placa, el primer y segundo platos tendrán que ser retirados.

* Operaciones :$

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

Crear: se crea la pila vacía.

Apilar: se añade un elemento a la pila.(push)

Desapilar: se elimina el elemento frontal de la pila.(pop)

Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)

Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.

**Implementación😮

Un requisito típico de almacenamiento de una pila de n elementos es O(n). El requisito típico de tiempo de O(1) las operaciones también son fáciles de satisfacer con un array o con listas enlazadas simples.

La biblioteca de plantillas de C++ estándar proporciona una “pila” clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.

Estos son ejemplos sencillos de una pila con las operaciones descritas anteriormente (pero no hay comprobación de errores).

Un uso muy común de las pilas a nivel de arquitectura hardware es la asignación de memoria.

Una pila típica es un área de la memoria de los computadores con un origen fijo y un tamaño variable. Al principio, el tamaño de la pila es cero. Un puntero de pila, por lo general en forma de un registro de hardware, apunta a la más reciente localización en la pila; cuando la pila tiene un tamaño de cero, el puntero de pila de puntos en el origen de la pila.

Las dos operaciones aplicables a todas las pilas son:

  • Una operación apilar, en el que un elemento de datos se coloca en el lugar apuntado por el puntero de pila, y la dirección en el puntero de pila se ajusta por el tamaño de los datos de partida.
  • Una operación desapilar: un elemento de datos en la ubicación actual apuntado por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamaño de los datos de partida.

Hay muchas variaciones en el principio básico de las operaciones de pila. Cada pila tiene un lugar fijo en la memoria en la que comienza. Como los datos se añadirán a la pila, el puntero de pila es desplazado para indicar el estado actual de la pila, que se expande lejos del origen (ya sea hacia arriba o hacia abajo, dependiendo de la aplicación concreta).

Por ejemplo, una pila puede comenzar en una posición de la memoria de mil, y ampliar por debajo de las direcciones, en cuyo caso, los nuevos datos se almacenan en lugares que van por debajo de 1000, y el puntero de pila se decrementa cada vez que un nuevo elemento se agrega. Cuando un tema es eliminado de la pila, el puntero de pila se incrementa.

Los punteros de pila pueden apuntar al origen de una pila o de un número limitado de direcciones, ya sea por encima o por debajo del origen (dependiendo de la dirección en que crece la pila), sin embargo el puntero de pila no puede cruzar el origen de la pila. En otras palabras, si el origen de la pila está en la dirección 1000 y la pila crece hacia abajo (hacia las direcciones 999, 998, y así sucesivamente), el puntero de pila nunca debe ser incrementado más allá de 1000 (para 1001, 1002, etc.) Si un desapilar operación en la pila hace que el puntero de pila se deje atrás el origen de la pila, una pila se produce desbordamiento. Si una operación de apilar hace que el puntero de pila incremente o decremente más allá del máximo de la pila, en una pila se produce desbordamiento.

La pila es visualizada ya sea creciente de abajo hacia arriba (como pilas del mundo real), o, con el máximo elemento de la pila en una posición fija, o creciente, de izquierda a derecha, por lo que el máximo elemento se convierte en el máximo a “la derecha”. Esta visualización puede ser independiente de la estructura real de la pila en la memoria. Esto significa que rotar a la derecha es mover el primer elemento a la tercera posición, la segunda a la primera y la tercera a la segunda. Aquí hay dos equivalentes visualizaciones de este proceso:

 Manzana                                            Plátano

 Plátano       ==rotar a la derecha==>              Fresa

 Fresa                                              Manzana

 Fresa                                             Manzana

 Plátano       ==rotar a la izquierda==>           Fresa

 Manzana                                           Plátano

Una pila es normalmente representada en los ordenadores por un bloque de celdas de memoria, con los “de abajo” en una ubicación fija, y el puntero de pila de la dirección actual de la “cima” de células de la pila. En la parte superior e inferior se utiliza la terminología con independencia de que la pila crece realmente a la baja de direcciones de memoria o direcciones de memoria hacia mayores.

Apilando un elemento en la pila,se ajusta el puntero de pila por el tamaño de elementos (ya sea decrementar o incrementar, en función de la dirección en que crece la pila en la memoria), que apunta a la próxima celda, y copia el nuevo elemento de la cima en área de la pila. Dependiendo de nuevo sobre la aplicación exacta, al final de una operación de apilar, el puntero de pila puede señalar a la siguiente ubicación no utilizado en la pila, o tal vez apunte al máximo elemento de la pila. Si la pila apunta al máximo elemento de la pila, el puntero de pila se actualizará antes de que un nuevo elemento se apile, si el puntero que apunta a la próxima ubicación disponible en la pila, que se actualizará después de que el máximo elemento se apile en la pila.

Desapilando es simplemente la inversa de apilar. El primer elemento de la pila es eliminado y el puntero de pila se actualiza, en el orden opuesto de la utilizada en la operación de apilar.

Expresión de evaluación y análisis sintáctico

Se calcula empleando la notación polaca inversa utilizando una estructura de pila para los posibles valores. Las expresiones pueden ser representadas en prefijo, infijo, postfijo. La conversión de una forma de la expresión a otra forma necesita de una pila. Muchos compiladores utilizan una pila para analizar la sintaxis de las expresiones, bloques de programa, etc. Antes de traducir el código de bajo nivel. La mayoría de los lenguajes de programación son de contexto libre de los idiomas que les permite ser analizados con máquinas basadas en la pila.

Por ejemplo, el cálculo: ((1 + 2) * 4) + 3, puede ser anotado como en notación postfija con la ventaja de no prevalecer las normas y los paréntesis necesario:

1 2 + 4 * 3 +

La expresión es evaluada de izquierda a derecha utilizando una pila:

  • Apilar cuando se enfrentan a un operando y
  • Desafilar dos operandos y evaluar el valor cuando se enfrentan a una operación.
  • Apilar el resultado.

De la siguiente manera (la Pila se muestra después de que la operación se haya llevado a cabo):

 ENTRADA         OPERACION                 PILA

 1             Apilar operando             1
 2             Apilar operando             1, 2
 +             Añadir                      3
 4             Apilar operando             3, 4
 *             Multiplicar                 12
 3             Apilar operando             12, 3
 +             Añadir                      15

El resultado final, 15, se encuentra en la parte superior de la pila al final del cálculo.

Expresión de evaluación y análisis sintáctico

Se calcula empleando la notación polaca inversa utilizando una estructura de pila para los posibles valores. Las expresiones pueden ser representadas en prefijo, infijo, postfijo. La conversión de una forma de la expresión a otra forma necesita de una pila. Muchos compiladores utilizan una pila para analizar la sintaxis de las expresiones, bloques de programa, etc. Antes de traducir el código de bajo nivel. La mayoría de los lenguajes de programación son de contexto libre de los idiomas que les permite ser analizados con máquinas basadas en la pila.

______________________________________________________________________________________________________________________

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.

en pocas palabras…

Colas:

Estructura lineal
Acceso de inserción por un extremo y
de eliminación por el otro extremo

Ejemplo de Cola

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

Tipos de colas

Colas circulares (anillos): en las que el último elemento y el primero están unidos.

Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:

Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.

Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:

Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.

Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

 

**Cola circular 🙂

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden cosultarse, añadirse y eliminarse unicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

anillo** en pseudocodigo :D

FUNC CrearCola() : TCola
VARIABLES
cola: TCola
INICIO
        cola.frente <- MAXCOLA
        cola.final <- MAXCOLA
        RESULTADO <- cola
FIN

PROC DestruirCola(&cola: TCola)
INICIO
//No hay q hacer nada
FIN

FUNC ColaLlena(cola: TCola): LÓGICO
INICIO
        RESULTADO <- (cola.final MOD MAXCOLA) + 1 = cola.frente
FIN

FUNC ColaVacia(cola: TCola): LÓGICO
INICIO
        RESULTADO <- cola.final = cola.frente
FIN

PROC MeterCola (&cola: TCola; &e: Telemento; &error: Terror)
VARIABLES
fin: NATURAL
INICIO
        SI ColaLlena(cola) ENTONCES
                error <- ErrorColaLlena
        EN OTRO CASO
                error <- NoError
                fin <- (cola.final MOD MAXCOLA) + 1
                cola.final <- fin
                cola.elementos[fin] <- e
        FINSI
FIN

PROC SacarCola (&cola: TCola; &e: Telemento; &error: Terror)
VARIABLES
        ini: NATURAL
INICIO
        SI ColaVacia(cola) ENTONCES
                error <- ErrorColaLlena
        EN OTRO CASO
                error <- NoError
                ini <- (cola.frente MOD MAXCOLA) + 1
                cola.frente <- ini
                e <- cola.elementos[ini]
        FINSI
FIN


Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.

en otras palabras ...

Una cola con prioridad es una estructura de datos lineal que devuelve los elementos de acuerdo a un valor asociado a ellos (prioridad)

(y no al orden en que fueron insertados). La prioridad puede coincidir con el valor del elemento, pero también puede diferir de él.

 

Este tipo especial de colas tienen las mismas operaciones que las colas , pero con la condición de que los elementos se atienden en orden de prioridad.

Ejemplos de la vida diaria serían la sala de urgencias de un hospital, ya que los enfermos se van atendiendo en función de la gravedad de su enfermedad.

Entendiendo la prioridad como un valor numérico y asignando a altas prioridades valores pequeños, las colas de prioridad nos permiten añadir elementos en cualquier orden y recuperarlos de menor a mayor.

Hay 2 formas de implementación:

Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.

Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

Tipos

Colas de prioridades con ordenamiento ascendente: en ellas los elementos se insertan de forma arbitraria, pero a la hora de extraerlos, se extrae el elemento de menor prioridad.

Colas de prioridades con ordenamiento descendente: son iguales que la colas de prioridad con ordenamiento ascendente, pero al extraer el elemento se extrae el de mayor prioridad.

Operaciones

Las operaciones de las colas de prioridad son las mismas que las de las colas genéricas:

Crear: se crea la cola vacía.

Encolar: se añade un elemento a la cola, con su correspondiente prioridad.

Desencolar: se elimina el elemento frontal de la cola.

Frente: se devuelve el elemento frontal de la cola.

Destruye: elimina la cola de memoria.

 

La bicola o doble cola es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola.

Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada.

Todas las operaciones de este tipo de datos tienen coste constante.

Ver animaciones de colas:
http://courses.cs.vt.edu/
csonline/DataStructures/
Lessons/
QueuesImplementationView/
applet.html
http://www.cs.usask.ca/
resources/tutorials/
csconcepts/1998_2/queues/java/

Referencias

http://www.it.uc3m.es/java/prog/units/pilas-colas/guides/index_es.html

http://www.it.uc3m.es/java/prog/units/pilas-colas/guides/index_es.html#idp22688

http://www.it.uc3m.es/java/prog/units/pilas-colas/guides/1/guide_es.html

http://es.wikipedia.org/wiki/Pila_%28estructura_de_datos%29

http://es.wikipedia.org/wiki/Cola_%28estructura_de_datos%29

http://es.wikipedia.org/wiki/Cola_circular

http://es.wikipedia.org/wiki/Cola_de_prioridad_%28estructura_de_datos%29

http://es.wikipedia.org/wiki/Bicolas

 

1 comentario (+¿añadir los tuyos?)

  1. Elisa Schaeffer
    Jul 08, 2011 @ 13:33:42

    Muy bien; 10.

    Responder

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: