UNIDAD II: ESTRUCTURAS LINEALES

2.1 Listas

Concepto:

Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior.

 Ejemplo.

Listas enlazadas: Son colecciones de elementos de información “formados en la fila”. Se hacen inserciones o eliminaciones por cualquier lugar de la lista.

2.2 Pilas estáticas y dinámicas

 Es una lista ordenada en la que el modo de acceso a sus elementos es de tipo Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos.

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

1. Crear: se crea la pila vacía. (constructor)
2. Tamaño: regresa el número de elementos de la pila. (size)
3. Apilar: se añade un elemento a la pila.(push)
4. Desapilar: se elimina el elemento frontal de la pila.(pop)
5. Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
6. Vacía: devuelve cierto si la pila está vacía o falso en caso contrario (empty).

Ejemplo en Java de Pila Estática.

package PILA;

import java.util.Scanner;
public class PilaEstatatica {
public static int op;
public static int tope;
    int pila[]= new int[10];
    public void insertar(){
        if(tope==10)
            System.out.println("Pila llena");
        else
    {
       for(int i=0;i<pila.length;i++ ){
        System.out.println("Proporciona el dato para la pila");
        System.out.println("dato " + tope);
        Scanner cap= new Scanner(System.in);
        pila[tope]=cap.nextInt();
        tope++;
    } }
}
    public void imprimir(){
        if(tope!=0){
            for(int topeL=tope-1;topeL>=0;topeL--){
                System.out.println("\n\n" + pila [topeL]);
            }
        }
        else
            System.err.println("Pila vacia no hay nada que mostrar");
    }
    public void eliminar(){
        if(tope<0){
            System.out.println("Pila vacia");
        }
        else
            if(tope==10){//Esto se usa cuando la pila esta totalmente llena,
                //ya que se incremento en insertar y quedo en 10, de lo contrario
                //noz arrojara un error de array
                tope--;
                pila[tope]=0;
                tope--;//se vuelve a decrementar para que este en la pocision correcta,porque
                //tenia un numero de mas
            }
            else{
            pila[tope]=0;
            tope--;
            }     
    }
    public static void main(String[] args) {
       PilaEstatatica p = new PilaEstatatica();
       String r;
       Scanner cap1=new Scanner(System.in);
       Scanner cap=new Scanner(System.in);
       tope=0;
       do{
           System.out.println("Menu principal:\n¿Qué desea hacer con la pila?");
           System.out.println("1.-Insertar elemento");
           System.out.println("2.- Eliminar elemento");
           System.out.println("3.- Imprimir Pila");
           System.out.println("4.-Salir");
           op=cap.nextInt();
           switch(op){
               case 1: p.insertar();break;
               case 2:if(tope==10)
                   p.eliminar();
               else
                       System.out.println("No hay nada que eliminar :) ");
                   break;
               case 3:p.imprimir();break;
               case 4:break;
               default:
                   System.out.println("Opcion no valida, vuelva a intentarlo");break;
           }
    }while(op!=4);

}
}

Ejemplo de Pila dinámica en Java

package PILA;
import java.util.*;
public class PilaDinamica {
    public static void main(String[] args) {
        Scanner leer =new Scanner(System.in);
        int num;
        int op;
        LinkedList lista = new LinkedList();
        do{
            System.out.println("\t Menuº \t");
            System.out.println("Operaciones con pilas");
            System.out.println("1.- Insertar");
            System.out.println("2.- Borrar");
            System.out.println("3.- Mostrar la pila");
            System.out.println("4.- Salir");
            System.out.println("\n");
            System.out.println("Elija la operación que desee");
            op =leer.nextInt();
            switch(op){
            case 1:
                System.out.println("Inserte Numero");
                num =leer.nextInt();
                lista.addLast(num);
                break;
            case 2:
                System.out.println("Se borrará el nodo final");
                lista.removeFirst();
                break;
            case 3:
                System.out.println("La lista es la siguiente");
                 List lista2 = new ArrayList (lista);
                 Iterator it = lista2.iterator();//añade otro nodo ,es un ciclo
                 //sirve para recorrer la lista
                 while (it.hasNext()){
                     System.out.println(it.next() + "");
                 }
                 break;
            case 4:
                System.out.println("Al rato");
                break;
            }
        }
        while(op != 4);
    }
}

Expresiones Aritméticas

Cuando se agrupan varios números u operaciones, es importante conocer el orden o jerarquía en que deben resolverse para obtener un resultado correcto.

Ejemplo:

Para resolver 3 x 6 + 4.
Podría interpretarse como: 3 x (6 + 4) = 3 x 10 = 30.
O bien, como: (3 x 6) + 4 = 18 + 4 = 22.
De igual manera, 8 x 3 + 5 se podría interpretar como:
8 x (3 + 5) = 8 x 8 = 64 o también como (8 x 3) + 5 = 24 + 5 = 29.
¿Cuáles serían los resultados correctos?

Para evitar confusiones y errores se ha convenido en que cuando no hay paréntesis, dado que los signos + y – separan cantidades, se efectúan las operaciones en el siguiente orden:
Potencias
Multiplicaciones
Divisiones
Adiciones
Sustracciones

Por tanto, retomando los ejemplos del principio:

3 x 6 + 4 = 18 + 4 = 22

8 x 3 + 5 = 24 + 5 = 29

Esto es importante, sobre todo cuando se manejan fórmulas de geometría o de cualquier otra ciencia.

Notación Infija

La notación de infija es la notación común de fórmulas aritméticas y lógicas, en la cual se escriben los operadores entre los operandos.

Ejemplo:

Notación Infija.

Notación Posfija

La notación  notación posfija, , es un método algebraico alternativo de introducción de datos, en donde primero están los operandos y después viene el operador que va a realizar los cálculos sobre ellos. 

Ejemplo:

Notación Prefija

La notación prefija, es una forma de notación para la lógica, la aritmética, y el álgebra. Su característica distintiva es que coloca los operadores a la izquierda de sus operandos.

Ejemplo:

2.3 Colas estáticas y dinámicas

Concepto:

Una cola constituye una estructura lineal de datos en la que los nuevos elementos se

introducen por un extremo y los ya existentes se eliminan por el otro. Es importante

señalar que los componentes de la cola se eliminan en el mismo orden en el cual se

insertaron. Es decir, el primer elemento que se introduce en la estructura será el que

se eliminará en primer orden. Debido a esta característica, las colas también reciben el

nombre de estructuras FIFO (First-In, First-Out: el primero en entrar es el primero en

salir).

Existen numerosos casos de la vida real en los cuales se usa este concepto. Por ejemplo,

la cola de los bancos en las que los clientes esperan para ser atendidos -;..

primera persona de la cola será la primera en recibir el servicio-, la cola de los niño.

que esperan a veces pacientemente para subir a un juego mecánico, las colas de 1 vehículos

esperando la luz verde del semáforo, las colas para entrar a un cine, teatro'

estadio de fútbol, etcétera.

Representación de colas

Las colas, al igual que las pilas, no existen como estructuras de datos estándar en lo

lenguajes de programación. Este tipo de estructura de datos se puede representar mediante

el uso de:

• Arreglos

• Listas'

Operaciones Básicas

• Crear: se crea la cola vacía.
• Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
• Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
• Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

Tipos de colas

Cola Circular

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

Cola de Prioridad

Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen

Bicola o Doble Cola

 Es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola.Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada.

Todas las operaciones de este tipo de datos tienen coste constante.

Ejemplo en Java de Pila Estática.

Package COLA;

import.java.util.Scanner;

public class ColaEstatica {

public static int op;

public static int tope;

    int cola[]= new int[10];

    public void insertar(){

        if(tope==10)

            System.out.println("Cola llena");

        else

    {

       for(int i=0;i<cola.length;i++ ){

        System.out.println("Proporciona el dato para la Cola");

        System.out.println("dato " + tope);

        Scanner cap= new Scanner(System.in);

        cola[tope]=cap.nextInt();

        tope++;

    } }

}

    public void imprimir(){

       if(tope>0){

            for(int topeL=0;topeL<10;topeL++){

                System.out.println("\n\n" + cola [topeL]);

                System.out.println(tope);

            }

        }

        else

            System.err.println("cola vacia no hay nada que mostrar");

    }

    public void eliminar(){

        if(tope<0){

            System.out.println("cola vacia");

        }

        else

                for(int topeL=0;topeL<10;topeL++){

                     cola[topeL]=0;

            }

            }

    public static void main(String[] args) {

       ColaEstatica p = new ColaEstatica();

       String r;

       Scanner cap1=new Scanner(System.in);

       Scanner cap=new Scanner(System.in);

       tope=0;

       do{

           System.out.println("Menu principal:\n¿Que desea hacer con la pila?");

           System.out.println("1.-insertar");

           System.out.println("2.- eliminar");

           System.out.println("3.- imprimir");

           System.out.println("4.-salir");

           op=cap.nextInt();

           switch(op){

               case 1: p.insertar();break;

               case 2:p.eliminar();break;

               case 3:p.imprimir();break;

               case 4:break; default:

                   System.out.println("opcion no valida");break;

           }

    }while(op!=4);

}}