Pilas (definición y operaciones primitivas).

Definición.

   La pila es un objeto dinámico en constante cambio.

   Una pila es un conjunto ordenado de elementos en el cual se pueden insertar y eliminar elementos únicamente por un extremo: el tope de la pila.

   La característica más importante de una pila es que el último elemento insertado en ella es el primero en eliminarse, mientras que el primero que fue insertado es el último en eliminarse. Por esta razón se dice que una pila es una estructura de datos de tipo LIFO (Last In First Out).

   El proceso de inserción y eliminación de elementos puede observarse en la siguiente figura en donde se muestra, por medio de una flecha, la representación del tope de la pila. Observe cómo con cada inserción o eliminación se modifica el tope de la pila.

Crecimiento y decrecimiento de una pila.

 

    La representación mostrada en la figura anterior permite visualizar todos los elementos de la pila, sin embargo, es importante señalar que en un momento dado únicamente se tiene acceso al elemento que está siendo referido por el tope de la pila, los demás elementos permanecen ocultos, tapados por decirlo de alguna manera, por el conjunto de elementos que se encuentran encima de cada uno de ellos, con excepción del que está en el tope de la pila.

Operaciones primitivas.
   Las operaciones primitivas o fundamentales definidas sobre una pila son la inserción (push) y la eliminación (pop).

1. El comportamiento definido para la operación push consiste en insertar un nuevo elemento en la pila, mismo que constituirá el nuevo tope de la pila.
2. El comportamiento definido para la operación pop elimina el elemento referido por el tope de la pila modificando en consecuencia el tope de la pila. El nuevo tope de la pila se refiere ahora al elemento (si existe) que fue insertado inmediatamente antes que el elemento eliminado.

   Existen otras operaciones útiles al usar pilas, como por ejemplo, antes de aplicar la operación pop a una pila, sería conveniente verificar que la pila no esté vacía (operación ¿Está vacía?).

   Otro comportamiento deseable sería la operación "ojeada" (peek), la cual hecha un vistazo al elemento que se encuentra en el tope de la pila y lo regresa pero no lo elimina.

   Las operaciones push, pop y peek, son muy comunes para la estructura de datos pila, por lo que se recomienda conservar dichos nombres en la implementación.

Contenido temático.

• A modo de prefacio.
  
• Orientación a Objetos.
• Orígenes.
• Paradigma.
• Objetos y clases.
• Orientación a objetos y modularidad.
• Características fundamentales de la POO.
• Ejercicios selectos.
• Un vistazo a Java.
• Un vistazo a C++.
• Orígenes y características.
• Estructura general de una clase.
• Bienvenid@ a Java / C++. 
• Compilación en línea de comandos.
• Ejemplos selectos de transición (Java).
• Ejemplos selectos de transición (C++).
• Lectura de datos.
• Estructuras de control.
• Arreglos.
• Argumentos en la línea de comandos.
• Excepciones. 
• Genéricos (sólo Java).
• Espacios de nombres y plantillas (templates)(sólo C++).
  
• Ejercicios selectos de transición (Java).
• Ejercicios selectos de transición (C++).
• Programación Orientada a Objetos.
• Mensajes, métodos y atributos (Java).
• Mensajes, métodos y atributos (C++).
• Métodos sin argumentos.
• Métodos con argumentos.
• Métodos y atributos.
• Métodos y constructores.
• Sobrecarga (overloading).
• Herencia / Generalización.
• Abstracción.
• Implementación (Java).
• Implementación (C++).
• Composición, Agregación y Asociación.
  
• Consideraciones adicionales (Java).
• Consideraciones adicionales (C++).
• Respecto al envío de mensajes.
• Respecto a la sobrecarga de operadores.
• Respecto al paradigma. 
• Respecto al polimorfismo (early binding vs late binding).
• Clases abstractas e interfaces (Java).
  
• Ejercicios selectos (Java).
• Ejercicios selectos (C++).
• Estructuras de datos.
• Panorama general.
• Tipos de datos y referencias.
• Tipos de datos abstractos (ADT).
• Especificación del ADT Racional.
• Implementación del ADT Racional (Java). 
• Implementación del ADT racional (C++).
• Abstracción de estructuras de datos.
• Clases autorreferidas.
• Implementación.
• Consideraciones adicionales.
• Ejercicios selectos (Java).
• Ejercicios selectos (C++).
  
• Pilas.
• Definición y operaciones primitivas.
• Implementación (Java).
• Implementación (C++).
  
• Pila primitiva.
• Pila genérica.
• Aplicaciones.
• Análisis básico de expresiones.
• Notación interfija, postfija y prefija.
• Evaluación de expresiones.
• Consideraciones adicionales.
• Ejercicios selectos (Java).
• Ejercicios selectos (C++).
  
• Colas de espera.
• Definición.
• Operaciones primitivas.
• Representación.
• Implementación (Java).
• Implementación (C++).
  
• Colas de prioridad (Java).
• Colas de prioridad (C++).
  
• Cola de prioridad ascendente.
• Implementación.
• Cola de prioridad descendente. 
• Consideraciones adicionales.
• Ejercicios selectos (Java).
• Ejercicios selectos (C++).
  
• Listas enlazadas.
• Definición.
• Operaciones primitivas.
• Representación.
• Implementación (Java).
• Implementación (C++).
  
• Herencia vs. composición (Java).
• Herencia vs composición (C++).
  
• Implementación de una pila utilizando herencia.
• Implementación de una pila utilizando composición.
• Listas circulares.
• El problema de Josephus.
• Listas doblemente enlazadas.
• Definición.
• Operaciones primitivas.
• Representación.
• Consideraciones adicionales (iteradores).
• Ejercicios selectos (Java).
• Ejercicios selectos (C++).
  
• Árboles binarios.
• Definición.
• Representación y conceptos.
• Operaciones primitivas.
• Recorridos.
• Árbol binario de búsqueda (ABB).
• Operaciones primitivas.
• Representación y diseño.
• Implementación (Java).
• Implementación (C++).
  
• Eliminación.
•    Árboles binarios balanceados (AVL).
• Definición y conceptos.
• Rotación simple.
• Rotación doble.
•    Consideraciones finales.
• Ejercicios selectos (Java).
• Ejercicios selectos (C++).
  
• Excepciones (Java).
• Atrapando y manejando excepciones.
• Especificación de excepciones lanzadas por un método.
• Lanzando y encadenamiento.
• Ventajas de las excepciones.
• Ejercicios selectos.
  
•  Hilos (Java).
• Creación de hilos.
• Trabajando con hilos.
• Hilos y pausas.
• Hilos interactuando.
• Consideraciones.
  
• Sincronización.
• Interferencia de hilos.
• Errores de consistencia de memoria.
• Candados intrínsecos y sentencias sincronizadas.
  
• Conclusión. 
  
• Interbloqueo.
  
• Ejercicios selectos.
  
• Breve introducción a redes y sockets. 
• Conceptos básicos de redes.
• Puertos.
  
• Manos a la obra (Java).
• Trabajando con URLs.
• Trabajando con Sockets.
• Ejercicios selectos (Java).
  
• Referencias sugeridas.
• Miscelánea
• BlueJ (A free Java Development Environment designed for beginners).
  
• Desarrollo de un Generador de Código Swift a Partir de Modelos de Clase en UML 2.
  
• FOLDOC (Free OnLine Dictionary Of Computing).
• Java API 8. 
• Kotlin (lenguaje de programación).
  
• Refactoring guru.
• The Impact of Quantum Computing on Software Development. 
• The Java Tutorials. 

"Un lenguaje de programación cumple dos propósitos relacionados entre sí: proporciona un vehículo para que el programador especifique acciones que deben ejecutarse y proporciona un conjunto de conceptos para que el programador los use cuando piense en lo que se puede hacer..."

 ...

"Para escribir un buen programa hace falta inteligencia, gusto y paciencia."

Bjarne Stroustrup

Ejercicios selectos (estructuras de datos).

1. Investigue cómo es que se representan los tipos de datos primitivos en una computadora. Es preciso que conozca cómo se representa un tipo de datos int por ejemplo, ¿cuántos bytes le son asignados a un entero? Los números de punto flotante (float y double por ejemplo), también tiene una representación particular dentro de una computadora basada en los conceptos de mantisa y exponente. Investigue dichos conceptos, así como la representación física (hardware) de los tipos de datos en una computadora convencional.
2. Modifique el Ejemplo PruebaRacional para que genere una salida como la de la siguiente figura:  . Asegúrese de probar el caso de error tanto para el constructor como para el método estableceDenominador.
3. Modifique el Ejemplo PruebaRacional para que permita leer datos (números racionales) desde la entrada estándar (teclado).
4. Considere el Ejemplo Racional, ¿qué valor inicial tiene el objeto Racional s y m en las líneas 44 y 53 respectivamente?
5. Modifique el Ejemplo Racional para que, en lugar de acceder directamente a los atributos p y q de los objetos s y m (líneas 46-47 y 55-56 respectivamente), se acceda a ellos y se modifiquen sus correspondientes valores a través del método de tipo set correspondiente.
6. Con base en lo descrito en el blog, modifique el Ejemplo Racional para que cambie la sentencia (línea 46): s.p = p * r.obtenDenominador( ) + q * r.obtenNumerador( ); por: s.p = this.p * r.obtenDenominador( ) + this.q * r.obtenNumerador( ); realice también lo correspondiente para las líneas 47, 55 y 56 respectivamente.
7. El Ejemplo Racional implementa las operaciones de adición (suma) y multiplicación (multiplica). Para que la implementación sea completa, implemente las operaciones aritméticas faltantes de sustracción y división; utilice resta y divide respectivamente para los nombres de los métodos, y ajústese a la especificación de las operaciones definidas en la sección Especificación del ADT racional de la entrada Tipos de datos abstractos (ADT).
8. Además de lo desarrollado en el ejercicio anterior, piense en cómo mejorar la definición del ADT racional discutido en el texto. Tome en cuenta, al menos, los siguientes aspectos:
1. Comparación de igualdad: ¿cuándo se dice que dos números racionales son iguales? Ejemplo: 3 / 21 = 1 / 7.
2. Simplificación: simplificar a su expresión mínima un número racional, ya sea como resultado de una operación, o simplemente como utilidad. Ejemplo: 3 / 21 => 1 / 7. Sugerencia: obtenga el MCD (Máximo Común Divisor) del numerador y denominador a través de un método privado para simplificar el racional a su expresión mínima.
3. Cuando haga la representación en cadena del número racional (toString), considere lo siguiente: ¿qué sucede si  el resultado de la simplificación es, por ejemplo 3 / 1?, ¿tendría sentido presentarlo así?, ¿qué sucede si  el resultado de una operación es 0 / 13 por ejemplo? Si el denominador es 1, sólo presente el numerador, por otro lado, si el numerador es cero, sólo presente éste valor para tener una mejor representación en cadena del objeto Racional.
4. Por último, pero no por ello menos importante, una versión más robusta de Racional podría ser que implementara la interfaz Comparable del API. La idea es aquí definir el método compareTo() para determinar la relación de orden entre dos números racionales; así por ejemplo si r1 = 3 / 4 y r2 = 2 / 5, r1.compareTo(r2) regresaría 1, r2.compareTo(r1) regresaría -1 y 0 si ambos son iguales o equivalentes (vea 8.1).
   
9. Sean c1 y c2 dos números complejos definidos de la siguiente manera: c1 = (a + bi) y c2 = (c + di) donde a, b, c, d son números reales. Utilice las definiciones y operaciones siguientes para abstraer un ADT complejo y utilícelas para realizar una implementación de dicha entidad (como se hizo para el Ejemplo Racional). Escriba también una clase de prueba que permita probar la implementación del ADT complejo así como sus respectivas operaciones aritméticas:
1. La suma de c1 y c2 se define como: c1 + c2 = (a + bi) + (c + di)  = (a + c) + (b + d)i.
2. La resta de c1 y c2 se define como: c1 - c2 = (a + bi) - (c + di)  = (a - c) + (b - d)i.
3. La multiplicación de c1 y c2 se define como: c1 * c2 = (a + bi) * (c + di)  = (ac - bd) + (ad + bc)i.
4. La división es un poco más elaborada debido a que se racionaliza el denominador; es decir, se multiplica el numerador y el denominador por el conjugado del denominador. El conjugado de un número complejo se obtiene cambiando el signo de su componente imaginaria, es decir: si c = a + bi  es un número complejo, su conjugado está dado por c¹ = a - bi, entonces: c1 / c2 = (a + bi) / (c + di)  = [(a + bi) * (c - di)] / [(c + di) * (c - di)] = [(ac + bd) + (bc - ad)i] / (c² + d²).
10. Considere el Ejemplo Racional2, mismo que muestra el uso de la cláusula (palabra reservada) this e implementa algunas cambios respecto del Ejemplo Racional. Estudie y compare ambos ejemplos a fin de entender sus similitudes y diferencias. Tome en cuenta que, desde el punto de vista funcional (características, servicios y comportamiento de la clase) son exactamente iguales. No olvide probar su funcionamiento.
11. En base a la explicación dada en la sección Clases autorreferidas de la entrada Abstracción de estructuras de datos, modifique el Ejemplo Nodo de tal forma que sobre cargue el constructor para que, en caso de crear un objeto sin argumentos: Nodo nodo = new Nodo( ); se construya un objeto como el mostrado en la figura: . Utilice cero para el atributo dato y asegúrese de probar el funcionamiento de su constructor.
12. Diseñe y construya una clase (Cuadratica) que permita instanciar (generar) objetos que representen una ecuación cuadrática de la forma ax^2 + bx + c, donde a, b y c son los coeficientes de la ecuación. Su clase deberá:
1. Considerar el caso de intentar inicializar un objeto cuyo coeficiente a sea cero y proceder a crear y lanzar una excepción.
2. Permitir el cálculo de las raíces reales cuando existan.
3. Lanzar una excepción si las raíces no son reales.

Consideraciones adicionales respecto a las ED y los ADT.

   Las nociones de la programación orientada a objetos fueron construidas sobre las ideas y bases teóricas de los tipos de datos abstractos (ADT).
 
   Un ADT es una abstracción sumamente útil, y está estrechamente relacionada con los principios de la orientación a objetos en el sentido en que puede ser definida en términos de las características (modeladas en atributos) y los servicios (representados por los métodos) que ofrece.

   La importancia más significativa en la idea de los ADT es la separación de las nociones de interfaz (servicios) e implementación.

   Por otro lado, la definición y operación de una estructura de datos está en directa relación con la definición de un ADT, por lo que en las secciones de las entradas siguientes, además de definir las estructuras de datos más usuales y convencionales, se presentará un tipo de implementación particular para ellas; sin embargo, es importante que el lector tenga presente que existe más de una posible implementación para una definición de un ADT determinado y que, si en la práctica debe utilizar alguna para resolver algún problema real, lo mejor será recurrir a las estructuras de datos del API o de la biblioteca estándar del lenguaje que utilice. En este blog, la implementación de dichas estructuras persigue un objetivo estrictamente didáctico, y constituyen más un medio para ilustrar el paradigma, que una implementación eficiente.

   Por último pero no menos importante, es menester mencionar que, además de la implementación de las estructuras de datos más comunes, se presentarán también algunas de las aplicaciones tradicionales más representativas, con la principal intención de poner en práctica de manera combinada, tanto los conceptos orientados a objetos, como las de las estructuras de datos propiamente dichas; al mismo que tiempo de que se somete a prueba su implementación.