Uff! El tema es muy denso para explicar en un sólo mensaje. Pero
vamos a intentarlo. Intenta, en un primer momento, olvidar que sabes
C/C++ o cualquier otro lenguaje.
Sabes, desde los 10 años, que los enteros ( o los naturales,
racionales) son un tipo de números dotados de ciertas operaciones (la
suma, el producto...). Allá por el último cuarto del siglo XIX, los
matemáticos europeos (Dedekind, Hilbert, Noether, Peano, Cantor y
otros... ) intentaban caracterizar las propiedades de esos "entes" y
sus operaciones. Te sonaran las propiedades commutativa, asociativa,
y algún valor especial como el elemento neutro,
y los términos anillo, semigrupo, grupo conmutativo...
En computación, esos enteros y sus operaciones tienen una
representación trivial y limitada en el computador (int, con MAX_INT,
etc...) que se proyecta en palabras de 8 o 16 bits y operaciones
básicas en la ALU...
Sin embargo, en algoritmia se necesitan además otros "tipos de
datos", como los que mencionas, (pila, cola, listas...) que también
se caracterizan por unas propiedades. Éstas también se pueden
expresar algebraicamente (aunque ya casi nadie lo practica,
)
En el caso de las pilas de enteros (stack), la estructura lineal más
sencilla, tenemos 3/4 operaciones.
Las operaciones, grosso modo, se dividen en tres grupos.
- constructoras
- modificadoras
- consultoras.
El primer axioma dice que al quitar (pop) un elmento de una pila (p)
a la que por lo menos se le ha añadido (push) un entero (i), nos
queda esa pila sin el elemento. Esto también lo sabes "por sentido
común", pero la novedad, repito, es la forma matemática, cuyo origen
debemos a los europeos del finales del s. XIX.
Y aquí entra el lenguaje C. Como no están implementadas a nivel
hardware, el lenguaje nos permite "simularlas" (ojo a la palabra, es
clave) con construcciones que tienen su base en elementos conocidos,
como arrays, punteros...
Los que programan la STL de C++ las ponen a tu disposición una serie
de estructuras (<stack>, <queue>, <list>) para que las uses en tus
algoritmos. Son de muy alta calidad y su implementación escapa a la
de cualquier principiante.
Pero podemos experimentar haciéndo las nuestras "de juguete".
- Para empezar, lo haremos con memoria estática, (arrays...)
- En otro correo, si quieres, las podemos hacer con memoria dinámica
(punteros)
Observa que, al igual que con los int, al usar una array fijo de
elementos, la expresividad de nuestra implementación esta limitada a
un número maximo de elementos apilados.
Al margen de esto, una operación no es aplicable siempre, como la
división por 0. Es el caso de la operación pop, o head. No son aplicables
sobre pilas vacías
En esos casos, su comportamiento está indefinido, por eso se emplea
la libreria <assert.h>.
vamos a intentarlo. Intenta, en un primer momento, olvidar que sabes
C/C++ o cualquier otro lenguaje.
Sabes, desde los 10 años, que los enteros ( o los naturales,
racionales) son un tipo de números dotados de ciertas operaciones (la
suma, el producto...). Allá por el último cuarto del siglo XIX, los
matemáticos europeos (Dedekind, Hilbert, Noether, Peano, Cantor y
otros... ) intentaban caracterizar las propiedades de esos "entes" y
sus operaciones. Te sonaran las propiedades commutativa, asociativa,
y algún valor especial como el elemento neutro,
Código [Seleccionar]
sets
int
operations
+ : (int, int) -> int
constants
0 : int
axioms
a + b = b + a [comm]
(a + b) + c = a + (b + c) [assoc]
a + 0 = a [e.neutro]
....y los términos anillo, semigrupo, grupo conmutativo...
En computación, esos enteros y sus operaciones tienen una
representación trivial y limitada en el computador (int, con MAX_INT,
etc...) que se proyecta en palabras de 8 o 16 bits y operaciones
básicas en la ALU...
Sin embargo, en algoritmia se necesitan además otros "tipos de
datos", como los que mencionas, (pila, cola, listas...) que también
se caracterizan por unas propiedades. Éstas también se pueden
expresar algebraicamente (aunque ya casi nadie lo practica,
)En el caso de las pilas de enteros (stack), la estructura lineal más
sencilla, tenemos 3/4 operaciones.
Las operaciones, grosso modo, se dividen en tres grupos.
- constructoras
- modificadoras
- consultoras.
Código [Seleccionar]
sets
stack, int, bool
constants
empty : stack
operations
push : (stack,int) -> stack
pop : stack - -> stack
head : stack - -> int
isempty : stack -> bool
var
i : int
p : stack
axioms
pop(push(p,i))=p
head(push(p,i))=i
isempty(empty)=true
...El primer axioma dice que al quitar (pop) un elmento de una pila (p)
a la que por lo menos se le ha añadido (push) un entero (i), nos
queda esa pila sin el elemento. Esto también lo sabes "por sentido
común", pero la novedad, repito, es la forma matemática, cuyo origen
debemos a los europeos del finales del s. XIX.
Y aquí entra el lenguaje C. Como no están implementadas a nivel
hardware, el lenguaje nos permite "simularlas" (ojo a la palabra, es
clave) con construcciones que tienen su base en elementos conocidos,
como arrays, punteros...
Los que programan la STL de C++ las ponen a tu disposición una serie
de estructuras (<stack>, <queue>, <list>) para que las uses en tus
algoritmos. Son de muy alta calidad y su implementación escapa a la
de cualquier principiante.
Pero podemos experimentar haciéndo las nuestras "de juguete".
- Para empezar, lo haremos con memoria estática, (arrays...)
- En otro correo, si quieres, las podemos hacer con memoria dinámica
(punteros)
Observa que, al igual que con los int, al usar una array fijo de
elementos, la expresividad de nuestra implementación esta limitada a
un número maximo de elementos apilados.
Al margen de esto, una operación no es aplicable siempre, como la
división por 0. Es el caso de la operación pop, o head. No son aplicables
sobre pilas vacías
En esos casos, su comportamiento está indefinido, por eso se emplea
la libreria <assert.h>.
Código (c) [Seleccionar]
#ifndef _STACK_TOY_
#define _STACK_TOY_
#define MAXIMUM 200
#include <assert.h>
typedef struct
{
// I : 0 <= many <= MAXIMUM
unsigned int many;
unsigned int M[MAXIMUM];
} STACK, *PSTACK;
void empty( PSTACK pstack)
{
pstack->many = 0 ;
}
void push(PSTACK pstack, const int i)
{
assert((pstack->many)<MAXIMUM);
pstack->M[pstack->many++]=i;
return;
}
void pop(PSTACK pstack)
{
assert((pstack->many)>0);
pstack->many--;
return;
}
int head(const PSTACK pstack)
{
assert((pstack->many)>0);
return pstack->M[pstack->many -1];
}
int isempty(const PSTACK pstack)
{
return (pstack->many == 0 );
}
#endif
Quizás una forma "repeat until" sería de lectura más fácil, pero lo dejo así, por ser la forma canónica de la derivación dijkstra... 
El 
)