Pilas, Colas Y Listas

INDICE

Cont. Pág.

Introducción………………………………………………………………..… 5

Definición de Pilas………..………………………………………………...... 6

Construcción…...……………………………………………………….…..... 6

Implementación……..…………………………………………………...…… 9

Operaciones………………………………………………………………...… 10

Definición de Cola…...…………………………………………………...….. 10

Implementación……………………………………………………………..... 11

Operaciones………………………………………………………………...… 11

Definición de lista………………………………………………………..…... 11

Implementación………………………………………………………...…….. 12

Operaciones……………………………………………………………...…… 12

Anexos………………………………………………………………….......… 13

• Implementación de pilas………………………………..……. 13

o En Python……………………………………...…....... 13

o En Maude……………………………………...…...… 14

o En Visual Basic……………………………..……...... 14

o En C++………………………………………….…… 15

• Implementación de colas………………………………....….. 16

o Basadas en Celdas Enlazadas…………………….….. 16

o En Maude………………………………………….…. 17

o En C++………………………………………….....… 18

• Implementación de listas…………………………………….. 19

o Listas enlazadas lineales…………………………….. 19

 Listas simples enlazadas…………………….. 19

 Listas doblemente enlazadas..……………….. 21

o Listas enlazadas circulares…………………………... 23

 Listas enlazadas doblemente circulares…..… 23

o Listas enlazadas usando vectores de nodos…..…….. 25

o Lista enlazada en C………………………………...... 25

o Lista enlazada en Maude………………………....…. 27

Conclusión……………………………………………………………........... 29

Referencias bibliográficas……………………………………………...…… 30

INTRODUCCION

Una pila es una estructura de datos que permite almacenar y recuperar datos, fue propuesta en 1955 y dos años mas tarde patentado por Fiedrich L.Bauer. 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.

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 teoría de colas generalmente es considerada una rama de investigación operativa porque sus resultados a menudo son aplicables en una amplia variedad de situaciones como negocios, comercio, industria, ingenierías, transporte y telecomunicaciones.

El matemático danés Agner Krarup Erlang, trabajador de la Copenhagen Telephone Exchange, publicó el primer artículo sobre la teoría de colas en 1909.1 Específicamente se preocupó del estudio del problema de dimensionamiento de líneas y centrales de conmutación telefónica para el servicio de llamadas.

Las listas enlazadas fueron desarrolladas en 1955-56 por Cliff Shaw y Herbert Simon en RAND Corporation, como la principal estructura de datos para su Lenguaje de Procesamiento de la Información (IPL). IPL fue usado por los autores para desarrollar varios programas relacionados con la inteligencia artificial, incluida la Máquina de la Teoría General, el Solucionador de Problemas Generales, y un programa informático de ajedrez.

DEFINICION DE PILA

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.

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:

• Evaluación de expresiones en notación postfija (notación polaca inversa).

• Reconocedores sintácticos de lenguajes independientes del contexto

• Implementación de recursividad.

CONSTRUCCION

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 decremento 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 desapilar la 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"

...