Estructura Datos

República Bolivariana de VenezuelaUniversidad Tecnológica del CentroDepartamento Redes

Facilitador:Prof. Bassam Asfur

Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura

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

En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.

Estructura Pila

Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

Las pilas suelen emplearse en los siguientes contextos:Evaluación de expresiones en notación postfija (notación polaca inversa).Reconocedores sintácticos de lenguajes independientes del contextoImplementación de recursividad.

Estructura Pila

Operaciones

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.

Crear: se crea la pila vacía.

Apilar: se añade un elemento a la pila.(push)

Desapilar: se elimina el elemento frontal de la pila.(pop)

Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)

Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.

Estructura Pila

Estructuras de datos relacionadas

El tipo base de la estructura FIFO (el primero en entrar es el primero en salir)es la cola.

Por ejemplo, el cambio de una pila en una cola en un algoritmo de búsqueda puede cambiar el algoritmo de búsqueda en primera profundidad (en inglés, DFS) por una búsqueda en amplitud (en inglés, BFS).

Una pila acotada es una pila limitada a un tamaño máximo impuesto en su especificación.

Estructura Pila

Arquitectura básica de una pila

Una pila típica es un área de la memoria de los computadores con un origen fijo y un tamaño variable. Al principio, el tamaño de la pila es cero. Un puntero de pila, por lo general en forma de un registro de hardware, apunta a la más reciente localización en la pila; cuando la pila tiene un tamaño de cero, el puntero de pila de puntos en el origen de la pila.

Las dos operaciones aplicables a todas las pilas son:

Una operación apilar, en el que un elemento de datos se coloca en el lugar apuntado por el puntero de pila, y la dirección en el puntero de pila se ajusta por el tamaño de los datos de partida.

Una operación desapilar: un elemento de datos en la ubicación actual apuntado por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamaño de los datos de partida.

Estructura Pila

Hay muchas variaciones en el principio básico de las operaciones de pila. Cada pila tiene un lugar fijo en la memoria en la que comienza.

Como los datos se añadirán a la pila, el puntero de pila es desplazado para indicar el estado actual de la pila, que se expande lejos del origen (ya sea hacia arriba o hacia abajo, dependiendo de la aplicación concreta

Por ejemplo, una pila puede comenzar en una posición de la memoria de mil, y ampliar por debajo de las direcciones, en cuyo caso, los nuevos datos se almacenan en lugares que van por debajo de 1000, y el puntero de pila se decrementa cada vez que un nuevo elemento se agrega.

Cuando un tema es eliminado de la pila, el puntero de pila se incrementa.

Estructura Pila

import java.io.*;public class principal { static int v[],i=0,n; public static void insertar(int v[], int i){ if (principal.i<principal.n){ v[i]=i+1; principal.i++; } else{ System.out.println("Pila llena"); } } public static void borrar(int v[], int i){ System.out.println("El elemento Borrado es "+v[i-1]); principal.i--; } public static void imprimir(int v[],int n){ System.out.println("\nLos datos de la Pila son"); for(int i=n-1; i>=0;i--){ System.out.println(v[i]); } }

public static void destruir(){ principal.i=0; } public static void main(String[] y)throws IOException{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int num; n=4; v = new int[n];do{ new menu();// clase que muestra menu num = Integer.parseInt(in.readLine( )); switch(num){ case 1: insertar(v,i); break; case 2: borrar(v,i); break; case 3: imprimir(v,i); break; case 4: destruir(); }

Pila con un Arreglo

}while(num!=5); }}class menu{ public menu(){ System.out.println("Selecione una opcion"); System.out.println("1.- Insertar Elemento"); System.out.println("2.- Borrar Elemento"); System.out.println("3.- Imprimir Stack"); System.out.println("4.- Destroy Stack"); System.out.println("5.- Salir"); }}

Una cola 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 (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento.

Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

Estructura Cola

Usos concretos de la cola

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

En caso de estar vacía borrar un elemento sería imposible hasta que no se añade un nuevo elemento. A la hora de añadir un elemento podríamos darle una mayor importancia a unos elementos que a otros (un cargo VIP) y para ello se crea un tipo de cola especial que es la cola de prioridad.

Estructura Cola

Ejemplo grafico de una cola

Estructura Cola

Operaciones Básicas

Crear: se crea la cola vacía.

Encolar (añadir, entrar, push): se añade un elemento a la cola. Se añade al final de esta.

Desencolar (sacar, salir, pop): 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 primero elemento que entró.

Estructura Cola

Tipos de colas

Colas circulares (anillos): en las que el último elemento y el primero están unidos.

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.

Estructura Cola

Representación grafica colas circulares

Estructura Cola

Tipos de colas

Colas de prioridad: En ellas, 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.

Hay 2 formas de implementación:

Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.

Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

Estructura Cola

Tipos de colas

Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos.

Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos.

Hay variantes:

Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.

Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

Estructura Cola

Tarea:

Crear un programa en java que permita realizar operaciones sobre un arreglo asumiendo que se esta trabajando sobre una cola de datos

Fecha de entrega 11/10/2011

Estructura Cola