Pila (informtica)

Pila (informtica)
Una pila (stack en ingls) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del ingls 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 informtica debido a su simplicidad y ordenacin implcita de la propia estructura. Para el manejo de los datos se cuenta con dos operaciones bsicas: apilar (push), que coloca un objeto en la pila, y su operacin inversa, retirar (o desapilar, pop), que retira el ltimo elemento apilado. En cada momento slo se tiene acceso a la parte superior de la pila, es decir, al ltimo objeto apilado (denominado TOS, Top of Stack en ingls). La operacin retirar permite la obtencin 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 analoga con objetos cotidianos, una operacin apilar equivaldra a colocar un plato sobre una pila de platos, y una operacin retirar a retirarlo. Las pilas suelen emplearse en los siguientes contextos: Evaluacin de expresiones en notacin postfija (notacin polaca inversa). Reconocedores sintcticos de lenguajes independientes del contexto Implementacin de recursividad.

Historia
El mtodo de pila para la evaluacin de expresiones fue propuesto en 1955 y dos aos despus patentado por Fiedrich L.Bauer, quin recibi en 1988 el premio "IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos.

Pila como tipo abstracto de datos

A modo de resumen tipo de datos, la pila es un contenedor de nodos y tiene dos operaciones bsicas: push (o apilar) y pop (o desapilar). 'Push' aade 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 metfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetera con muelle de pila. En esa serie, slo la primera placa es visible y accesible para el usuario, todas las dems placas permanecen ocultas. Como se aaden 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 metfora: En primer lugar la ltima salida es un principio, la segunda es que el contenido de la pila est oculto. Slo 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 tendrn que ser retirados.

Pila (informtica)

Operaciones
Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen aadir ms de uso habitual. Crear: se crea la pila vaca. (constructor) Tamao: regresa el numero de elementos de la pila. (size) Apilar: se aade 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) Vaca: devuelve cierto si la pila est vaca o falso en caso contrario (empty).

Implementacin
Un requisito tpico de almacenamiento de una pila de n elementos es O(n). El requisito tpico de tiempo de O(1) las operaciones tambin son fciles de satisfacer con un array o con listas enlazadas simples. La biblioteca de plantillas de C++ estndar proporciona una "pila" clase templated que se limita a slo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especializacin de Vector. Esto podra ser considerado como un defecto, porque el diseo heredado get () de Vector mtodo LIFO ignora la limitacin de la Pila. Estos son ejemplos sencillos de una pila con las operaciones descritas anteriormente (pero no hay comprobacin de errores). Implementacin en Python class Stack(object): def __init__(self): self.stack_pointer = None def push(self, element): self.stack_pointer = Node(element, self.stack_pointer) def pop(self): e = self.stack_pointer.element self.stack_pointer = self.stack_pointer.next return e def peek(self): return self.stack_pointer.element def __len__(self): i = 0 sp = self.stack_pointer while sp: i += 1 sp = sp.next return i class Node(object): def __init__(self, element=None, next=None):

Pila (informtica) self.element = element self.next = next if __name__ == '__main__': # small use example s = Stack() for i in range(10):s.push(i) for i in range(len(s)):print(s.pop()) Implementacin en Maude La PilaNV es la pila no vaca, que diferenciamos de la pila normal a la hora de tomar en cuenta errores. El elemento X representa el tipo de valor que puede contener la pila: entero, carcter, registro, etc. fmod PILA-GENRICA {X :: TRIV} is sorts Pila{X} PilaNV{X}. subsorts PilaNV{X} < Pila{X}. ***generadores: op crear: -> Pila {X} [ctor]. op apilar : X$Elt Pila{X} -> PilaNV{X} [ctor]. ***constructores op desapilar : Pila{X} -> Pila{X}. ***selectores op cima : PilaNV{X} -> X$Elt. ***variables var P : Pila{X}. var E : X$Elt. ***ecuaciones eq desapilar (crear) = crear. eq desapilar(apilar(E, P)) = P. eq cima(apilar(E, P)) = E. endfm Implementacin en Visual Basic Public Class Stack Private p_index As Integer Private list As New ArrayList Public Sub New() p_index = -1 End Sub ReadOnly Property count

Pila (informtica) Get Return list.Count End Get End Property Public Sub push(ByVal value As Object) list.Add(value) p_index += 1 End Sub Public Function pop() As Object Dim obj As Object = list.Item(p_index) list.RemoveAt(p_index) p_index -= 1 Return obj End Function Public Sub clear() list.Clear() p_index = -1 End Sub Public Function peek() As Object Return list.Item(p_index) End Function End Class En C++ #ifndef PILA #define PILA // define la pila

template <class T> class Pila { private: struct Nodo { T elemento; Nodo* siguiente; // coloca el nodo en la segunda posicion }* ultimo; unsigned int elementos; public: Pila() { elementos = 0; }

Pila (informtica) ~Pila() { while (elementos != 0) pop(); } void push(const T& elem) { Nodo* aux = new Nodo; aux->elemento = elem; aux->siguiente = ultimo; ultimo = aux; ++elementos; } void pop() { Nodo* aux = ultimo; ultimo = ultimo->siguiente; delete aux; --elementos; } T cima() const { return ultimo->elemento; } bool vacia() const { return elementos == 0; } unsigned int altura() const { return elementos; } };

#endif

Estructuras de datos relacionadas

El tipo base de la estructura FIFO (el primero en entrar es el primero en salir)es la cola, y la combinacin de las operaciones de la pila y la cola es proporcionado por el deque. Por ejemplo, el cambio de una pila en una cola en un algoritmo de bsqueda puede cambiar el algoritmo de bsqueda en primera profundidad (en ingls, DFS) por una bsqueda en amplitud (en ingls, BFS). Una pila acotada es una pila limitada a un tamao mximo impuesto en su especificacin.

Pila (informtica)

Pilas Hardware
Un uso muy comn de las pilas a nivel de arquitectura hardware es la asignacin de memoria.

Arquitectura bsica de una pila

Una pila tpica es un rea de la memoria de los computadores con un origen fijo y un tamao variable. Al principio, el tamao de la pila es cero. Un puntero de pila, por lo general en forma de un registro de hardware, apunta a la ms reciente localizacin en la pila; cuando la pila tiene un tamao de cero, el puntero de pila de puntos en el origen de la pila. Las dos operaciones aplicables a todas las pilas son: Una operacin apilar, en el que un elemento de datos se coloca en el lugar apuntado por el puntero de pila, y la direccin en el puntero de pila se ajusta por el tamao de los datos de partida. Una operacin desapilar: un elemento de datos en la ubicacin actual apuntado por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamao de los datos de partida. Hay muchas variaciones en el principio bsico de las operaciones de pila. Cada pila tiene un lugar fijo en la memoria en la que comienza. Como los datos se aadirn 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 aplicacin concreta). Por ejemplo, una pila puede comenzar en una posicin 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 nmero limitado de direcciones, ya sea por encima o por debajo del origen (dependiendo de la direccin 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 direccin 1000 y la pila crece hacia abajo (hacia las direcciones 999, 998, y as sucesivamente), el puntero de pila nunca debe ser incrementado ms all de 1000 (para 1001, 1002, etc.) Si un desapilar operacin en la pila hace que el puntero de pila se deje atrs el origen de la pila, una pila se produce desbordamiento. Si una operacin de apilar hace que el puntero de pila incremente o decremente ms all del mximo 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 mximo elemento de la pila en una posicin fija, o creciente, de izquierda a derecha, por lo que el mximo elemento se convierte en el mximo a "la derecha". Esta visualizacin 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 posicin, la segunda a la primera y la tercera a la segunda. Aqu hay dos equivalentes visualizaciones de este proceso: Manzana Pltano Fresa Fresa Pltano Manzana ==rotar a la izquierda==> ==rotar a la derecha==> Pltano Fresa Manzana Manzana Fresa Pltano

Pila (informtica) Una pila es normalmente representada en los ordenadores por un bloque de celdas de memoria, con los "de abajo" en una ubicacin fija, y el puntero de pila de la direccin actual de la "cima" de clulas de la pila. En la parte superior e inferior se utiliza la terminologa 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 tamao de elementos (ya sea decrementar o incrementar, en funcin de la direccin en que crece la pila en la memoria), que apunta a la prxima celda, y copia el nuevo elemento de la cima en rea de la pila. Dependiendo de nuevo sobre la aplicacin exacta, al final de una operacin de apilar, el puntero de pila puede sealar a la siguiente ubicacin no utilizado en la pila, o tal vez apunte al mximo elemento de la pila. Si la pila apunta al mximo 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 prxima ubicacin disponible en la pila, que se actualizar despus de que el mximo 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 operacin de apilar.

Soporte de Hardware
Muchas CPUs tienen registros que se pueden utilizar como punteros de pila. Algunos, como el Intel x86, tienen instrucciones especiales que implcitamente el uso de un registro dedicado a la tarea de ser un puntero de pila. Otros, como el DEC PDP-11 y de la familia 68000 de Motorola tienen que hacer frente a los modos de hacer posible la utilizacin de toda una serie de registros como un puntero de pila. La serie Intel 80x87 numrico de coprocessors tiene un conjunto de registros que se puede acceder ya sea como una pila o como una serie de registros numerados. Algunos microcontroladores, por ejemplo algunos PICs, tienen un fondo fijo de pila que no es directamente accesible. Tambin hay una serie de microprocesadores que aplicar una pila directamente en el hardware: Computer vaqueros MuP21 Harris RTX lnea Novix NC4016 Muchas pilas basadas en los microprocesadores se utilizan para aplicar el lenguaje de programacin Forth en el nivel de microcdigo. Pila tambin se utilizaron como base de una serie de mainframes y miniordenadores. Esas mquinas fueron llamados pila de mquinas, el ms famoso es el Burroughs B5000

Soporte de Software
En programas de aplicacin escrito en un lenguaje de alto nivel, una pila puede ser implementada de manera eficiente, ya sea usando vectores o listas enlazadas. En LISP no hay necesidad de aplicar la pila, puesto que las funciones apilar y desapilar estn disponibles para cualquier lista. Adobe PostScript tambin est diseada en torno a una pila que se encuentra directamente visible y manipuladas por el programador. El uso de las pilas est muy presente en el desarrollo de software por ello la importancia de las pilas como tipo abstracto de datos.

Expresin de evaluacin y anlisis sintctico

Se calcula empleando la notacin polaca inversa utilizando una estructura de pila para los posibles valores. Las expresiones pueden ser representadas en prefijo, infijo, postfijo. La conversin de una forma de la expresin 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 cdigo de bajo nivel. La mayora de los lenguajes de programacin son de contexto libre de los idiomas que les permite ser analizados con mquinas basadas en la pila. Por ejemplo, el clculo: ((1 + 2) * 4) + 3, puede ser anotado como en notacin postfija con la ventaja de no prevalecer las normas y los parntesis necesario:

Pila (informtica) 12+4*3+ La expresin 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 operacin. Apilar el resultado. De la siguiente manera (la Pila se muestra despus de que la operacin se haya llevado a cabo): ENTRADA 1 2 + 4 * 3 + OPERACIN Apilar operando Apilar operando Aadir Apilar operando Multiplicar Apilar operando Aadir PILA 1 1, 2 3 3, 4 12 12, 3 15

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

Tiempo de ejecucin de la gestin de memoria

Artculo principal: Pila basada en la asignacin de memoria y Pila mquina. Una serie de lenguajes de programacin estn orientadas a la pila, lo que significa que la mayora definen operaciones bsicas (aadir dos nmeros, la impresin de un carcter) cogiendo sus argumentos de la pila, y realizando de nuevo los valores de retorno en la pila. Por ejemplo, PostScript tiene una pila de retorno y un operando de pila, y tambin tiene un montn de grficos estado y un diccionario de pila. Forth utiliza dos pilas, una para pasar argumentos y una subrutina de direcciones de retorno. El uso de una pila de retorno es muy comn, pero el uso poco habitual de un argumento para una pila legible para humanos es el lenguaje de programacin Forth razn que se denomina una pila basada en el idioma. Muchas mquinas virtuales tambin estn orientadas hacia la pila, incluida la p-cdigo mquina y la mquina virtual Java. Casi todos los entornos de computacin de tiempo de ejecucin de memoria utilizan una pila especial PILA para tener informacin sobre la llamada de un procedimiento o funcin y de la anidacin con el fin de cambiar al contexto de la llamada a restaurar cuando la llamada termina. Ellos siguen un protocolo de tiempo de ejecucin entre el que llama y el llamado para guardar los argumentos y el valor de retorno en la pila. Pila es una forma importante de apoyar llamadas anidadas o a funciones recursivas. Este tipo de pila se utiliza implcitamente por el compilador para apoyar CALL y RETURN estados (o sus equivalentes), y no es manipulada directamente por el programador. Algunos lenguajes de programacin utilizar la pila para almacenar datos que son locales a un procedimiento. El espacio para los datos locales se asigna a los temas de la pila cuando el procedimiento se introduce, y son borradas cuando el procedimiento termina. El lenguaje de programacin C es generalmente aplicado de esta manera. Utilizando la misma pila de los datos y llamadas de procedimiento tiene importantes consecuencias para la seguridad (ver ms abajo), de los que un programador debe ser consciente, a fin de evitar la introduccin de graves errores de seguridad en un programa.

Pila (informtica)

Solucionar problemas de bsqueda

La bsqueda de la solucin de un problema, es independientemente de si el enfoque es exhaustivo u ptimo, necesita espacio en la pila. Ejemplos de bsqueda exhaustiva mtodos son fuerza bruta y backtraking. Ejemplos de bsqueda ptima a explorar mtodos,son branch and bound y soluciones heursticas. Todos estos algoritmos utilizan pilas para recordar la bsqueda de nodos que se han observado, pero no explorados an. La nica alternativa al uso de una pila es utilizar la recursividad y dejar que el compilador sea recursivo (pero en este caso el compilador todava est utilizando una pila interna). El uso de pilas es frecuente en muchos problemas, que van desde almacenar la profundidad de los rboles hasta resolver crucigramas o jugar al ajedrez por ordenador. Algunos de estos problemas pueden ser resueltos por otras estructuras de datos como una cola.

Seguridad
La seguridad a la hora de desarrollar software usando estructuras de datos de tipo pila es un factor a tener en cuenta debido a ciertas vulnerabilidad que un uso incorrecto de stas puede originar en la seguridad de nuestro software o en la seguridad del propio sistema que lo ejecuta. Por ejemplo, algunos lenguajes de programacin usan una misma pila para almacenar los datos para un procedimientos y el link que permite retornar a su invocador. Esto significa que el programa introduce y extrae los datos de la misma pila en la que se encuentra informacin crtica con las direcciones de retorno de las llamadas a procedimiento, supongamos que al introducir datos en la pila lo hacemos en una posicin errnea de manera que introducimos una datos de mayor tamao al soportado por la pila corrompiendo as las llamadas a procedimientos provocariamos un fallo en nuestro programa. sta tcnica [1] usada de forma maliciosa (es similar, pero en otro mbito al buffer overflow) permitira a un atacante modificar el funcionamiento normal de nuestro programa y nuestro sistema, y es al menos una tcnica til si no lo evitamos en lenguajes muy populares como el ejemplo C++.

Referencias
[1] http:/ / www. cs. ucla. edu/ ~palsberg/ paper/ sas03. pdf

Fuentes y contribuyentes del artculo

10

Fuentes y contribuyentes del artculo

Pila (informtica) Fuente: http://es.wikipedia.org/w/index.php?oldid=57336180 Contribuyentes: AchedDamiman, Andreasmperu, Biasoli, David f.1993, Diegusjaimes, Ealmagro, Emijrp, Ezarate, Farisori, Fernd, Fortran, GCaracuel, Gbduende, GermanX, Greek, Jesuja, Jkbw, Juan Mayordomo, Kn, Laura Fiorucci, LyingB, Martaka, Matdrodes, Phaetton, Poco a poco, Plux, Rbonvall, Rjelves, Sebado, Shooke, Sire, Sirpuppet, Sms, Technopat, Vivero, Wilfredor, 100 ediciones annimas

Fuentes de imagen, Licencias y contribuyentes

Archivo:stack.png Fuente: http://es.wikipedia.org/w/index.php?title=Archivo:Stack.png Licencia: GNU Free Documentation License Contribuyentes: Foroa, German, Rimshot, Vegpuff, Yonidebest Archivo:Pila de datos.jpg Fuente: http://es.wikipedia.org/w/index.php?title=Archivo:Pila_de_datos.jpg Licencia: Public Domain Contribuyentes: MyName (Martaka)

Licencia
Creative Commons Attribution-Share Alike 3.0 Unported //creativecommons.org/licenses/by-sa/3.0/