Pilas Y Colas

CONSULTA DE PROGRAMACION

1¿Que son pilas y que son colas?, ¿qué sintaxis utilizan? , realizar un ejemplo:

Pilas y Colas

Los desarrolladores utilizan los arrays y las variantes de listas enlazadas para construir una gran variedad de estructuras de datos complejas. Esta página explora dos de esas estructuras: las Pilas, las Colas. Cuando presentemos los algoritmos lo haremos únicamente en código Java por motivos de brevedad.

La Pila es una estructura de datos donde las inserciones y recuperaciones/borrados de datos se hacen en uno de los finales, que es conocido como el top de la pila. Como el último elemento insertado es el primero en recuperarse/borrarse, los desarrolladores se refieren a estas pilas como pilas LIFO (last-in, first-out).

Los datos se push (insertan) dentro y se pop (recuperan/borran) de la parte superior de la pila. La siguiente figura ilustra una pila con tres String cada uno insertado en la parte superior de la pila:

• Pilas que contienen direcciones de retorno:

Cuando el código llama a un método, la dirección de la primera instrucción que sigue a la llamada se inserta en la parte superior de la pila de llamadas de métodos del thread actual. Cuando el método llamado ejecuta la instrucción return, se saca la dirección de la parte superior de la pila y la ejecución continúa en sa dirección. Si un método llama a otro método, el comportamiento LIFO de la pila asegura que la instrucción return del segundo método transfiere la ejecución al primer método, y la del primer método transfiere la ejecución al código que sigue al código que llamó al primer método. Como resultado una pila "recuerda" las direcciones de retorno de los métodos llamados.

• Pilas que contienen todos los parámetros del método llamado y las variables locales:

Cuando se llama a un método, la JVM reserva memoria cerca de la dirección de retorno y almacena todos los parámetros del método llamado y las variables locales de ese método. Si el método es un método de ejemplar, uno de los parámetros que almacena en la pila es la referencia this del objeto actual.

Es muy común implementar una pila utilizando un array uni-dimensional o una lista de enlace simple. En el escenario del array uni-dimensional, una variable entera, típicamente llamada top, contiene el índice de la parte superior de la pila. De forma similar, una variable de referencia, también nombrada normalmente como top, referencia el nodo superior del escenario de la lista de enlace simple.

He modelado mis implementaciones de pilas después de encontrar la arquitectura del API Collections de Java. Mis implementaciones constan de un interface Stack para una máxima flexibilidad, las clases de implementación ArrayStack y LinkedListStack, y una clase de soporte FullStackException. Para facilitar su distribución, he empaquetado estas clases en un paquete llamado com.javajeff.cds, donde cds viene de estructura de datos complejas. El siguiente listado presenta el interface Stack:

// Stack.java

package com.javajeff.cds;

public interface Stack {

boolean isEmpty ();

Object peek ();

void push (Object o);

Object pop ();

}

Sus cuatro métodos determinan si la pila está vacía, recuperan el elemento superior sin borrarlo de la pila, sitúan un elemento en la parte superior de la pila y el último recuera/borra el elemento superior. Aparte de un constructor específico de la implementación, su programa únicamente necesita llamar a estos métodos.

El siguiente listado presenta una implementación de un Stack basado en un array uni-dimensional:

// ArrayStack.java

package com.javajeff.cds;

public class ArrayStack implements Stack {

private int top = -1;

private Object [] stack;

public ArrayStack (int maxElements) {

stack = new Object [maxElements];

}

public boolean isEmpty () {

return top == -1;

}

public Object peek () {

if (top < 0)

throw new java.util.EmptyStackException ();

return stack [top];

}

public void push (Object o) {

if (top == stack.length - 1)

throw new FullStackException ();

stack [++top] = o;

}

public Object pop () {

if (top < 0)

throw new java.util.EmptyStackException ();

return stack [top--];

}

}

2. ¿Que son arboles binarios?, ¿Con que finalidad se utilizan, como es su estructura?

Un árbol binario de búsqueda también llamados BST (acrónimo del inglés Binary Search Tree) es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática.

Árbol binario

La mayoría de los arboles binarios son de búsqueda

Un árbol binario no

...