Pilas Colas Listas - Apuntes Unidad 3 PDF

Preview

Summary

Pilas, colas y listas...

Description

Tabla de contenido Pilas

3

Representación en memoria 3 Operaciones Básicas 4 Aplicaciones 4

Colas

6

Representación en memoria 6 Operaciones Básicas 6 Tipos de colas: Simples, Circulares y Bicolas 7 Aplicaciones 8

Listas 8 Operaciones Básicas 8 Tipos de Listas: Simplemente enlazadas, Doblemente enlazadas y Circulares 9

1

Pilas Las pilas son estructuras de datos que tienes dos operaciones básicas: push (para insertar un elemento) y pop (para extraer un elemento). Su característica fundamental es que al extraer se obtiene siempre el último elemento que acaba de insertarse. Por esta razón también se conocen como estructuras de datos LIFO (del inglés Last In First Out). Una posible implementación mediante listas enlazadas sería insertando y extrayendo siempre por el principio de la lista. Gracias a las pilas es posible el uso de la recursividad (lo veremos en detalle en el tema siguiente). La variable que llama al mismo procedimiento en el q está, habrá que guardarla, así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de pilas. Las pilas se utilizan en muchas aplicaciones que utilizamos con frecuencia. Por ejemplo, la gestión de ventanas en Windows (cuando cerramos una ventana siempre recuperamos la que teníamos detrás). Otro ejemplo es la evaluación general de cualquier expresión matemática para evitar tener que calcular el número de variables temporales que hacen falta. Por ejemplo:

Representación en memoria Las pilas no son estructuras de datos fundamentales, es decir, no están definidas como tales en los lenguajes de programación. Las pilas pueden representarse mediante el uso de: 

Arreglos.



Listas enlazadas.

Nosotros ahora usaremos los arreglos. Por lo tanto, debemos definir el tamaño máximo de la pila, además de un apuntador al último elemento insertado en la pila el cual denominaremos SP. La representación gráfica de una pila es la siguiente:

2

Como utilizamos arreglos para implementar pilas, tenemos la limitante de espacio de memoria reservada. Una vez establecido un máximo de capacidad para la pila, ya no es posible insertar más elementos. Una posible solución a este problema es el uso de espacios compartidos de memoria. Supóngase que se necesitan dos pilas, cada una con un tamaño máximo de n elementos. En este caso se definirá un solo arreglo de 2*n elementos, en lugar que dos arreglos de n elementos. En este caso utilizaremos dos apuntadores: SP1 para apuntar al último elemento insertado en la pila 1 y SP2 para apuntar al último elemento insertado en la pila 2. Cada una de las pilas insertará sus elementos por los extremos opuestos, es decir, la pila 1 iniciará a partir de la localidad 1 del arreglo y la pila 2 iniciará en la localidad 2n. De este modo si la pila 1 necesita más de n espacios (hay que recordar que a cada pila se le asignaron n localidades) y la pila 2 no tiene ocupados sus n lugares, entonces se podrán seguir insertando elementos en la pila 1 sin caer en un error de desbordamiento.

Operaciones Básicas Las principales operaciones a realizar sobre una pila son insertar y borrar. Insertar En primer lugar, hay que decir que esta operación es muy comúnmente denominada push. La inserción en una pila se realiza en su cima, considerando la cima como el último elemento insertado. Esta es una de las particularidades de las pilas, mientras el resto de estructuras de datos lineales se representan gráficamente en horizontal, las pilas se representan verticalmente. Por esta razón es por lo que se habla de cima de la pila y no de cola de la cima. Aunque en el fondo sea lo mismo, el último elemento de la estructura de datos. Las operaciones a realizar para realizar la inserción en la pila son muy simples, hacer que el nuevo nodo apunte a la cima anterior, y definir el nuevo nodo como cima de la pila. Vamos a ver un ejemplo de una inserción:

3

Al insertar sobre esta pila el elemento 0, la pila resultante sería:

Borrar Esta operación es normalmente conocida como pop. Cuando se elimina un elemento de la pila, el elemento que se borra es el elemento situado en la cima de la pila, el que menos tiempo lleva en la estructura. Las operaciones a realizar son muy simples, avanzar el puntero que apunta a la cima y extraer la cima anterior. Si aplicamos la operación pop a la pila de 4 elementos representada arriba el resultado sería:

Aplicaciones Las Aplicaciones que tiene las pilas son las siguientes: -Llamadas a subprogramas -Recursividad -Tratamiento de Expresiones Aritméticas -Ordenación De las cuales las 2 principales son: Llamadas a subprogramas

4

Cuando se tiene un programa que llama a un subprograma, también conocido como módulo o función, internamente se usan pilas para guardar el estado de las variables del programa, así como las instrucciones pendientes de ejecución en el momento que hace la llamada. Cuando termina la ejecución del subprograma, los valores almacenados en la pila se recuperan para continuar con la ejecución del programa en el punto en el cual fue interrumpido. Además de las variables se recupera la dirección del programa la que se hizo la llamada, porque a esa posición se regresa el control del proceso. Tratamiento de Expresiones aritméticas A+B = Infija AB+ = posfija +AB = Prefija

A+B = Infija: Esta notación es Infija porque el operador se encuentra entre los operadores. AB+ = posfija: Esta notación es Posfija porque el operador se encuentra después de los operadores. +AB = Prefija: Esta es una notación Prefija porque el operador se encuentra antes de los operadores.

Colas Una cola es una estructura de almacenamiento, donde la podemos considerar como una lista de elementos, en la que éstos van a ser insertados por un extremo y serán extraídos por otro. Las colas son estructuras de tipo FIFO (first-in, first-out), ya que el primer elemento en entrar a la cola será el primero en salir de ella. Existen muchísimos ejemplos de colas en la vida real, como por ejemplo: personas esperando en un teléfono público, niños esperando para subir a un juego mecánico, estudiantes esperando para subir a un camión escolar, etc.

Representación en memoria Podemos representar a las colas de dos formas: • Como arreglos • Como listas ordenadas Las colas se tratan como arreglos de elementos, en donde debemos definir el tamaño de la cola y dos apuntadores, uno para accesar el primer elemento de la lista y otro que guarde el último.

Operaciones Básicas En las colas como en toda estructura de datos las operaciones principales son insertar y eliminar, aunque en varias implementaciones de colas puedan recibir nombres diferentes.

5

Insertar La inserción en las colas se realiza por la cola de las mismas, es decir, se inserta al final de la estructura. Para llevar a cabo esta operación únicamente hay que reestructurar un par de punteros, el último nodo debe pasar a apuntar al nuevo nodo (que pasará a ser el último) y el nuevo nodo pasa a ser la nueva cola de la cola. Vamos a verlo gráficamente sobre la siguiente cola:

Si a esta cola le añadimos el elemento 0, la cola resultante sería:

Borrar El borrado es una operación muy simple en las colas. Esta operación supone extraer la cabeza de la cola, ya que es el elemento que más tiempo lleva en la estructura. Para llevar a cabo esta operación únicamente hay que extraer el elemento situado en la cabeza de la cola y avanzar el puntero cabeza una posición, para que de esta forma la nueva cabeza sea el segundo elemento que más tiempo lleva en la cola. Si realizamos la operación eliminar sobre la colas de 4 elementos del último gráfico el resultado sería el siguiente:

Una diferencia importante entre las colas y las listas, es que en las colas no se puede borrar un elemento cualquiera, se borra siempre el que está en la cabeza de la cola.

Tipos de colas: Simples, Circulares y Bicolas Colas simples: Se inserta por un sitio y se saca por otro, en el caso de la cola simple se inserta por el final y se saca por el principio. Para gestionar este tipo de cola hay que recordar siempre cual es el siguiente elemento que se va a leer y cuál es el último elemento que se ha introducido.

6

Colas circulares: En las colas circulares se considera que después del último elemento se accede de nuevo al primero. De esta forma se reutilizan las posiciones extraídas, el final de la cola es a su vez el principio, creándose un circuito cerrado.

Lo que se ha hecho es insertar (5), sacar (1), e insertar (8). Se sabrá que una tabla está llena cuando “rear” y “front” estén en una posición de diferencia. El teclado de ordenador se comporta exactamente como una cola circular. Para implementar las colas circulares mediante listas enlazadas se pone en el tipo T_Lista los punteros front y rear. Colas con prioridad: Las colas con prioridad se implementan mediante listas o arrays ordenados. No nos interesa en este caso que salgan en el orden de entrada sino con una prioridad que le asignemos. Puede darse el caso que existan varios elementos con la misma prioridad, en este caso saldrá primero aquel que primero llego (FIFO).

Aplicaciones Esta estructura de datos se usa en muchos sistemas operativos, por ejemplo, Unix, para llevar el control de la ejecución de procesos, cada proceso en el sistema es almacenado en una lista y esta se va recorriendo, dándole un pequeño tiempo del microprocesador a cada proceso, durante la fracción de segundo de cada proceso este asume que tiene el control total del procesador.

Listas Una lista es una estructura de datos secuencial. Una manera de clasificarlas es por la forma de acceder al siguiente elemento: - lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un array. - lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además, es dinámica, es decir, su tamaño cambia durante la ejecución del programa.

Operaciones Básicas En toda estructura de datos hay dos operaciones que sobresalen por encima del resto: Insertar y borrar. Estas dos operaciones aparecerán en toda estructura de datos, puede que con otro

7

nombre, o con una funcionalidad ligeramente diferente, pero su filosofía será la misma, proporcionar unas operaciones para la construcción de la estructura de datos. Insertar La operación insertar consiste en la introducción de un nuevo elemento en la lista. En una lista no ordenada no es necesario mantener ningún orden, por lo tanto la inserción de elementos se puede realizar en cualquier lugar de la lista, al principio, al final, en una posición aleatoria, ... Generalmente se realiza la inserción de tal forma que la complejidad temporal sea mínima, es decir, que sea una operación sencilla para que se realice en el menor tiempo posible. La operación más sencilla depende de la implementación de la estructura de datos, en unos casos puede ser la inserción al inicio, en otros la inserción al final y en este caso la inserción la realiza en el segundo nodo de la lista. Si tenemos la lista...

... e insertamos el elemento 0, la lista quedaría de la siguiente forma:

Borrar La operación borrar consiste en la eliminación de la lista de un elemento concreto. El elemento a borrar será escogido por el programador. La eliminación en una lista no conlleva ningún trabajo adicional más que el propio de la eliminación del elemento en sí. Para borrar un elemento cualquiera habría que realizar un recorrido secuencial de la lista hasta encontrar el nodo buscado y una vez localizado reestructurar los punteros para saltarse el nodo a borrar y así poder eliminarlo. Vamos a verlo con un ejemplo. Borrado del elemento 76 en la lista anterior: Paso 1: Localizar el elemento a borrar.

Paso 2: Reestructurar punteros y eliminar nodo.

8

Tipos de Listas: Simplemente enlazadas, Doblemente enlazadas y Circulares Listas Enlazadas Una lista enlazada o encadenada es una colección de elementos o nodos, en donde cada uno contiene datos y un enlace o liga. Un nodo es una secuencia de caracteres en memoria dividida en campos (de cualquier tipo). Un nodo siempre contiene la dirección de memoria del siguiente nodo de información si este existe. Un apuntador es la dirección de memoria de un nodo La figura siguiente muestra la estructura de un nodo:

El campo liga, que es de tipo puntero, es el que se usa para establecer la liga con el siguiente nodo de la lista. Si el nodo fuera el último, este campo recibe como valor NIL (vacío). A continuación, se muestra el esquema de una lista:

Listas Dobles Una lista doble o doblemente ligada es una colección de nodos en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (li) y otro a su sucesor(ld). Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero. La estructura de un nodo en una lista doble es la siguiente:

Existen dos tipos de listas doblemente ligadas: • Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo del primer nodo como el derecho del último nodo apuntan a NIL. • Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al último nodo de la lista, y el puntero derecho del último nodo apunta al primer nodo de la lista. Debido a que las listas dobles circulares son más eficientes, los algoritmos que en esta sección se traten serán sobre listas dobles circulares. En la figura siguiente se muestra un ejemplo de una lista doblemente ligada lineal que almacena números:

9

En la figura siguiente se muestra un ejemplo de una lista doblemente ligada circular que almacena números:

Listas circulares Las listas circulares tienen la característica de que el último elemento de la misma apunta al primero La siguiente figura es una representación gráfica de una lista circular.

Enseguida se mostrarán los algoritmos más comunes en listas circulares. Al igual que en las secciones anteriores, utilizaremos el apuntador top para hacer referencia al primer nodo en la lista.

Referencias

http://metodos1utec.blogspot.com/2012/10/operaciones-con-pilas-y-aplicaciones.html http://www.hci.uniovi.es/Products/DSTool/pilas/pilas-operaciones.html http://www.iuma.ulpgc.es/users/jmiranda/docencia/programacion/Tema4_ne.pdf https://upload.wikimedia.org/wikipedia/commons/5/51/APUNTES.pdf https://es.slideshare.net/josemanuelrf7/aplicacion-de-las-estructuras-de-datos http://www.hci.uniovi.es/Products/DSTool/colas/colas-operaciones.html http://www.hci.uniovi.es/Products/DSTool/listas/listas-operaciones.html http://www.algoritmia.net/articles.php?id=13

10...