Pila (Estructura de datos) - Historial de revisiones

Katia pedagogico.pri: /* Historia */

2014-04-25T14:33:58Z

‎Historia

Katia pedagogico.pri: /* Pila de llamadas */

2014-04-25T14:31:18Z

‎Pila de llamadas

Astroboy: Pila (estructura de datos) trasladada a Pila (Estructura de datos)

2012-02-19T00:28:33Z

Pila (estructura de datos) trasladada a Pila (Estructura de datos)

Cruces2 jc en 21:46 7 mar 2011

2011-03-07T21:46:37Z

Humberto0601ad jc en 23:29 21 ene 2011

2011-01-21T23:29:58Z

AlejandroGuerra bnjm: /* Pila de llamadas */

2010-07-21T20:04:35Z

‎Pila de llamadas

AlejandroGuerra bnjm: /* Historia */

2010-07-21T20:03:15Z

‎Historia

Year bot: Removida de referencia

2010-05-31T12:37:08Z

Removida de referencia

Jany barroso en 14:25 28 may 2010

2010-05-28T14:25:35Z

Mostrar los cambios

Year bot: Removida de referencia

2010-05-28T13:30:59Z

Removida de referencia

@@ Línea 17: / Línea 17: @@
 == Historia  ==
-El método de pila para la evaluación de expresiones fue propuesto en [[1955|1955 y]] dos años después patentado por [[Fiedrich L.Bauer]], quien recibió en [[1988]] el premio "[[IEEE Computer Society]] Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos.
+El método de pila para la evaluación de expresiones fue propuesto en [[1955|1955 y]] dos años después patentado por Fiedrich L.Bauer, quien recibió en [[1988]] el premio "IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos.
 == Pila de llamadas  ==

@@ Línea 21: / Línea 21: @@
 == Pila de llamadas  ==
-La[[Pila de llamadas|pila de llamadas]] es un segmento de [[Memoria de ordenador|memoria]] que utiliza esta estructura de datos para almacenar información sobre las llamadas a [[Subrutina|subrutinas]] actualmente en ejecución en un [[Programa informático|programa]] en [[Proceso (informática)|proceso]].
+La pila de llamadas es un segmento de [[Memoria RAM|memoria]] que utiliza esta estructura de datos para almacenar información sobre las llamadas a subrutinas actualmente en ejecución en un [[Programa informático|programa]] en [[Proceso informático|proceso]].
-Cada vez que una nueva [[subrutina]] es llamada, se apila una nueva entrada con información sobre ésta tal como sus variables locales. En especial, se almacena aquí el punto de retorno al que regresar cuando esta [[subrutina]] termine (para volver a la [[subrutina]] anterior y continuar su ejecución después de esta llamada)..
+Cada vez que una nueva subrutina es llamada, se apila una nueva entrada con información sobre ésta tal como sus variables locales. En especial, se almacena aquí el punto de retorno al que regresar cuando esta subrutina termine (para volver a la subrutina anterior y continuar su ejecución después de esta llamada)..
 == Pila como tipo abstracto de datos  ==

@@ Línea 1: / Línea 1: @@
-{{Mejorar|Le faltan los hipervínculos, la plantilla, la fuente y separar un poco los párrafos}}'''Pila (informática).'''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. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura. Representación gráfica de una pila
+{{Definición
 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.
@@ Línea 22: / Línea 26: @@
 == Pila como tipo abstracto de datos  ==
+[[Image:pila _estruc.jpg|thumb|left|200px|Estructura de una Pila]]
 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. <br>
@@ Línea 147: / Línea 151: @@
 === Solucionar problemas de búsqueda  ===
+[[Image:pila02.jpg|thumb|left|200px|]]
 La búsqueda de la solución de un problema, es independientemente de si el enfoque es exhaustivo u óptimo, necesita espacio en la pila. Ejemplos de búsqueda exhaustiva métodos son fuerza bruta y backtraking. Ejemplos de búsqueda óptima a explorar métodos,son branch and bound y soluciones heurísticas. Todos estos algoritmos utilizan pilas para recordar la búsqueda de nodos que se han observado, pero no explorados aún. 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 todavía 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.
@@ Línea 154: / Línea 158: @@
 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 programación usan una misma pila para almacenar los datos para un procedimientos y el link que permite retornar a su invocador. Ésto significa que el programa introduce y extrae los datos de la misma pila en la que se encuentra información crítica con las direcciones de retorno de las llamadas a procedimiento, supongamos que al introducir datos en la pila lo hacemos en una posición errónea de manera que introducimos una datos de mayor tamaño al soportado por la pila corrompiendo así las llamadas a procedimientos provocariamos un fallo en nuestro programa. [http://www.cs.ucla.edu/~palsberg/paper/sas03.pdf Ésta técnica] usada de forma maliciosa (es similar pero en otro ámbito al buffer overflow) permitiría a un atacante modificar el funcionamiento normal de nuestro programa y nuestro sistema, y es al menos una técnica útil si no lo evitamos en lenguajes muy populares como el ejemplo C.
-==Fuente==
+== Fuente ==
 [[Category:Estructura_de_datos]] [[Category:Programación]]

@@ Línea 1: / Línea 1: @@
-{{Mejorar|Le faltan los hipervínculos, la plantilla, la fuente y separar un poco los párrafos}}{{Referencia}}'''Pila (informática).'''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. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura. Representación gráfica de una pila
+{{Mejorar|Le faltan los hipervínculos, la plantilla, la fuente y separar un poco los párrafos}}'''Pila (informática).'''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. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura. 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.
@@ Línea 154: / Línea 154: @@
 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 programación usan una misma pila para almacenar los datos para un procedimientos y el link que permite retornar a su invocador. Ésto significa que el programa introduce y extrae los datos de la misma pila en la que se encuentra información crítica con las direcciones de retorno de las llamadas a procedimiento, supongamos que al introducir datos en la pila lo hacemos en una posición errónea de manera que introducimos una datos de mayor tamaño al soportado por la pila corrompiendo así las llamadas a procedimientos provocariamos un fallo en nuestro programa. [http://www.cs.ucla.edu/~palsberg/paper/sas03.pdf Ésta técnica] usada de forma maliciosa (es similar pero en otro ámbito al buffer overflow) permitiría a un atacante modificar el funcionamiento normal de nuestro programa y nuestro sistema, y es al menos una técnica útil si no lo evitamos en lenguajes muy populares como el ejemplo C.
-<br>
+==Fuente==
 [[Category:Estructura_de_datos]] [[Category:Programación]]

@@ Línea 19: / Línea 19: @@
 La[[Pila de llamadas|pila de llamadas]] es un segmento de [[Memoria de ordenador|memoria]] que utiliza esta estructura de datos para almacenar información sobre las llamadas a [[Subrutina|subrutinas]] actualmente en ejecución en un [[Programa informático|programa]] en [[Proceso (informática)|proceso]].
-Cada vez que una nueva subrutina es llamada, se apila una nueva entrada con información sobre ésta tal como sus variables locales. En especial, se almacena aquí el punto de retorno al que regresar cuando esta subrutina termine (para volver a la subrutina anterior y continuar su ejecución después de esta llamada)..
+Cada vez que una nueva [[subrutina]] es llamada, se apila una nueva entrada con información sobre ésta tal como sus variables locales. En especial, se almacena aquí el punto de retorno al que regresar cuando esta [[subrutina]] termine (para volver a la [[subrutina]] anterior y continuar su ejecución después de esta llamada)..
 == Pila como tipo abstracto de datos  ==

← Revisión anterior	Revisión del 00:28 19 feb 2012
(Sin diferencias)

@@ Línea 13: / Línea 13: @@
 == Historia  ==
-El método de pila para la evaluación de expresiones fue propuesto en 1955 y dos años después patentado por Fiedrich L.Bauer, quién recibió en [[1988]] el premio " IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos.
+El método de pila para la evaluación de expresiones fue propuesto en 1955 y dos años después patentado por Fiedrich L.Bauer, quién recibió en [[1988]] el premio &quot; IEEE Computer Society Pioneer Award&quot; por su trabajo en el desarrollo de dicha estructura de datos.
 == Pila de llamadas  ==
@@ Línea 45: / Línea 45: @@
 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.
+La biblioteca de plantillas de C++ estándar proporciona una &quot;pila&quot; 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).
@@ Línea 59: / Línea 59: @@
 La PilaNV es la pila no vacía, 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, carácter, registro....
-fmod PILA-GENERICA {X&nbsp;:: TRIV} is<br> sorts Pila{X} PilaNV{X}.<br> subsorts PilaNV{X} &lt; Pila{X}.<br> <br> ***generadores:<br> op crear: -&gt; Pila {X} [ctor].<br> op apilar&nbsp;: X$Elt Pila{X} -&gt; PilaNV{X} [ctor].<br> <br> ***constructores<br> op desapilar&nbsp;: Pila{X} -&gt; Pila{X}.<br> <br> ***selectores <br> op cima&nbsp;: PilaNV{X} -&gt; X$Elt.<br> <br> ***variables <br> var P&nbsp;: Pila{X}.<br> var E&nbsp;: X$Elt.<br> <br> ***ecuaciones <br> eq desapilar (crear) = crear.<br> eq desapilar(apilar(E, P)) = P.<br> eq cima(apilar(E, P)) = E.<br>endfm<br>
+fmod PILA–GENERICA {X&nbsp;:: TRIV} is<br> sorts Pila{X} PilaNV{X}.<br> subsorts PilaNV{X} &lt; Pila{X}.<br> <br> ***generadores:<br> op crear: –&gt; Pila {X} [ctor].<br> op apilar&nbsp;: X$Elt Pila{X} –&gt; PilaNV{X} [ctor].<br> <br> ***constructores<br> op desapilar&nbsp;: Pila{X} –&gt; Pila{X}.<br> <br> ***selectores <br> op cima&nbsp;: PilaNV{X} –&gt; X$Elt.<br> <br> ***variables <br> var P&nbsp;: Pila{X}.<br> var E&nbsp;: X$Elt.<br> <br> ***ecuaciones <br> eq desapilar (crear) = crear.<br> eq desapilar(apilar(E, P)) = P.<br> eq cima(apilar(E, P)) = E.<br>endfm<br>
 ==== EN C++  ====
-#ifndef PILA<br>#define PILA // define la pila<br><br>template &lt;class T&gt;<br>class Pila {<br><br>private:<br>struct Nodo {<br>T elemento;<br>Nodo* siguiente; // coloca el nodo en la segunda posicion<br>}* ultimo;<br>unsigned int elementos;<br><br>public:<br>Pila() {<br>elementos = 0;<br>}<br><br>~Pila() {<br>while (elementos&nbsp;!= 0) pop();<br>}<br><br>void push(const T&amp; elem) {<br>Nodo* aux = new Nodo;<br>aux-&gt;elemento = elem;<br>aux-&gt;siguiente = ultimo;<br>ultimo = aux;<br>++elementos;<br>}<br><br>void pop() {<br>Nodo* aux = ultimo;<br>ultimo = ultimo-&gt;siguiente;<br>delete aux;<br>--elementos;<br>}<br><br>T cima() const {<br>return ultimo-&gt;elemento;<br>}<br><br>bool vacia() const {<br>return elementos == 0;<br>}<br><br>unsigned int altura() const {<br>return elementos;<br>}<br><br>};<br><br><br>#endif<br>
+#ifndef PILA<br>#define PILA // define la pila<br><br>template &lt;class T&gt;<br>class Pila {<br><br>private:<br>struct Nodo {<br>T elemento;<br>Nodo* siguiente; // coloca el nodo en la segunda posicion<br>}* ultimo;<br>unsigned int elementos;<br><br>public:<br>Pila() {<br>elementos = 0;<br>}<br><br>~Pila() {<br>while (elementos&nbsp;!= 0) pop();<br>}<br><br>void push(const T&amp; elem) {<br>Nodo* aux = new Nodo;<br>aux–&gt;elemento = elem;<br>aux–&gt;siguiente = ultimo;<br>ultimo = aux;<br>++elementos;<br>}<br><br>void pop() {<br>Nodo* aux = ultimo;<br>ultimo = ultimo–&gt;siguiente;<br>delete aux;<br>––elementos;<br>}<br><br>T cima() const {<br>return ultimo–&gt;elemento;<br>}<br><br>bool vacia() const {<br>return elementos == 0;<br>}<br><br>unsigned int altura() const {<br>return elementos;<br>}<br><br>};<br><br><br>#endif<br>
 === Estructuras de datos relacionadas  ===
@@ Línea 88: / Línea 88: @@
 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:
+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 &quot;la derecha&quot;. 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<br> <br> Plátano ==rotar a la derecha==&gt; Fresa<br> <br> Fresa Manzana<br>
@@ Línea 94: / Línea 94: @@
 Fresa Manzana<br> <br> Plátano ==rotar a la izquierda==&gt; Fresa<br> <br> Manzana Plátano<br>
-<br> 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.
+<br> Una pila es normalmente representada en los ordenadores por un bloque de celdas de memoria, con los &quot;de abajo&quot; en una ubicación fija, y el puntero de pila de la dirección actual de la &quot;cima&quot; 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.
@@ Línea 102: / Línea 102: @@
 == Soporte de Hardware  ==
-Muchas [[CPU]]s tienen registros que se pueden utilizar como punteros de pila. Algunos, como el Intel x86, tienen instrucciones especiales que implícitamente 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 utilización de toda una serie de registros como un puntero de pila. La serie Intel 80x87 numérico 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. También hay una serie de microprocesadores que aplicar una pila directamente en el hardware:
+Muchas [[CPU]]s tienen registros que se pueden utilizar como punteros de pila. Algunos, como el Intel x86, tienen instrucciones especiales que implícitamente 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 utilización de toda una serie de registros como un puntero de pila. La serie Intel 80x87 numérico 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. También hay una serie de microprocesadores que aplicar una pila directamente en el hardware:
 *Computer vaqueros MuP21
@@ Línea 140: / Línea 140: @@
 Forth utiliza dos pilas, una para pasar argumentos y una subrutina de direcciones de retorno. El uso de una pila de retorno es muy común, pero el uso poco habitual de un argumento para una pila legible para humanos es el lenguaje de programación Forth razón que se denomina una pila basada en el idioma.
-Muchas máquinas virtuales también están orientadas hacia la pila, incluida la p-código máquina y la máquina virtual Java.
+Muchas máquinas virtuales también están orientadas hacia la pila, incluida la p–código máquina y la máquina virtual Java.
 Casi todos los entornos de computación de tiempo de ejecución de memoria utilizan una pila especial PILA para tener información sobre la llamada de un procedimiento o función y de la anidación con el fin de cambiar al contexto de la llamada a restaurar cuando la llamada termina. Ellos siguen un protocolo de tiempo de ejecución 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 implícitamente por el compilador para apoyar CALL y RETURN estados (o sus equivalentes), y no es manipulada directamente por el programador.