estructura de datos
TRANSCRIPT
2
Forma de Evaluar el Curso
2 Exámenes 40%Tareas y trabajos 10%Proyecto Final 50%Total 100%Condición para pasar el curso 80% asistencias.
3Unidad 1: Introducción a las estructuras de datos.
4
Introducción TAD
La principal razón para que las personas aprendan lenguajes y técnicas de programación es utilizar la computadora como una herramienta para resolver problemas.La abstracción de datos es la técnica de inventar nuevos tipos de datos que sean más adecuados y por consiguiente, facilitar la estructura del programa.Los lenguajes de programación soportan tipos de datos fundamentales o básicos (predefinidos), tales como int, char y float en C++ y Java.
5
Introducción TAD
Un tipo de dato definido por el programador se denomina tipo abstracto de dato TAD (Abstract Data Type, ADT). El término abstracto se refiere al medio en que un programador abstrae algunos conceptos de programación, creando un nuevo tipo de dato.La popularización de un programa utiliza la noción tipo abstracto de dato (TAD), siempre que sea posible si el lenguaje de programación soporta los tipos que desea el usuario y el conjunto de operaciones sobre cada tipo, se obtiene un nuevo tipo de dato denominado TAD.
6
1.1 Tipos de datos abstractos (TDA).
El concepto de tipo de dato abstracto (TDA, Abstract Data Type), fue propuesto por primera vez hacia 1974 por John Guttag y otros, pero no fue hasta 1975 que por primera vez Liskov lo propuso para el lenguaje CLU.Un tipo de dato abstracto es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo.
7
1.1 Tipos de datos abstractos (TDA).
Con mucha frecuencia se utilizan los términos TDA y Abstracción de Datos de manera equivalente, y esto es debido a la similitud e interdependencia de ambos. Sin embargo, es importante definir por separado los dos conceptos.Los Lenguajes de Programación Orientados a Objetos son lenguajes formados por diferentes métodos o funciones y que son llamados en el orden en que el programa lo requiere, o el usuario lo desea.
8
1.1 Tipos de datos abstractos (TDA).
La abstracción de datos consiste en ocultar las características de un objeto y obviarlas, de manera que solamente utilizamos el nombre del objeto en nuestro programa.Al hecho de guardar todas las características y habilidades de un objeto por separado se le llama Encapsulamiento y es también un concepto importante para entender la estructuración de datos. Es frecuente que el Encapsulamiento sea usado como un sinónimo del Ocultación de información.
9
1.1 Tipos de datos abstractos (TDA).
Un TDA está caracterizado por un conjunto de operaciones (funciones) al cual se denomina usualmente como interfaz pública y representa el comportamiento del TDA; mientras que la implementación como la parte privada del TDA está oculta al programa cliente que lo usa.Los TDA que nos van a interesar de ahora en adelante son aquellos que reflejen cierto comportamiento organizando cierta variedad de datos estructuradamente. A esta forma estructurada de almacenar los datos será a la que nos refiramos para caracterizar cada TDA.
10
1.1 Tipos de datos abstractos (TDA).
Un TDA tendrá una parte que será invisible al usuario la cual hay que proteger y que se puede decir que es irrelevante para el uso del usuario y está constituida tanto por la maquinaria algorítmica que implemente la semántica de las operaciones como por los datos que sirvan de enlace entre los elementos del TDA, es decir, información interna necesaria para la implementación que se esté haciendo para ese comportamiento del TDA. Resumiendo podemos decir, que tanto la implementación de las operaciones como los elementos internos del TDA serán privados al acceso externo y ocultos a cualquier otro nivel.
11
1.1 Tipos de datos abstractos (TDA).
Un TDA representa una abstracción: Se destacan los detalles (normalmente pocos) de
la especificación (el qué). Se ocultan los detalles (casi siempre numerosos)
de la implementación (el cómo).
Abstracción. denota las características esenciales de un objeto que lo distingue de otros
12
1.1 Tipos de datos abstractos (TDA).
Ejemplo:public class Coche {
private String matricula;
private double velocidad; // atributos privados
private double velocidadMax;
// Método constructor
public Coche(String pMatricula, double pVelMax) {
this.matricula= pMatricula;
this.velocidad = 0.0;
if (velocidadMax >= 0.0) {
this.velocidadMax = pVelMax; }
else { velocidadMax = 0.0; }
}
// Métodos de consulta
public String getMatricula() { return this.matricula; }
…
// Métodos de asignación
public void setMatricula(String pMatric) { this.matricula = pMatric; }
…
// Otros métodos
public void Acelerar(double pVel) {
this.velocidad = this.velocidad + pVel;
if (this.velocidad > this.velocidadMax) {
this.velocidad = this.velocidadMax; }
if (this.velocidad < 0.0) { this.velocidad= 0.0; }
}
…}
13
1.2 Modularidad (Ocultación de la información).
Se denomina Modularidad a la propiedad que permite subdividir una aplicación en partes más pequeñas (llamadas módulos), cada una de las cuales debe ser tan independiente como sea posible de la aplicación en sí y de las restantes partes.
Modularidad. capacidad de un
sistema que ha sido dividido en módulos
cohesivos y débilmente acoplados
14
1.2 Modularidad (Ocultación de la información).
Estos módulos que se puedan compilar por separado, pero que tienen conexiones con otros módulos. Al igual que la encapsulación, los lenguajes soportan la Modularidad de diversas formas.Según Bertrand Meyer "El acto de particionar un programa en componentes individuales para reducir su complejidad en algún grado. . . . A pesar de particionar un programa es útil por esta razón, una justificación más poderosa para particionar un programa es que crea una serie de límites bien definidos y documentados en el programa. Estos límites, o interfaces, son muy valiosos en la comprensión del programa".
15
1.2 Modularidad (Ocultación de la información).
Ventajas de la Modularización Un programa modular es
fácil de mantener y modificar.
Un programa modular es más fácil de escribir y depurar (ejecutar, probar y poner a punto).
Un programa modular es más fácil de controlar. El desglose de un problema en módulos permite encomendar los módulos más complejos a los programadores más experimentados y los más sencillos a los programadores nóveles.
Posibilita el uso repetitivo de las rutinas en el mismo o en diferentes programas
Desventajas de la Modularización No se dispone de algoritmos
formales de modularidad, por lo que a veces los programadores no tienen claras las ideas de los módulos.
La programación modular requiere más memoria y tiempo de ejecución.
16
1.2 Modularidad (Ocultación de la información).
En Java la unidad modular es la clase Una clase es la abstracción de un conjunto de objetos (instancias) Una clase ofrece unos servicios y oculta otros recursos Java no separa la especificación y la implementación de los
módulos. En Java es posible definir objetos interfaz que contengan la
declaración de un conjunto de operaciones públicas de una clase. Esta interfaz agruparía la especificación de los métodos que exporta un
módulo. Es posible definir varias interfaces para una clase. En la interfaz NO se incluyen los métodos estáticos ni el método constructor
de la clase. Implementación: definición de una clase Java. Ocultaremos los detalles
17
1.2 Modularidad (Ocultación de la información).
Java permite organizar las clases en paquetes y subpaquetes de forma jerárquica
Esta jerarquía se refleja en la forma de almacenamiento en disco a través de directorios
18
1.2 Modularidad (Ocultación de la información).
Tipos de Módulos (Java)a) Módulos de definiciónb) Módulos de servicioc) Tipos Abstractos de Datosd) Máquinas Abstractas de Estado
19
1.2 Modularidad (Ocultación de la información).
Módulos de Definición Declaración de
constantes y variables
Se declaran sobre clases abstractas (abstract)
Se declaran como estáticas (static)
Definiciones de constantes (final)
Ejemplo:abstract class ConfiguracionSistema{
static boolean VersionEvaluacion;
static int diasUtilización;
static final int maxDias;
static String ubicacion;
static String paginaInicial;
}
20
1.2 Modularidad (Ocultación de la información).
Módulos de Servicio Ofrecen un servicio Agrupan un conjunto de
operaciones Las operaciones de la
interfaz se declaran sobre clases no instanciables (abstract y
final) Las operaciones son
declaradas estáticas (static)
Ejemplo:abstract class UtilidadesString
{
static void aMayusculas(String S)
{...}
static void eliminarBlancos(String S)
{...}
static Boolean esPrefijo (String P, String S)
{...}
private static int interna(String P, String S)
{...}
}
21
1.2 Modularidad (Ocultación de la información).
Máquinas Abstractas de Estado (MAE)
A diferencia de los TADs, las operaciones de una MAE se efectúan sobre un único objeto (la clase), no se pueden generar diferentes objetos del mismo tipo
En Java definiremos MAEs a través de clases que cumplan los siguientes requisitos:
No pueden admitir tener varias instancias
Los métodos se aplican sobre el único objeto dela clase
Ejemplo:
public class Pila { // Atributos
private static final int CAPACIDAD=1000;
private static int elementos[];
private int tope; // índice de la primera posición libre
private static Pila unaPila = new Pila(); // única instancia de la clase
// Constructora
private Pila() {
elementos = new int[CAPACIDAD];
tope = 0;
}
// Operación de acceso
public static Pila obtPila (){
return unaPila;
}
22
1.3 Usos de los TDA
Algunos ejemplos de utilización de TDA en programación son: Conjuntos: Implementación de conjuntos con sus
operaciones básicas (unión, intersección y diferencia), operaciones de inserción, borrado, búsqueda.
Árboles Binarios de Búsqueda: Implementación de árboles de elementos, utilizados para la representación interna de datos complejos. Aunque siempre se los toma como un TDA separado son parte de la familia de los grafos.
23
1.3 Usos de los TDA
Pilas y Colas: Implementación de los algoritmos FIFO y LIFO.
Grafos: Implementación de grafos; una serie de vértices unidos mediante una serie de arcos o aristas.
24
1.4 Manejo de Memoria Estática
Es la asignación de memoria para algunos elementos fijos del programa que es controlada por el compilador.
Define la cantidad de memoria necesaria para un programa durante el tiempo de compilación.
El tamaño no puede cambiar durante el tiempo de ejecución del programa.
Algunos lenguajes de programación utilizan la palabra static para especificar elementos del programa que deben almacenarse en memoria estática.
Elementos que residen en memoria estática: Código del programa. Las variables definidas en la sección principal del
programa, las cuales pueden solo cambiar su contenido no su tamaño.
Todas aquellas variables declaradas como estáticas en otras clases o módulos.
25
1.5 Manejo de Memoria Dinámica
Es la asignación y posible recuperación de memoria durante la ejecución de un programa y bajo su control.
Define el tamaño del espacio de memoria necesario para un programa en tiempo de ejecución.
El tamaño de los elementos puede cambiar durante la ejecución del programa.
Almacena todos los elementos definidos con la palabra new en un programa.
Sus variables crecen de tamaño o se reducen durante la ejecución del programa. Estas se almacenan en un espacio de memoria llamado heap; el cual se localiza en la región de memoria que esta encima del stack.
Algunos lenguajes de programación permiten que el programador asigne y desasigne manualmente la memoria… Pero JAVA utiliza un recolector de basura.
26
Recursividad
Unidad 2
27
2.1 Definición
La recursividad forma parte del repertorio para resolver problemas en Computación y es de los métodos más poderosos y usados.La recursividad es un concepto fundamental en matemáticas y en computación. Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismo concepto que intenta describir.La recursividad consiste en realizar una definición de un concepto en términos del propio concepto que se está definiendo.
28
2.1 Definición
En toda situación en la cual la respuesta pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas, la fórmula recursiva es un buen candidato para resolver el problema.Los razonamientos recursivos se encuentran en la base misma de las matemáticas porque son necesarios para describir conceptos centrales como el de número.
29
2.2 Procedimientos Recursivos
Un método recursivo es aquel que (directa o indirectamente) se llama a si mismo.
Para que el método recursivo defina una computación que termina, la(s) llamada(s) recursiva(s) han de ser más sencilla(s) (de acuerdo con alguna métrica)
30
Estructuras lineales
Unidad 3
31
Introducción
Las estructuras lineales son importantes porque aparecen con mucha frecuencia en situaciones de la vida: Una cola de clientes de un banco, las instrucciones de un programa, los caracteres de una cadena o las páginas de un libro
Características: existe un único elemento, llamado primero, existe un único elemento, llamado último, cada elemento, excepto el primero, tiene un único predecesor y cada elemento, excepto el último, tiene un único sucesor.
Operaciones: crear la estructura vacía, insertar un elemento, borrar y obtener un elemento. Para definir claramente el comportamiento de la estructura es necesario determinar en qué posición se inserta un elemento nuevo y qué elemento se borra o se obtiene.
Principales estructuras lineales: pilas, colas y listas
32
Estructuras de Datos
Estructuras de Datos
Lineales
No lineales
Almacenamiento Contiguo
Almacenamiento No
Contiguo
33
Operaciones Básicas en Estructuras Lineales
1. Recorrido: Procesa c/elemento de la estructura.
2. Búsqueda: Recupera la posición de un elemento específico.
3. Inserción: Adiciona un nuevo elemento a la estructura.
4. Borrado: Elimina un elemento de la estructura.
5. Ordenación: Ordena los elementos de la estructura de acuerdo a los valores que contiene.
6. Mezcla: Combina 2 estructuras en una sola.
34
LISTAS ENLAZADAS
1. Simples (con enlace simple)2. Dobles (doblemente enlazadas)
Existe diversas implementaciones de estas estructuras.
Las variaciones mas comunes implementan listas circulares y listas con cabecera en sus dos variaciones (simples y dobles)
35
Ejemplo Lista simplemente enlazada
36
LISTAS
Una lista es una colección lineal de elementos llamados nodos donde el orden de los mismos se establece mediante punteros o referencias y existe un puntero/referencia especial llamado inicio para localizar al primer elemento.
Ejemplos:
inicio *Lista enlazada de 0 elementos
inicio
* Lista enlazada de 4 elementos
Información enlace
37
Los nodos de las listas
Un nodo se divide en 2 partes: Información: Contiene la información del
elemento. Enlace: Contiene la dirección del siguiente nodo
de la lista.
información enlace
Nodo
public class Nodo{ // atributos public String informacion; public Nodo enlace; // el constructor de nodos Nodo (String n){ informacion = n; enlace = null; }}
38
Los nodos de las listas
Una lista enlazada requiere, como mínimo, una referencia al primer nodo de la lista:
Cuando la lista está vacía, el atributo primero apunta a null:
39
En Java
40
1. Arreglos: La relación lineal esta implícita en la relación física de los elementos. Desventaja: Almacenamiento estático y tamaño fijo.
2. Elementos enlazados: Agrega a cada elemento un campo de enlace, no requieren almacenamiento contiguo en memoria, se pueden añadir y borrar elementos fácilmente.
Almacenamiento de datos:
41
Listas Simples
Colección lineal de elementos llamados nodos.
Existe un elemento llamado inicio que apunta al primer elemento de la lista.
Cada nodo contiene un campo de enlace que apunta al siguiente elemento.
El último elemento de la lista en su campo enlace apunta a nulo.
Al principio el apuntador inicio apunta a nulo.
42
Insertar: Agrega un elemento a la lista.
Eliminar: Retira un elemento de la lista.
Buscar: Busca un elemento en la lista.
Recorrer: Visita todos los elementos de la lista.
Vacía: Indica si la lista contiene o no elementos.
Tamaño: Indica el número de elementos de la lista.
Operaciones con listas simples
43
Lista doblemente enlazada
Una lista doblemente enlazada es una lista enlazada de nodos, donde cada nodo tiene un par de campos de enlace. Un campo de enlace permite atravesar la lista hacia adelante, mientras que el otro permite atravesar la lista haca atrás. Para la dirección hacia adelante, una variable de referencia contiene una referencia al primer nodo. Cada nodo se enlaza con el siguiente mediante el campo de enlace next, excepto el último nodo, cuyo campo de enlace next contiene null para indicar el final de la lista (en dirección hacia adelante).
44
Lista doblemente enlazada
De forma similar, para la dirección contraria, una variable de referencia contiene una referencia al último nodo de la dirección normal (hacia adelante), lo que se interpreta como el primer nodo. Cada nodo se enlaza con el anterior mediante el campo de enlace previous, y el primer nodo de la dirección hacia adelante, contiene null en su campo previous para indicar el fin de la lista.
45
Lista doblemente enlazada
Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior.
Las listas doblemente enlazadas no necesitan un nodo especial para acceder a ellas, pueden recorrerse en ambos sentidos a partir de cualquier nodo, esto es porque a partir de cualquier nodo, siempre es posible alcanzar cualquier nodo de la lista, hasta que se llega a uno de los extremos.
46
Lista doblemente enlazada
En algunas aplicaciones podemos desear recorrer la lista hacia adelante y hacia atrás, o dado un elemento, podemos desear conocer rápidamente los elementos anterior y siguiente. En tales situaciones podríamos desear darle a cada celda sobre una lista un puntero a las celdas siguiente y anterior en la lista.Además podemos usar un puntero a la celda que contiene el n-ésimo elemento de una lista para representar la posición n, mejor que usar el puntero a la celda anterior aunque lógicamente, también es posible la implementación similar a la expuesta en las listas simples haciendo uso de la cabecera.
47
Añadir un elemento a la lista Doblemente Enlazada
48
Insertar un elemento en la primera posición de la lista
49
Insertar un elemento en la ultima posición de la lista
50
Insertar un elemento a continuación de un nodo cualquiera
51
Listas Circulares
Una lista circular es una lista lineal en la que el último nodo a punta al primero.
Las listas circulares evitan excepciones en la operaciones que se realicen sobre ellas. No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.
En algunas listas circulares se añade un nodo especial de cabecera, de ese modo se evita la única excepción posible, la de que la lista esté vacía.
52
Listas Circulares
A pesar de que las listas circulares simplifiquen las operaciones sobre ellas, también introducen algunas complicaciones. Por ejemplo, en un proceso de búsqueda, no es tan sencillo dar por terminada la búsqueda cuando el elemento buscado no existe.
Por ese motivo se suele resaltar un nodo en particular, que no tiene por qué ser siempre el mismo. Cualquier nodo puede cumplir ese propósito, y puede variar durante la ejecución del programa.
53
Listas Circulares
Otra alternativa que se usa a menudo, y que simplifica en cierto modo el uso de listas circulares es crear un nodo especial de hará la función de nodo cabecera. De este modo, la lista nunca estará vacía, y se eliminan casi todos los casos especiales.
54
Pilas
Los compiladores utilizan la memoria para almacenar ciertos datos que serán utilizados dentro de la ejecución de un programa, teniendo en cuenta el tamaño y su tiempo de vida dentro del programa se puede escoger entre la memoria estática o la memoria dinámica.
55
Memoria Estática
La memoria estática se utiliza cuando se conoce el tamaño y duración de los datos durante la ejecución del programa, de esta forma se declaran los datos y su dirección de memoria de manera contigua.Ejemplo:Supóngase un programa con dos variables flotantes A y B, además de un arreglo T de tamaño 10
56
Memoria Estática
En la tabla se muestra una representación gráfica de memoria estática.
57
Memoria Dinámica
En memoria dinámica los espacios de memoria se van asignando durante la ejecución del programa, si algún dato llegará a desaparecer el espacio de memoria queda disponible para poder ser utilizado. ApuntadoresUn apuntador es una variable que contiene la dirección de otra variable. los apuntadores se utilizan en las estructuras de datos para apuntar a direcciones de memoria que pueden cambiar durante la ejecución de un programa. En la siguiente figura se representa p como un apuntador, este apunta hacia c que son dos celdas de memoria, c podría ser un char.
58
Pilas
Las pilas forman parte de las estructuras de datos lineales, esta se puede ejemplificar como una pila de libros.
En esta pila solo se puede ver o tomar el libro que ocupa la cima, si se quiere tomar uno de en medio se tendría que sacar de uno en uno hasta llegar al valor deseado.
En programación una pila es una secuencia de datos diseñada para realizar inserciones y eliminaciones desde uno de sus extremos (la cima o el tope), a continuación se muestra una representación gráfica de la estructura pila.
59
Pilas
60
Operaciones básicas con pilas
public void push(int valor){ Nodo nuevo = new Nodo
(valor); // se declara el nodo con el valor que almacenará
if(vacia()) // si la pila está vacía el nodo declarado en la linea anterior, representa el tope de la lista
tope=nuevo; else{ // de lo contrario el
apuntador 'siguiente' del nodo nuevo apunta hacia el que anteriormente era el tope
nuevo.siguiente=tope; // ahora el tope es nuestro nodo nuevo
tope= nuevo;}}
Push: Utilizado para agregar un elemento a la lista, recibe como parámetro un número entero, ya que la pila que se describe es de enteros, y este nodo será insertado en la cima.
61
Operaciones básicas con pilas
public void pop(){ if (vacia())// si la
lista está vacía, mandamos un mensaje de información
System.out.println("La pila está vacia");
else// de lo contrario el tope será el que era el elemento de abajo del tope
tope= tope.siguiente;
}
Pop: Utilizado para eliminar el elemento que está en el tope, lo único que hace es asignar el apuntador de inicio a el penúltimo elemento.
62
Operaciones básicas con pilas Vacía: nos indica
si la pila está vacía.
public boolean vacia(){
return tope==null; // si el tope es vacio, siginifica que la lista está vacia
}
63
Operaciones básicas con pilas
Peek: nos muestra el nodo tope.
public int peek(){ if (vacia()){ // si la pila
está vacía, mandamos un mensaje de información y regresamos null
System.out.println("La pila está vacia");
return new Integer(null);
}else // sino está vacia
regresamos el elemento del tope
return tope.dato;}
64
Operaciones básicas con pilas Adicionalmente
se proporciona un método de recorrer, para verificar que las inserciones se realizaron correctamente.
public static void recorrer(Nodo init){
if(init!=null){
System.out.print(init.dato+"-");
recorrer(init.siguiente);
}}
65
Notación infija y postfija
Evaluación de expresiones aritméticas mediante pilas Una expresión aritmética está formada por operandos y operadores. Así la expresión x *y-(a+b) consta de los operadores *, -, + y de los operandos x, y, a, b. Los operandos pueden ser valores constantes, variables o incluso, otra expresión. Los operadores son los símbolos conocidos de las operaciones matemáticas. La evaluación de una expresión aritmética da lugar a un valor numérico, se realiza sustituyendo los operandos que son variables por valores concretos y ejecutando las operaciones aritméticas representadas por los operadores.
66
Notación infija y postfija
Así, si los operandos de la expresión anterior toman los valores: x=5, y=2, a=3, b=4, el resultado de la evaluación es: 5*2 – (3+4) = 5*2 – 7 = 10 – 7 = 3 La forma habitual de escribir expresiones matemáticas es aquella en la que el operador está entre dos operandos. La expresión anterior escrita de esa forma, recibe el nombre de notación infija. Esta forma de escribir las expresiones exige, en algunas ocasiones, el uso de paréntesis para encerrar subexpresiones con mayor prioridad, sin olvidar los niveles de prioridad y la asociatividad.
67
Notación infija y postfija
Notación prefija y notación postfija de una expresión aritmética. Para nuestro problema una expresión aritmética será un medio que permite indicar el orden en que se deben realizar una serie de operaciones para obtener un resultado. Las operaciones se indican mediante operadores, que en nuestro caso representan las operaciones suma, resta, producto, división e igualdad, todas ellas operaciones binarias (necesitan exactamente dos argumentos para poderse evaluar).
68
Notación infija y postfija
Existen varias notaciones para representar expresiones aritméticas, que se diferencian en el orden en que se escriben los argumentos (operandos) de los operadores. Las más relevantes son: Notación infija: La notación habitual. El orden es
primer operando, operador, segundo operando. Notación prefija: El orden es operador, primer
operando, segundo operando. Notación postfija: El orden es primer operando,
segundo operando, operador. Notación funcional: Se escribe el operador/función y
después, entre paréntesis, los operadores separados por comas.
69
Notación infija y postfija
La notación infija tiene el problema de que en expresiones con más de un operador existe ambiguedad sobre cual es el orden de evaluación. Por ejemplo, la expresión 8/4/2 se puede interpretar como (8/4)/2 o bien como 8/(4/2). Las otras notaciones no sufren este problema. Un problema interesante en computación es poder convertir expresiones en notación INFIJA a su equivalente en notacion POSTFIJA. Dada la expresión A+B se dice que está en notación INFIJA, y su nombre se debe a que el operador (+) esta entre los operadores (A y B).
70
Notación infija y postfija
Dada la expresión AB+ se dice que está en notación POSTFIJA, y su nombre se debe a que el operador (+) esta después entre los operadores (A y B). La ventaja de usar expresiones en notación polaca POSTFIJA radica en que no son necesarios los paréntesis para indicar orden de operación, ya que este queda establecido por ubicación de los operadores con respecto a los operandos. Para convertir una expresión dada en notación INFIJA a una notación POSTFIJA, deberán establecerse previamente ciertas condiciones
71
Notación infija y postfija
72
Tarea:
73
Recursividad con ayuda de pilasLas pilas se usan comúnmente para indicar en que punto se encuentra un programa cuando contiene procedimientos que se llaman a si mismos. Estos procedimientos se conocen como procedimientos recursivos.
La recursividad es una técnica en la que un procedimiento o función se hace llamadas a si mismo en el proceso de realización de sus tareas. La recursividad se puede definir mediante un clásico ejemplo de la función factorial. La recursividad es una técnica de programación muy potente que puede ser usada en lugar de una iteración (Bucles o ciclos). Ello implica una forma diferente de ver las acciones repetitivas permitiendo que un subprograma se llame a si mismo para resolver una operación mas pequeña del programa original
74
Colas
Es una lista de elementos en la que los elementos se introducen por un extremo y se eliminan por otro. Los elementos se eliminan en el mismo orden en el que se insertaron. Por lo tanto el primer elemento en entrar a la cola será el primer elemento en salir. Debido a esta característica las colas reciben también el nombre de QUEUE o FIFO (First-In, First-Out: Primero en Entrar Primero en
Salir).
En la vida real existen numerosos casos de colas: personas esperando para usar un teléfono público, las personas que esperan para ser atendidas en la caja de un banco, etc.
75
Colas
Otras aplicaciones ligadas a la computación son: en las colas de Impresión, en el caso de que existiese una sola computadora para atender a varios usuarios, puede suceder que algunos de ellos soliciten los servicios de impresión al mismo tiempo o mientras el dispositivo está ocupado. En estos casos se forma una cola con los trabajos que esperan a ser impresos. Los mismos se irán imprimiendo en el orden en que fueron llegando a la cola.
Otro caso es cuando se manejan los sistemas en tiempo compartido. Varios usuarios comparten ciertos recursos, como CPU o memoria RAM. Los recursos se asignan a los procesos que están en cola de espera, suponiendo que todos tienen la misma prioridad, en el orden en el cual fueron introducidos en la cola.
76
Representación en memoria estática
En este caso se tratarán las colas como arreglos de elementos, en las cuales es necesario definir el tamaño de la cola y dos apuntadores. El primer apuntador se usará para acceder al primer elemento al cual le llamaremos F y el otro puntador que guarde el último elemento y le llamaremos A. Además uno llamado MÁXIMO para definir el número máximo de elementos en la cola.
77
Representación en memoria estática
Ejemplo:En la siguiente figura se muestra una cola que ha guardado tres elementos:X,Y,Z.
78
Representación en memoria dinámica
Este tipo de estructuras se caracteriza porque insertamos los elementos por un lado y los extraemos por el otro lado. Es de tipo FIFO ( First In First Out ), el primer elemento en entrar es el primero en salir. Para gestionar la cola utilizaremos 3 punteros.
79
Representación en memoria dinámica
80
Operaciones básicas con colas.
El método push nos sirve para ingresar elementos nuevos a la cola, como se menciono anteriormente la particularidad de las colas es que los nuevos elementos se insertan al final de la cola.
81
Operaciones básicas con colas.
82
Operaciones básicas con colas.
El método pop tiene como objetivo el poder eliminar elementos de la cola, pero con una condición que la diferencia de las pilas o las listas ligadas, las colas eliminan elementos al inicio.
83
Operaciones básicas con colas.
84
Operaciones básicas con colas
Este método recorre toda la cola de inicio a fin, con este método podemos comprobar si nuestros métodos anteriores (push y pop) son correctos.
85
Operaciones básicas con colas
86
Aplicaciones Colas
Aplicaciones de la cola: Aplicaciones informáticas: atender las solicitudes de un único recurso compartido (impresora, disco, CPU), la transferencia de datos de forma asíncrona (datos no reciben necesariamente al mismo ritmo que el enviado) entre los dos procesos (buffers IO), por ejemplo, tubos, archivo IO, tomas de corriente. Tampones en reproductores de MP3 y reproductores portátiles de CD, iPod lista de reproducción. Lista de reproducción de jukebox - añadir canciones a la final, el juego desde el frente de la lista. Manejo de interrupciones: En la programación de un sistema en tiempo real que puede ser interrumpida, es necesario prestar atención a las interrupciones de inmediato, antes de proceder con la actividad actual.