Facebook Twitter RSS Reset

Tipos de estructuras de datos

Tipos de estructuras de datosGIF

¿Qué es?

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales (un dato elemental es la mínima información que se tiene en el sistema) con el objetivo de facilitar la manipulación de estos datos como un todo y/o individualmente.

¿Cuáles son?

Arreglos

Un arreglo se usa para agrupar, almacenar y organizar datos de un mismo tipo. En un arreglo cada valor se almacena en una posición numerada específica dentro del arreglo. El número correspondiente a cada posición se conoce como índice.

Tipos de estructuras de datos

Esta estructura presenta ciertas desventajas:

o en un arreglo desordenado, la búsqueda es lenta o en un arreglo ordenado, la inserción es lenta o en ambos casos, la eliminación es lenta o el tamaño de un arreglo no puede cambiar después que se creó.

Lista ligada



Una lista ligada es un mecanismo versátil conveniente para su uso en muchos tipos de bases de datos de propósito general. También puede reemplazar a los arreglos como base para otras estructuras de almacenamiento como pilas y colas.

La ventaja más evidente de utilizar estructuras ligadas, es que permite optimizar el uso de la memoria, pues no desperdiciamos el espacio de localidades vacías:

Tipos de estructuras de datos
La desventaja más grande de las estructuras ligadas es que deben ser recorridas desde su inicio para localizar un dato particular. Es decir, no hay forma de acceder al i-ésimo dato de la lista, como lo haríamos en un arreglo.

Algunas listas más complejas son las listas doblemente ligadas o las listas circulares, por nombrar algunas.

Tipos de estructuras de datos
Pilas



Una pila, es una particularización de las listas y se puede definir como una estructura en la cual los elementos son agregados y eliminados en el tope de la lista. Es una estructura LIFO (Last In First Out – el primero que llega es el último que sale).

Las pilas cuentan solo con 2 operaciones, conocidas como PUSH, insertar un elemento en el tope de la pila, y POP, leer el elemento del tope de la pila. Veamos como funcionan estos métodos:

PUSH

1.- Crear un NodoDeLista nuevo

2.- Hacer el siguiente de nuevo igual al tope

3.- Hacer el tope de la pila igual al nuevo nodo

POP

1.- Crear un nodo temporal que se instancia al tope de la pila

2.- Hacer el tope de la pila igual al siguiente del temporal

3.- Regresar el valor del nodo temporal antes que desaparezca

Colas



Una cola es una estructura de datos similar a una lista con restricciones especiales. Los elementos son agregados en la parte posterior de la cola y son eliminados por el frente. Esta estructura es llamada FIFO (First In, First Out – el primero que llega, es el primero en salir).

Implementar colas involucra el uso clases similares a una lista. Las operaciones sobre esta estructura son idénticas: insertar y eliminar, con las consideraciones pertinentes.

Insertar

Insertar un dato en una cola es muy similar a hacerlo en una pila o una lista, la diferencia es que tendremos que hacerlo por el final de la cola. A este proceso se le llama encolar.

1.- Cola inicial

2.- Creamos el nuevo nodo

3.- Hacemos que último apunte al nuevo nodo

Eliminar

Para extraer un dato de la cola, es necesario modificar el valor del nodo primero, de manera que deje de apuntar al primer elemento de la cola. De la misma manera que con las pilas, se extrae el valor antes de que se pierda. Se hace que el nodo primero ahora apunte al nuevo elemento (anterior de la cola).

Árboles



Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura compuesta por un dato y varios árboles. La forma gráfica se puede apreciar como sigue:

Tipos de estructuras de datos
En relación con los nodos, debemos definir algunos conceptos como:

•Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, „L‟ y „M‟ son hijos de „G‟.

•Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, „A‟ es padre de „B‟, „C‟ y „D‟.

En cuanto a la posición dentro del árbol, tenemos:

•Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para acceder al árbol. En el ejemplo, ese nodo es „A‟.

•Nodo hoja: nodo que no tiene hijos. En el ejemplo, hay varios: „K‟, „M‟, „O‟, etc.

•Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo „B‟, „G‟, „D‟, „J‟, etc.

Ejemplo:

public class Programa {

public static void main(String arg[]) {

String cadenano = “(Cadena no equilibrada en paréntesis(()()()))))”;

String cadenasi = “(Cadena equilibrada en parentesis())”;

System.out.println(“Verificación equilibrado en paréntesis para cadenano:”Tipos de estructuras de datosTipos de estructuras de datos;

System.out.println(verificaParentesis(cadenano));

System.out.println(“Verificación equilibrado en paréntesis para cadenasi:”Tipos de estructuras de datosTipos de estructuras de datos;

System.out.println(verificaParentesis(cadenasi));

}

public static boolean verificaParentesis(String cadena) {

Stack pila = new Stack(); int i = 0;

while (i if(cadena.charAt(i)=='(‘) {pila.push(“(“Tipos de estructuras de datosTipos de estructuras de datos;} else if (cadena.charAt(i)==’)’) {

if (!pila.empty()){ pila.pop(); } else { pila.push(“Tipos de estructuras de datosTipos de estructuras de datosTipos de estructuras de datosTipos de estructuras de datos; break; } }

i++;

}

if(pila.empty()){ return true; } else { return false; }

}

}

No comments yet.

Leave a Comment