PILAS DINÁMICAS

Pilas Dinámicas

Una pila al ser una lista puede almacenar en el campo de información cualquier tipo de valor (int, char, float, vector de caracteres, un objeto, etc). 

También se las llama listas LIFO (Last In First Out - último en entrar primero en salir) 

Existen dos tipos de pilas, la estática y la dinámica, la primera se hace a través de arreglos y la segunda por celdas. 

Para estudiar el mecanismo de utilización de una pila supondremos que en el campo de información almacena un entero (para una fácil interpretación y codificación) 

Inicialmente la PILA está vacía y decimos que el puntero raíz apunta a null. 

Aquí el código para una pila Dinámica en C Sharp. 

class Pila
{
private class celda
{
public object e; //Se declara un objeto "e" de clase publico
public celda sig; //Se declara un elemento siguiente de clase celda
public celda(object x, celda p) //constructor de la clase celda que recibe un objeto y la celda como parametro
{
e = x;
sig = p;
}
}
celda p; //Referecia de celda es de tipo privado
public Pila() //CONSTRUCTOR de la clase pila
{
p = null; //Que la pila este vacia se usa el NUll
}
public bool vacia() //metodo de como saver si la pila esta vacia
{
return p == null; //Como saber si la pila esta vacia
}
public void pop() //Metodo para elinminar el elemento
{
if(!vacia()) //si la pila no esta vacia. "!" Quiere decir "Si No" o "Negar" en c#
{
p=p.sig; //Continua hacial la otra celda
}
}
public object top() //Para recuperar el ultimo elemento que el pop elimino TOPE
{
if (!vacia()) //Si la pila ne esta vacia retorna un objeto anterior
{
return p.e; //retorna el elemento p
}
else
{
return null;
}
} //celda tiene que apuntar a donde apuntaba p se puede hacer cuando
public void push(object x)
{
p = new celda(x, p);
}

}
class Program //Clase program Esta clase lo puedes modificar a tu gusto.
{
static void Main(string[] args)
{
Pila p = new Pila();
for (int i = 0; i < 4; i++)
{
Console.WriteLine("Introduzca un elemento";);
p.push(Console.ReadLine());
}
for (int i = 0; i < 4; i++)
{
Console.WriteLine("Elemento {0} es {1}", i+1, p.top());
p.pop();
}
Console.ReadLine();
}
}

COLAS DINÁMICAS

Colas Dinámicas

Una cola dinámica en C Sharp utiliza celdas para almacenar los datos. Cumple las propiedades de las colas. (Primero en entrar primero en salir). 

Aquí el código de una cola en C Sharp: 

classCola
{
classcelda
{
publicobject e;
publiccelda sig=null;
publiccelda(object x, celda p)
{
e = x;
p.sig = this;
}
public celda(object x)
{
e = x;
}
}
celda posterior, frente;
public Cola()
{
posterior = null;
frente = null;
}
publicboolvacia()
{
return posterior == null;
}
publicvoid push(Object X)
{
if (vacia())
{
posterior= frente =newcelda(X);
}
else
{
posterior = newcelda(X, posterior);
}
}
publicobject top()
{
if (!vacia())
{
returnfrente.e;
}
returnnull;
}
publicvoid pop()
{
if (!vacia())
{
if (frente == posterior)
{
posterior = frente = null;
}
else
{
frente = frente.sig;
}
}
}
}

Y aquí el método Main para la cola.

staticvoid Main(string[] args)
{
Cola p = newCola();
Console.WriteLine(p.vacia());
for (inti = 0; i< 4; i++)
{
Console.WriteLine("Introduzca un elemento";);
p.push(Console.ReadLine());
}
for (inti = 0; i< 4; i++)
{
Console.WriteLine("Elemento {0}: {1}", i+1, p.top());
p.pop();
}
Console.ReadLine();
}

LISTAS

Listas

Una lista es una estructura de datos secuencial.

Una manera de clasificarlas es por la forma de acceder al siguiente elemento:

- lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un array.

- lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del programa.

Una lista enlazada se puede definir recursivamente de la siguiente manera:

- una lista enlazada es una estructura vacía o

- un elemento de información y un enlace hacia una lista (un nodo).

Gráficamente se suele representar así:

Como se ha dicho anteriormente, pueden cambiar de tamaño, pero su ventaja fundamental es que son flexibles a la hora de reorganizar sus elementos; a cambio se ha de pagar una mayor lentitud a la hora de acceder a cualquier elemento.

En la lista de la figura anterior se puede observar que hay dos elementos de información, x e y. Supongamos que queremos añadir un nuevo nodo, con la información p, al comienzo de la lista. Para hacerlo basta con crear ese nodo, introducir la información p, y hacer un enlace hacia el siguiente nodo, que en este caso contiene la información x. 

¿Qué ocurre si quisiéramos hacer lo mismo sobre un array?. En ese caso sería necesario desplazar todos los elementos de información "hacia la derecha", para poder introducir el nuevo elemento, una operación muy engorrosa.

La sintaxis para crear una colección list‹T› es la siguiente:

List‹tipo› nombre = new List‹tipo›();

ArrayList es un objeto creado de una manera similar, aunque sin el argumento de tipo:

ArrayList nombre = new ArrayList ();

Con esta sintaxis ahora podemos crear una list‹T› denominada listacolores:using System;
using System.Collections.Generic;

public class Lists
{
static void Main()
{
List‹string› listacolores = new List‹string›();
}
}



Ejemplo:


List<List<string>> almacen = new List<List<string>>();

// Ahora vas rellenando los datos en las sucesivas listas
List<string> datos1 = new List<string>();
datos1.Add("D1 - nombre");
datos1.Add("D1 - direccion");
etc... para la lista datos1

// Se inserta la lista datos1 en la lista de listas almacen
almacen.Add(datos1);

// Ahora para recuperar algun dato:
List<string> datos1 = almacen[0]; // esta es la primera <lista> de la <lista de listas>
string nombre= datos1[0]; // Este es el primer valor de la lista anterior
MessageBox.Show("El primer dato de la primera lista es: " + nombre);

Cuando entiendes el proceso ya lo puedes hacer de una vez, por ejemplo adoptando tu nomenclatura:
MessageBox.Show("El primer dato de la primera lista es: " + Listas_de_Nombres[0][0]);
siendo: Listas_de_Nombres[0] la primera <lista> de la <lista de listas>
siendo Listas_de_Nombres[0][0] el primer nombre de la primera <lista> de la <lista de listas>

COLAS

Queue (Cola)

La cola (Queue), tiene el comportamiento contrario a la pila. Todo nuevo elemento se agrega al principio de la colección y solo se puede extraer el último elemento. Por esta razón, la cola se conoce como una colección FIFO (Fisrt Input First Output) ya que el primer elemento que ingresa a la cola es el primer elemento que sale. Para recordar este comportamiento se puede asociar la Queue con la fila que se debe hacer en un banco para realizar una consignación. En ese caso, el cajero atiende en el orden en que llegan las personas a la cola.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;// necesario para poder declarar un "Queue"

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Queue cola = new Queue();//instancio un nuevo objeto Queue(Cola)

cola.Enqueue("Perro");//agrego un elemento a la cola
cola.Enqueue("Gato");
cola.Enqueue("Loro");
cola.Enqueue("Tigre");
cola.Enqueue("Leon");
cola.Enqueue("Lobo");
cola.Enqueue("Zorro");
cola.Enqueue("Conejo");



for (int i = 0; i < 3; i++)//itera 3 veces para ir retirando elementos de la cola
{
Console.WriteLine("Elementos totales que se encuentran en la cola: " + cola.Count);//.count cuenta la cantidad de elementos en la cola
Console.WriteLine("");

Console.WriteLine("Elemento retirado de la cola: " +cola.Dequeue());//.dequeue() retira un elemento de la cola
Console.WriteLine("el proximo elemento que queda en la cola es: " +cola.Peek());//.peek() muestra el proximo elemento de la cola, sin retirarlo
Console.WriteLine("");
Console.WriteLine("");
}

Console.WriteLine("Elementos totales que se encuentran en la cola: " + cola.Count);
Console.ReadKey();
}
}
}

PILAS

Stack (Pila)

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



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.

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 contexto

· Implementación de recursividad.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;// necesario para poder declarar un "STACK"
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Stack pila = new Stack();//instancio un nuevo objeto stack(pila)

pila.Push(1);//agrego un elemento a la pila
pila.Push(4);
pila.Push(1);
pila.Push(6);
pila.Push(3);
pila.Push(5);
pila.Push(9);

for (int i = 0; i < 3; i++)//itera 3 veces para ir retirando elementos de la pila
{
//pila.pop saca elementos de la pila
Console.WriteLine("Elemento retirado de la pila: " + pila.Pop());//imprime los elementos que va retirando el .pop
Console.WriteLine("el próximo elemento que queda en la pila es: " + pila.Peek());//muestra el elemento siguiente en la pila sin eliminarlo
Console.WriteLine("");
}
Console.ReadKey();
}
}
}