PILA.

Una pila representa una estructura lineal de datos en la que se puede agregar o quitar elementos únicamente por uno de los extremos. En consecuencia, los elementos de una pila se eliminan en orden inverso al que se insertaron; es decir, el ultimo elemento que se mete a la pila es el primero que se saca. Debido a esta característica, se le conoce como estructura LIFO, (el ultimo en entrar es el primero en salir).

Existen numerosos casos prácticos en los que se utiliza el concepto de pila; por ejemplo, una pila de platos, una pila de latas, una pila de libros etc.

Una pila se define formalmente como una colección de datos a los cuáles se puede acceder mediante un extremo, que se conoce generalmente como tope.

OPERACIONES CON PILAS.

La definición de una estructura de datos queda completa al incluir las operaciones que se pueden realizar en ella. Para el caso de las pilas, las operaciones básicas que se pueden llevar a cabo son:

• Insertar un elemento---push---en la pila.
• Eliminar un elemento---pop---en la pila.

Y las operaciones auxiliares:

• pila_vacía.
• pila_llena.

 Pila_vacía (PILA, TOPE, BAND)

{Este algoritmo verifica si una estructura tipo pila esta vacía, asignando a BAND el valor de verdad correspondiente. La pila se implementa en un arreglo unidimensional. TOPE es un parámetro de tipo entero. BAND es un parámetro de tipo booleano}

1. si (TOPE=0) {verifica si no hay elementos almacenados en la pila}

 entonces

                Hacer BAND--verdadero {la pila esta vacía}

si no

               Hacer BAND--falso {la pila no esta llena}

     2. { fin del condicional del paso 1} 

  

pila_llena (PILA, TOPE, MAX, BAND)

{ Este algoritmo verifica si una estructura tipo pila esta llena, asignando a BAND el valor de verdad correspondiente. La pila se implementa en un arreglo unidimensional de MAX elementos. TOPE es un parámetro de tipo entero. BAND es un parámetro de tipo booleano}

1. si (TOPE=MAX)

         entonces

                     Hacer BAND----verdadero {la pila esta llena}

          si no

                  Hacer BAND---falso{la pila no esta llena}

2. {fin del condicional del paso 1}

Llamada a Subprogramas.

Cuando se tiene un programa que llama a subprograma, también conocido como modulo o función, internamente se usan pilas para guardar el estado de las variables del programa, así como las instrucciones pendientes de ejecución del subprograma, los valorea 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 en la que se hizo la llamada, por que a esa pocisión se regresa el control del proceso.

 

RECURSIVIDAD.

La recursion es un recurso muy poderoso que permite expresar soluciones simples y naturales a ciertos tipos de problemas. Es importante recordad que no todos los problemas son naturales recursivos; algunos si lo son y otros no.

La recursion se puede presentar de dos maneras diferentes:

a)  Directa: el programa o subprograma se llama directamente así mismo.

b) Indirecta: el subprograma llama a otro subprograma y este en algún momento, llama nuevamente a primero.

TRATAMIENTO DE EXPRESIONES ARITMÉTICAS.

Un problema interesante en computación consiste en convertir expresiones en notación infija a su equivalente en notación prefija o postfija o prefija.

* Dada la expresión A+B se dice que esta se encuentra en notación infija, porque el operador (+) se encuentra entre dos operadores ( A y B).

* Dada la expresión AB+ se dice que esta se encuentra en notación postfija, porque el operador (+) se encuentra después de los operadores (A y B).

* Dada la expresión +AB se dice que esta se encuentra en notación prefija, porque el operador (+) esta precediendo a los dos operandos.

ORDENACIÓN.

Ordenar significa reagrupar o reorganizar un conjunto de datos u objetos en una secuencia especifica.

PROGRAMA PILA ESTÁTICA.

Import java. util.scanner;

public classs pilaestatica{

public static void main (string argss []){

   int dato;

   int pila []= new int [5];

scanner captura= new scanner (system.in);

for (int tope=0; tope<4; tope++) 

{

system.out.print\n (proporciones de datos para pila);

dato=captura.next\n+();

pila[tope]=dato;

}

for (int tope=4; tope>4; tope-) 

system.out.print\n (la pila tiene los siguientes datos¨+ pila

[tope]);

}

}

LISTAS.
Es un tipo de estructura lineal y dinámica de datos. Lineal porque a cada elemento le puede seguir solo otro elemento;  dinámica porque se puede manejar la memoria de manera flexible, sin necesidad de reserva de espacio con antelación.
La principal ventaja de manejar un tipo dinámico de datos es que se pueden adquirir posiciones de memoria a medida que se necesitan; estas se liberan cuando ya no se requieren.

• LISTAS LIGADAS.

Son colecciones de elementos llamdos nodos; el orden entr estos se establece por medio de un tipo de datos denominado punteros, apuntadores, direcciones o referencias a otros nodos.
En general un noda consta de dos partes:

• Un campo de INFORMACION que sera del tipo de datos que se quieran almacenar en la lista.
• Un campo LIGA, de tipo puntero que se utiliza para establecer la liga o enlace con otro nodo de la lista. Si el nodo fuera el ultimo de la lista, esta campo tendra como valor NIL-vacio-. Al emplearse el campo liga para relacionar dos nodos, no sera necesario almacenar fisicamente a los nodos en espacios contiguos.

Las operaciones que pueden efectuarse en una lista simplemente ligada son:

• Recorrido de la lista: Consiste en visitar cada uno de los nodos que forman la lista.
• Inserccion de un elemento: Consiste en agregar un nuevo nodo a la lista.
• Borrado de un elemento: Consiste en eliminar un nodo de la lista y liberar espacio de la memoria correspondiente.
• Busqueda de un elemento:  Se debe ir recorriendo los nodos hasta encontrar el que estemos buscando o hasta que llegue al final de la lista.

LISTAS CICULARES.

Tiene la caracterstica de que el ultimo elemento de la lista apunta al primero, en lugar de apuntar al vacio o NIL.
Se define una lista simplemente ligada circular como una coleccion de elementos llamados nodos en la cual el ultimo nodo apunta al primero.
La operacion de recorrido de listas circulares se necesita considerar algun criterio para detectar cuando se han visitado todos los nodos de la lista.
Este ultimo con el proposito de evitar caer en ciclos infinitos. Una posible solucion al problema planteado consiste en usar un nodo extra llamado nodo de cabecera, para indicar el inicio de la lista. Este nodo contendra informacion especial de tal manera que se distinga de los demas y asi podra hacer referencia al pricipio de la lista.

LISTAS DOBLEMENTE LIGADAS. 

Es una coleccion de nodos, en la cual cada uno de ellos tiene dos apuntadores, uno apuntando a su predecesor (LIGAIZQ) y otra a su sucesor (LIGADER). Por medio de estos punteros se podra entonces avanzar o retroceder a traves de la lista, segun se tomen las direcciones de uno u otro

apuntador.

Las operaciones que se pueden llevar a cabo con este tipo de estructuras son las mismas que con listas simplemente ligadas. En esta seccion se presentaran las operaciones de:

• Recorrido de la lista: Al tener cada nodo  una doble liga, la lista se puede recorrer tanto del inicio al final, mediante la ligas derechas, com en sentido inverso; es decir del final al principio, con las ligas izquierdas.
• Inserccion de un elemento: Agrgar un nuevo nodo a la lista y establecer los apuntadores correspondientes.
• Borrado de un elemento: Eliminar un elemento de la lista, redefiniendo los apuntadores correspondientes y liberando el espacio de memoria ocupado por el nodo.

 

Listas Enlazadas