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

...