Definicion de Pilas y Colas

Definicion de Pilas

Una pila (stack en inglés) es una lista ordenada 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.

Definicion de Colas

Una cola es una colección de elementos homogéneos (almacenados en dicha estructura), en la misma se pueden insertar elementos por uno de los extremos, llamado frente, y retirar los mismos por el otro extremo, denominado final.

Es importante aclarar que, tanto el frente como el final de la cola, son los únicos indicados para retirar e insertar elementos, respectivamente. Esto nos indica que no podemos acceder directamente a cualquier elemento de la cola, sino solo al primero, o sea el que está o se encuentra en el frente, y no se pueden insertar elementos en cualquier posición sino solo por el final, así el elemento insertado queda como último.

Por esta razón la cola es denominada una estructura F.I.F.O., o simplemente una lista F.I.F.O., esto representa el acrónimo de las palabras inglesas “first in, first out” (primero en entrar, primero en salir).

Gráficamente podemos representarla como:

Torres de Hanoi

Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Édouard Lucas.Este juego de mesa solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.

Algoritmo

Entrada: Tres pilas de números origen, auxiliar, destino, con la pila origen ordenada

Salida: La pila destino

1. si origen  entonces
   1. mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino)
   2. terminar
2. si no
   1. hanoi(,origen,destino, auxiliar)     //mover todas las fichas menos la más grande (n) a la varilla auxiliar
3. mover disco n a destino                //mover la ficha grande hasta la varilla final
4. hanoi (auxiliar, origen, destino)          //mover todas las fichas restantes, 1...n–1, encima de la ficha grande (n)
5. terminar

Ejemplos de Manejo de Funciones

Ejemplos de Manejo de Funciones

A continuacion podran ver algunos ejemplos sobre el manejo de funciones y como funcionan las funciones en el lenguaje C.

/* Inclusión de archivos */
#include <stdio.h>

void holamundo(void) /* Función donde se ejecuta la lógica del programa */
{
  printf("Hola Mundo\n"); /* imprime la cadena */
 return; /* sale de la función */
}
 
int main(void) /* Función principal del programa */
{
 holamundo(); /* llamada a la función holamundo */
 return 0; /* sale del programa con código 0 (correcto) */
}

Este código es en todo equivalente al "Hola Mundo" original, sólo que nos muestra cómo escribir y cómo utilizar una función. Y además nos muestra un principio de buena programación: meter las sentencias que "hacen el trabajo" en otras funciones específicas para sacarlas de main(), dejando en ésta tan sólo un guión general de lo que hace el programa, no las órdenes específicas. De esta manera se facilita la comprensión del programa, y por tanto el futuro trabajo de modificarlo.

#include <stdio.h>

int main(void)
{
 int suma = sumar(5, 3); /* ERROR, sumar no ha sido declarada aún */
 printf("La suma es: %d ", suma);
 return 0;
}

int sumar(int numero1, int numero2)
{
 return numero1 + numero2;
}

En este caso el programa es erróneo y no compila, ya que en la línea donde se llama a la función sumar, el compilador aún no conoce ninguna función con ese nombre, y cuáles son sus argumentos y valor de retorno.

Una posible solución es declarar el prototipo de la función al principio, para informar al compilador que existe, y luego definir el cuerpo de la misma en cualquier lugar del programa:

#include <stdio.h>

/* Declaración */
int sumar(int numero1, int numero2);

int main(void)
{
 int suma = sumar(5, 3);
 printf("La suma es: %d ", suma);
 return 0;
}

/* Definición */
int sumar(int numero1, int numero2)
{
 return numero1 + numero2;
}

Y un ejemplo de Funcion Recursiva =).

#include <stdio.h>

void funcionA(char c); /* se declara el prototipo de la función para que el llamado */
void funcionB(char c); /* a la misma en la función no sea implícita */

int main(void)
{

 funcionA('z'); /* llamado a funcionA */

 return 0;
}

void funcionA(char c)
{
 if (c > 'a') /* caso base mientras c no sea menor que A */
  funcionB(c); /* llamado a la funcionB */

 printf("%c ", c); /* imprimimos el valor de c */
*la variable es un parametro no utilizado para este proceso
}

void funcionB(char c)
{
 funcionA(--c); /* llamado a la funcionA decrementando el valor de 'z' */
}

Ejemplos de pila con arreglo y listas

En el siguiente codigo en C++ se pueden apreciar el uso de pilas utilizando arreglos y listas :
 Pila con Arreglos

Codigo con Arreglos :

#include<iostream>
#define j 10
using namespace std;
int s[j] ,top = -1;
bool full() {
    return top == j-1;
}
bool empty() {
    return top == -1;
}
void insert(int dato) {
    if (!full()) { // No podemos colocar un elemento a una pila llena.
       top++;
       s[top] = dato;
    }           
}
int extract() {
   if (!empty()) {
      int aux = s[top];
      top--;
      return aux; //Una forma mas elegante era colocar: return V[tope--];
   }
   else return -00000; //Si la pila esta vacia, retornamos un valor bandera...
}
int main() 
{

insert (29);
insert (32);
insert (56);
insert (78);
insert (23);
cout<< extract() << endl;
cout<< extract() << endl;
cout<< extract() << endl;
cout<< extract() << endl;
cout<< extract() << endl;
}
Donde esta seria su ejecucion : 


Codigo  con lista :

#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;                                                                

struct node{
int data;
struct node*foward;
}*top=NULL,*help;

void pile(int num)
{
help=new node;
help->data=num;
if(top==NULL)
{
top=help;
help->foward=NULL;
}else{
help->foward=top;
top=help;
}
}
void list()
{
cout<<"\ndatos dentro de la pila\n";
help=top;
while (help!=NULL)
{
cout<<help->data<<"---";
help=help->foward;

}
cout<<"NULL";
}
main()
{
pile(12);pile(13);pile(14);pile(15);
list();
getch();
}

Donde su ejecucion seria :





Mas caerca de la recursividad aplicada a otras operciones :
https://ccodigo.wordpress.com/tag/recursividad/

Recursividad aplicada a los juegos :

Buscaminas :
http://buscaminas.eu/

1. 1. Recursividad aplicado al juego : busca minas <br />
2. 2. Buscaminas<br />
3. 3. Lógica del juego<br /> Primero hay que entender bien la lógica del buscaminas: la relación entre minas y nivel de advertencia de las casillas limpias - Estructuras según dificultad o tamaño de tablero:    - Cantidad de casillas totales    - Número de minas    - Número de casillas limpias    - Número de casillas de aviso 1    - Número de casillas de aviso 2    - Número de casillas de aviso 3     ...<br />
4. 4.  - Definición del tablero:    - Matriz de 2 dimensiones que almacenará el valor de cada casilla:              * -1 si no ha sido pulsada              * 0 si está limpia              * 1, 2, etc según nivel de alerta              * 9 si tiene mina                 Módulos: - Inserción aleatoria de minas - Asignación de nivel de alerta(nivel de alerta, mapa actual): Se le llamará 1 vez por cada nivel de alerta, de mayor a menor. - Juego: redibujar mientras no se pulsa una mina<br />
5. 5. Ejemplo <br />La recursividad , se muestra en el siguiente ejemplo <br />

Torres de Hanoi :
http://www.uterra.com/juegos/torre_hanoi.php

Ajedrez :
http://ajedrez-online.es/

"El hombre equivocado en el lugar correcto puede hacer la diferencia"
                                          -Half Life-
                     

"You have to learn the rules of the game, 

and then you have to play better than anyone else."

                                              -Albert Einstein-

Ejemplos de Programas con Punteros

PROGRAMA #1

#include <iostream>
using namespace std;
 
int main() {
   char cadena1[] = "Cadena 1";
   char *cadena2 = "Cadena 2";
 
   cout << cadena1 << endl;
   cout << cadena2 << endl; 

   //cadena1++; // Ilegal, cadena1 es constante 
   cadena2++; // Legal, cadena2 es un puntero 

   cout << cadena1 << endl; 
   cout << cadena2 << endl;
 
   cout << cadena1[1] << endl;
   cout << cadena2[0] << endl;
 
   cout << cadena1 + 2 << endl; 
   cout << cadena2 + 1 << endl;
 
   cout << *(cadena1 + 2) << endl; 
   cout << *(cadena2 + 1) << endl; 
   
   return 0;
}

PROGRAMA #2

#include <iostream>
using namespace std;
 
struct stEstructura {
   int a, b; 
} estructura, *e;
 
int main() { 
   estructura.a = 10;
   estructura.b = 32;
   e = &estructura;
 
   cout << "puntero" << endl;
   cout << e->a << endl;
   cout << e->b << endl;
   cout << "objeto" << endl;
   cout << estructura.a << endl; 
   cout << estructura.b << endl; 

   return 0; 
}

Punteros y sus aplicaciones

CONCEPTO

Un puntero es una variable que contiene la dirección de memoria de un dato o de otra variable que contiene al dato en un arreglo. Quiere esto decir, que el puntero apunta al espacio físico donde está el dato o la variable. Un puntero puede apuntar a un objeto de cualquier tipo, como por ejemplo, a una estructura o una función. Los punteros se pueden utilizar para referencia y manipular estructuras de datos, para referenciar bloques de memoria asignados dinamicamente y para proveer el paso de argumentos por referencias en las llamadas a funciones.

Ejemplo breve:

#include <stdio.h>

int main()
{
int a=0; //Declaración de variable entera de tipo entero
int *puntero; //Declaración de variable puntero de tipo entero
puntero = &a; //Asignación de la dirección memoria de a

printf("El valor de a es: %d. \nEl valor de *puntero es: %d. \n",a,*puntero);
printf("La direccion de memoria de *puntero es: %p",puntero);

return 0;
}

Operadores:




Operador de Dirección (&): Este nos permite acceder a la dirección de memoria de una variable.



Operador de Indirección (*): Además de que nos permite declarar un tipo de dato puntero, también nos permite ver el VALOR que está en la dirección asignada.





Incrementos (++) y Decrementos (--)

TIPOS DE PUNTEROS

Punteros Constantes:

Es posible que hayas pensado como declarar un puntero como una constante, tal vez pensaste en un #define, o en un atributo const. Bueno es posible usar el atributo const, pero para un puntero hay que hacerlo de otra forma.

int a=10,b=20;
int * const p = &a; //objeto variable y puntero constante
*p = 15; // Correcto: El valor apuntado es variable.
p=&b; //ERROR: p es constante

Punteros Genéricos:

Un puntero a cualquier tipo de dato puede convertirse a un puntero del tipo void *. Por esto un puntero a void *, recibe el nombre de puntero generico.

En C, se permite la conversión implícita de punteros, pero en C++ esto no es posible, asi que por compatibilidad y buena practica recomendamos usar la conversion explicita (cast).

int *puntero;
funcion (*puntero);
....
void funcion (void *p)

int *q;
q=(int *)p; //En C se podria hacer q = p;

 

Punteros y Matrices:

Anteriormente decíamos que una matriz es una secuencia de espacios en memoria, que nos permitían alojar datos en cada uno y un puntero es una variable que guarda la dirección de memoria, también decíamos como recorre las direcciones de memoria con los operadores ++ y --.

Aquí veremos como puede usarse un puntero como si de una matriz se tratase, luego de que veas que es técnicamente lo mismo, te preguntaras por que usar punteros, pero estos son muy necesarios y únicos que nos permiten realizar cosas que con un array normal, no se puede, como asignarle memoria dinámica, etc...

#include <stdio.h>

int main()
{

int array[10]={0,2,3,5,5,6,7,8,9,0}; //Declarar e inicializar un array.
int *puntero = &array[0]; //Le damos la dirección de inicio del array
int i; //variable contadora...

for (i=0;i<10;i++)
printf("%d\n",*(puntero+i)); //imprimimos los valores del puntero.

return 0;
}

Punteros a cadenas de caracteres:

Ya hemos visto el uso que se le puede dar a un puntero como si de un array se tratase, entonces usando esta misma logica podemos hacer un array de caracteres usando punteros.

char *nombre="Gustavo A. Chavarria";//Es como un array de 20 caracteres
printf("%s",nombre);

Para poder modificar el valor de este puntero, este tendría que apuntar a una dirección que no sea una constante, como un array.

char nombre[]="Gustavo A. Chavarria"; //declaramos un array de caracteres
char *puntero=nombre;//Asignamos al puntero el comienzo del array
printf("%s \nIngrese otro nombre: ",puntero);//Escribimos en pantalla nombre...
gets(puntero); //leemos otro nombre
printf("%s",puntero); //escribimos el nuevo nombre...

Esta vez pudiste notar que si se pudo remplazar el valor del nombre.

Punteros a Punteros:

Es una variable que contiene la dirección de memoria de un puntero, el cual a su vez contiene la dirección de memoria de un tipo de dato. Recuerden que un puntero sigue siendo un espacio en memoria, pero en vez de almacenar un valor almacena una dirección.

int a=0; //Supongamos que es una variable cuya direccion es 0x1601
int *puntero1=&a; //El puntero tiene guardada la direccion de a, 
                  //pero este tiene como direccion 0x1890
int **puntero2=&puntero1; //**puntero 2 guarda la direccion 0x1890

ESTRUCTURAS DE DATOS

ESTRUCTURAS DE DATOS

Podríamos decir que las estructura de datos son formas particulares en las que se pueden organizar los datos para que estos puedan ser usados de manera eficiente. Se pueden desglozar del modo realizado en la imagen superior.

Para emplear algunas estructuras de datos, recomendamos los siguientes videos:

El empleo de Struct

El empleo de arreglos unidimensionales y arreglos multidimensionales

Tipos de datos

 TIPOS DE DATOS

Clasificación de los tipos de datos.

El tipo de dato es un atributo del dato le indica al ordenador con que clase va a trabajar. Esto contribuye a conocer que restricciones tiene ese tipo de dato, que valores puede tomar, y qué operaciones se pueden realizar con el.

Como declarar variables según su tipo en C.

  Video recomendado: