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,

...