Autómatas definición

UNIVERSIDAD MARIANO GÁLVEZ DE GUATEMALA

Ingeniería en Sistemas de Información y Ciencias
Programación
Ing. Marco Barrientos












Pilas y Colas (Push y Pop)












Eduardo José Marroquín Marroquín 1590-11-1510

02 de Julio del 2,012
Pila
Es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (último enentrar, 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.

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. La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente.

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.

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

Crear: se crea la pila vacía. (constructor)
Tamaño: regresa el número de elementos de la pila. (size)
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 (empty).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.

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 enforma 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 eltamañ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.

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 aderecha, 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

Rota a la derechaPlátano
Plátano

Fresa
Fresa

Manzana

Fresa

Rota a la izquierda


Manzana
Plátano

Fresa
Manzana

Plátano

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:

Evaluación de expresiones en notación postfija...