Estructura de datos

Unidad III

Estructuras Lineales

Rubi veronica chimal Cuxin.

Ingeniería

en sistem

as computacionales

INSTITUTO TECNOLÓGICO SUPERIOR DE FELIPE CARRILLO PUERTO

IntroducciónEsta unidad conoceremos, identificaremos y aplicaremos las estructuras lineales en la solución de problemas del mundo real utilizando un lenguaje de programación implemente las operaciones básicas (insertar, eliminar y buscar) en listas simples y doblemente enlazadas con un lenguaje de programación implemente las operaciones básicas (insertar y eliminar) en una pila en sus modalidades estática y dinámica. Además de utilizar un lenguaje de programación implemente las operaciones básicas (insertar y eliminar) en una cola en sus modalidades estática y dinámica. Incorpore además sus variantes de cola circular y bicola.

Colas

Una cola, es una estructura de datos lineal que permite almacenar elementos por

un extremo y extraerlos por el otro. Por tal motivo, es una estructura FIFO (first in,

first out: primero en entrar, primero en salir).

Al igual que en las pilas, se debe tener el control de la cola, tomando en cuenta de

que si se quiere extraer un elemento de la cola se debe asegurar de que no esté

vacía, o si se quiere insertar un elemento se debe asegurar de que la cola no esté

llena, estas dos acciones se deben desarrollar al hacer operaciones con una cola.

Las operaciones que aplican a una cola son:

-       Crear una cola.-       Revisar si la cola está vacía.-       Revisar si la cola está llena.-       Insertar un elemento en la cola.-       Extraer un elemento de la cola.-       Revisar cuál es el siguiente elemento en la cola.

 

Funcionamiento Cola vacía

         

 Se va a insertar un elemento en la cola, el número 10 push(10)(Los elementos se insertan al final de la cola)

10        

 Se va a insertar otro elemento en la cola, el número 13 push(13) (Los elementos se insertan al final de la cola)

10 13      

 Se va a insertar otro elemento en la cola, el número 15 push(15) (Los elementos se insertan al final de la cola)

10 13 15    

 Se va a insertar otro elemento en la cola, el número 20 push(20)(Los elementos se insertan al final de la cola)

10 13 15 20  

 Se va a insertar otro elemento en la cola, el número 5 push(5)(Los elementos se insertan al final de la cola)

10 13 15 20 5

 Si se quiere insertar otro elemento en la cola entonces debe de marcar cola llena, ya que no hay espacio para almacenar ningún otro valor

 Se extrae un valor de la cola llamando al método pop() (todos los valores de la cola se sacan del inicio).

10 13 15 20 5

Sale el valor de 10.  13 15 20 5

Al sacar el valor de 10 queda con espacio vacío en  la primera posición por lo que se debe de recorrer para que quede espacio para almacenar un nuevo valor.

 Cola con recorrido aplicado13 15 20 5  

Si se extrae un valor de la cola llamando al método pop() (todos los valores de la cola se sacan del inicio).

13 15 20 5  

Sale el valor de 13.  15 20 5  

Al sacar el valor de 13 queda con espacio vacío en  la primera posición por lo que se debe de recorrer para que quede espacio para almacenar un nuevo valor.

 Cola con recorrido aplicado15 20 5    

 

Y así sucesivamente hasta que no queden más elementos en la cola y si se quiere sacar un valor entonces va a marcar cola vacia.

 Lo más recomendable y flexible para la creación de un nodo es utilizar un objeto

por cada nodo, para ello debe comprender cuatro conceptos fundamentales que

son:

-       Clase auto-referenciada,-       Nodo,-       Campo de enlace y-       Enlace

 Una clase auto-referenciada es una clase con al menos un campo cuyo tipo de

referencia es el nombre de la misma clase.

            public clase Nodo

{

                       Object elemento;

                       Nodo siguiente;

                        //métodos

}

El código anterior es una clase auto-referenciada porque su campo siguiente tiene

el tipo Nodo. El nodo es un objeto creado a partir de una clase auto-referenciada.

Conclusión

Entendemos que una cola es una estructura de datos lineal que permite

almacenar elementos por un extremo y extraerlos por el otro. Que utiliza diferentes

secuencias o lógicas para poder lograrlo al igual que tienen algunas operaciones

que aplican a una cola son: Crear una cola, Revisar si la cola está vacía, Revisar

si la cola está llenar, Insertar un elemento en la cola, Extraer un elemento de la

cola, Revisar cuál es el siguiente elemento en la cola.