PILAS

Las pilas son otro tipo de estructura de datos lineales, las cuales presentan restricciones en cuanto a la posición en la cual pueden realizarse las inserciones y las extracciones de elementos. Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella.

Definición

La pila es una lista ordenada o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (Last In First Out) “último en entrar, primero en salir” que permite almacenar y recuperar datos.

Operaciones

Para el manejo de los datos se cuenta con dos operaciones básicas: Push “apilar, insertar” que coloca un objeto en la pila, y su operación inversa, pop “retirar, desapilar o eliminar”, que retira el último elemento apilado

.

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.

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

Operaciones auxiliares

·         Llena: Regresa verdadero si la pila está llena.

·         Vacía: Regresa verdadero si la pila está vacía.

·         Size: Regresa el tope de la pila.

·         Vaciar: Elimina todos los elementos de la pila

Clases para la implementación de pilas

Las pilas son una estructura de datos muy usadas en la solución de diversos tipos de problemas. Por ejemplo en la recursividad. El concepto de recursión es difícil de precisar, pero existen ejemplos de la vida cotidiana que nos pueden servir para darnos una mejor idea acerca de lo que es recursividad. Un ejemplo de esto es cuando se toma una fotografía de una fotografía, o cuando en un programa de televisión un periodista transfiere el control a otro periodista que se encuentra en otra ciudad, y este a su vez le transfiere el control a otro.

Implementación matricial

Una forma mejor de usar matrices toma en cuenta el hecho de que inserciones y borrados ocurren solamente en el tope y por lo tanto dichas operaciones sólo se efectuarán en un extremo de la estructura.

Implementación mediante celdas enlazadas

Push y pop operan solamente sobre la celda de cabecera.  Las cabeceras pueden ser punteros mejor que celdas completas, ya que no hay noción de posición para las pilas.

Aplicación del tema Pilas

Los navegadores de Internet almacenan las direcciones visitadas recientemente. Cada vez que el usuario visita una página, su dirección es almacenada en una pila, de forma que cada vez que el usuario hace clic en back se retira el último elemento insertado en la pila, esto es, se muestra en pantalla la última página visitada.

En la vida cotidiana existen muchos ejemplos de pilas, una pila de platos en una alacena, una pila de latas en un supermercado, una pila de papeles sobre un escritorio, una pila de películas, de libros, de discos, pila de resultados parciales de fórmulas aritméticas, llamadas a subprogramas etc.

Aportaciones

El tema de pilas nos aportó conocimientos acerca de que son y cómo se en la vida estas son ocupadas y las podemos encontrar en diversos aspectos e incluso en nuestro hogar. De esta manera nos es más sencillo entender este tipo de estructuras de datos y aplicarlo en la programación.

Conclusiones

La pila es una estructura de datos en la que los elementos pueden ser añadidos o removidos por un solo extremo, teniendo como operaciones principales dos que son push y pop y algunas otras como pila vacía o llena, se dice que su último valor en entrar es el primero en salir y a este se le llama tope. Por esta razón también es considerada como una estructura de tipo LIFO

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. Una cola es una estructura de datos lineal, es decir una colección de elementos en la cual cada elemento tiene un sucesor y un predecesor únicos, con excepción del primero y del último. La estructura cola se caracteriza porque las operaciones de inserción y eliminación de elementos deben hacerse por extremos diferentes. Los elementos se insertan por uno de los extremos y se eliminan por el otro extremo. En una estructura tipo cola se identifican los dos extremos por donde se realizan las operaciones. El frente o principio de la cola será el extremo en el cual se eliminarán elementos, mientras que el final será el extremo en el cual se harán las inserciones.

Definición

Es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Tipos

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.

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.

Colas dobles

En una doble cola, los elementos se pueden insertar o eliminar por cualquiera de los dos extremos. Es decir, se pueden insertar y eliminar valores tanto por el  frente como por el final de la cola.

Operaciones

Las operaciones principales son insertar y eliminar

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.

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.

Operaciones Auxiliares

·         Llena: Regresa verdadero cuando la cola está llena.

·         Vacía: Regresa verdadero cuando la cola está llena.

Clases para la implementación de colas

La clase Cola: La clase cola tiene atributos y métodos, como cualquier clase.

Esta implementación es estática, es decir, da un tamaño máximo fijo a la cola.

No se incluye comprobación de errores dentro del encolado y el desencolado, pero se implementan como funciones aparte.

Como se aprecia en la implementación de las pilas, los elementos se quitan y se ponen sobre la cima, pero en este caso se introducen por un sitio y se quitan por otro. Podría hacerse con un array secuencial

Aplicación del tema Colas

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.

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, cola de automóviles esperando servicio en una gasolinera, Cola de programas en espera de ser ejecutados por una computadora.

Aportaciones

El tema de colas al igual que el de pilas nos aportó como este tipo de estructuras las tenemos presentes día con día y es muy común que existan colas en diversas cuestiones. Este tema es aplicado de la misma manera en la informática como estructuras de datos y este tema hoy nos deja el entendimiento de cómo se llevan a cabo en esta ciencia.

Conclusiones

Las colas son una estructura lineal en la que sus elementos entran o salen por ambos extremos, cada elemento tiene un antecesor y un sucesor con excepción del primero y el último. Tiene dos operaciones principales que son push y pop o insertar y eliminar. A las colas se les considera una estructura de tipo FIFO, esta denominación se le da ya que su primer elemento en entrar también es el primero es salir. Para las colas existen diversos tipos como son: colas circulares, dobles y simples.

LISTAS ENLAZADAS

Una lista enlazada o encadenada es una colección de elementos ó 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.

Simples

Una lista con nodo de cabecera es aquella en la que el primer nodo de la lista contendrá en su campo dato algún valor que lo diferencie de los demás nodos (como: *, -, +, etc).

Para el caso de las listas sin nodo de cabecera, se usará la expresión TOP para referenciar al primer nodo de la lista, y TOP (dato), TOP (liga) para hacer referencia al dato almacenado y a la liga al siguiente nodo respectivamente.

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.

·         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.

Circulares

Las listas circulares tienen la característica de que el último elemento de la misma apunta al primero

Multilistas.

Este método de búsqueda permite accesar la información de manera ordenada a través de campos claves. Las multilistas permiten llegar a un registro por diferentes caminos. El camino lo determina el campo clave sobre el cual se haga la búsqueda.

Clases para la implementación de listas.

     Declaración de listas enlazadas. Los nodos de una lista enlazada se representan mediante registros de dos campos: un campo para los datos y otro para el enlace. Ejemplo Las declaraciones para una lista enlazada de nombres son TYPE

·         Crear una lista enlazada vacía. Para construir una lista enlazada debemos ser capaces de crear una lista vacía. PROCEDURE CrearLista( VAR Lista : TipoListaEnlazada ).

·         Comprobar si una lista enlazada está vacía. Dado que una lista enlazada vacía se representa mediante un puntero nulo, resulta sencillo determinar si una lista enlazada está vacía o no.

·         un elemento al principio de una lista enlazada. Uno de los métodos para construir una lista enlazada consiste en añadir repetidamente elementos al principio de la lista, comenzando con una lista vacía.

Aplicación del tema Listas

Una buena analogía de una lista sería un tren, donde cada vagón está conectado con el que le precede y el que le sigue.

Aportaciones

Este tema nos dio a conocer lo que son las listas así como sus tipos y entender como son implementadas en la informática, lo que nosotros entendíamos como listas en este tema lo reafirmamos pero dando un enfoque a la estructura de datos. Al igual nos dimos cuenta que respecto a esto existen diversos tipos de las mismas.

Conclusiones

Una lista es una colección de varios elementos a los cuales llamamos nodos y cada uno tiene una liga que va a unirlo a otro y que también contiene datos. Las listas también tiene una inserción, eliminación y una búsqueda de elementos y distintos tipos los cuales son: simples, dobles en las cuales encontramos dobles lineales y dobles circulares, circulares y multilistas