Definición y
ejemplos
Una pila es un conjunto ordenado de elementos en el cual
se pueden agregar y eliminar elementos en un extremo, que
es llamado el tope de la pila
A diferencia del arreglo, la definición de la
pila considera la inserción y eliminaciòn de
elementos, por lo que una pila es un objeto dinámico en
constante cambio. ¿Cómo cambia una pila? La
definición especifica que un solo extremo de la pila se
designa como el tope. Pueden colocarse nuevos elementos en
el tope de la pila (en este caso el tope de la pila sube para
corresponder al nuevo elemento más alto), o se pueden
quitar elementos (en este caso el tope de la pila baja para
corresponder al nuevo elemento más alto). Para contestar
la pregunta cual lado es arriba? debemos decidir
cuál extremo de la pila se designa como el tope, es decir,
en cuál extremo se agregan o suprimen
elementos.
Esto también se indica mediante las líneas
verticales que se extienden más allá de los
elementos de la pila, en dirección al tope.
De acuerdo con la definición, sólo hay un
lugar en la pila donde puede colocarse: en el tope. Ahora, el
elemento superior de la pila es G. Conforme la película
avanza por los cuadros c, d, y e, se agregan sucesivamente a la
pila los elementos H, I y J Observe que el último
elemento agregado (en este caso J), está en el tope de la
pila. Sin embargo, empezando con el cuadro f, la pila empieza a
reducirse, al principio se retira J y después, de
manera sucesiva, se eliminan I, H, G y F. En cada punto se
quita el elemento superior de la pila, porque sólo puede
hacerse una supresión del tope. El elemento G no
podría retirarse de la pila antes que los elementos J,
I y H. Esto ilustra la característica más importante de una
pila, que el último elemento insertado en ella es el
primero en suprimiese. Por tanto, J se retira antes que I, porque
J se insertó después. Por esta razón, en
ocasiones una pila se denomina una lista "último en
entrar, primero en salir" (o LIFO, por sus siglas en inglés).
Entre los cuadros j y k la pila ha dejado de reducirse y
empieza a crecer otra vez conforme se añade el elemento K.
Sin embargo, esta expansión es de corta duración y
la pila se reduce a sólo, tres elementos en el cuadro
n.
Observe que no se pueden diferenciar los cuadros a e i
al observar el estado de
la pila en los dos casos. En ambos casos la pila contiene
elementos idénticos en el mismo orden y tienen el misma
tope. En la pila no se conserva un registro de que,
entre esos dos periodos, se han agregado y, removido cuatro
elementos. De igual modo, no es posible diferenciar los cuadros d
y f, oj y l. Si se,, necesita un registro de los
elementos intermedios que han estado en la
pila, debe con otra parte; no existe dentro de la pila
misma.
De hecho, hemos tenido una imagen exagerada
de lo que realmente ocurre en ti verdadera imagen de una
pila la proporciona una vista desde el tope ¡lacia abajo, y
no de hacia adentro. Por tanto, no hay una diferencia notable
entre los cuadros h y En cada caso el elemento en el tope es
G. Si bien la pila en el cuadro 11 y la pila en el cuadro
o iguales, la 4nica forma de determinar esto es quitar todos los
elementos de ambas pila,. compararlos individualmente. Aunque
hemos hecho cortes en las pilas para
comprenderlas e mayor claridad, debe señalarse que
sólo se hizo con fines didácticos .
REPRESENTACION DE PILAS EN
C
Antes de programar una solución de un problema
que emplee una pila, debemos decidir cómo representar una
pila usando las estructuras de
datos que
existen en nuestro lenguaje de
programación. Como veremos, hay varias formas de
representar una pila en C. Por el momento, consideraremos
la más simple de ellas. En todo el texto,
presentaremos otras representaciones posibles. Sin embargo, cada
una de ellas es sólo una implementación del
concepto
introducido en la sección 2. l.
una tiene ventajas y desventajas, en términos
de la fidelidad con la que refleja el concepto de una
pila y el esfuerzo que deben aportar el programador y la
computadora para usarla.
Una pila es un conjunto ordenado de elementos y C ya
contiene un tipo de datos que es un
conjunto ordenado de ellos: el arreglo. Por tanto, cuando una
solución de un problema requiere que se uw una
pila, es adecuado empezar un programa
declarando una variable stock como un arreglo. Sin
embargo, una pila y un arreglo son dos cosas completamente
distintas. La cantidad de elementos en un arreglo es fija y se
asigna mediante la declaración para el arreglo. En
general, el usuario no puede, cambiar esta cifra. Por otra parte,
una pila es fundamentalmente un objeto dinámico cuyo
tamaño se modifica en forma continua, conforme se agregan
y remueven elementos.
No obstante, aunque un arreglo no puede ser una pila,
puede alojar una. Es decir, puede declararse un arreglo
suficientemente grande para el máximo tamaño de la
pila. Durante el curso de la ejecución del programa, La pila
puede crecer y reducirse dentro del espacio reservado para ella.
Un extremo del arreglo es la parte inferior fija de la pila,
mientras que el tope de ella cambia constantemente conforme se
agregan y remueven elementos. Por tanto, se requiere otro campo
que, en cada punto de la ejecución del programa,
registre la posición actual del tope de la
pila.
Por eta razón, una pila en C se declara
como una estructura que
contiene dos objetos: un arreglo para contener los elementos de
la pila y un entero para indicar la posición del tope de
la pila actual dentro del arreglo. Esto se hace para una pila de
enteros mediante las declaraciones
t~ne STWIZE 1 00
W"ct stack 1
int top;
int ftems [STACKSIZEI;
l;
Una vez que se ha hecho esto, se declara una pila
real mediante
dmct stack s;
Aquí, suponemos que los elementos de la pila s
contenidos en el arreglo s.items son enteros y que
la pila en ningún momento contendrá más que
enteros STACKSIZE.(tAmafío de la pila). En este
ejemplo, STA CKSIZE se establece en 1 00 para indicar que
la pila puede contener 1 00 elementos (de ¡tems[O] a
¡tems[991).
Por supuesto, no hay razón para limitar a una
pila para que sólo contenga enteros; los
¡tems (elementos) podrían haberse declarado
comofloat ¡tenls[STACKSIZE] o char
¡tems[STACKSIZEJ o cualquier otro tipo que
deseáramos dar a los elementos de la pila. De hecho, si.
fuera necesario, una pila puede contener objetos de tipos
diferentes por medio del uso de uniones en C. Por
tanto
#define STACKSIZE 1 00
#define INT 1
#define FLOAT 2
#define STRING 3
estruct stackelement (
int etype; etype es Igual a INT, FLOAT o STRING
dependiendo del típo de elemento correspondiente.
union 1
int ¡va¡;
float fval;
char *pval; 1* apuntador a una
cadena
1 element;
struct stack 1
int top;
struct stackelement Rems
[STACKSIZEI;
l;
define una pila cuyos elementos pueden ser enteros,
números de punto flotante o cadenas,
dependiendo del valor del
etype correspondiente. Dada una pila s declarada
mediante
struct stack s;
podríamos imprimir el elemento superior de la
pila de modo siguiente:
struct stackelement se;
se = s. ¡te"' [S.topl;
ms
.switch
(se.etype) 1
case INTGR printf("% dkn', se.ival);
case FLT: pñnff('% f@n',
se.fval);
case STRING :,. , printf("% s@n',
se.pval);
fin @e,,Swit@h
Para simplificar, en el resto de esta sección
suponemos que se declara una pila que sólo tiene elementos
homogéneos (es decir, que no se requieren uniones). El
identificador top (parte superior o tope) siempre debe declararse
como entero, dado que su valor
representa la posición dentro del arreglo
¡tems del elemento en el tope de la pila. Por tanto,
si el valor de
s.top es 4, hay cinco elementos en la pila: s.
¡tems[Ol, s. ¡tems[ 1 1, s. ¡tenls[2], s.
¡teins(31 y s. ¡tenis[4]. Cuando se remueve de la
pila, el valor de
s.top cambia a 3, para indicar que ahora sólo hay 4
elementos en la pila y que s.item[31 es el elemento
superior. Por otra parte, si se agrega un elemento nuevo a la
pila, el valor de
s.top debe incrementarse en 1 para llegar a 6 y el objeto
nuevo insertado en s.item[51.
La pila vacía no contiene elementos y, por tanto,
se indica mediante top igual a -l. Para inicializar una pila
s para un estado
vacío, se ejecuta al inicio s.top = -I;
Para determinar durante el curso de la ejecución
si una pila está vacía o no, se verifica la
condición s.top = = -l en un enunciado if del modo
siguiente:
if (S.top == -l)
1* la píla está
vacía
cise
1* la pila no está
vacía
Esta prueba corresponde a la operación
enipty(s) introducida en la sección 2. l. 0 bien se
puede escribir una función que retorne TRUE si la
pila está vacía y FALSE si no lo
está, del modo siguiente:
int empty(struct stack *ps)
1
if (P$->top == -l)
retum(TRUE);
clac
return(FALSE);
1 /*fin de empty'l
Una vez que existe esta función, se implementa
una prueba de la pila vacía mediante el
enunciado
if (empty (&s»
1* la píla está
vacía
cise
la píla no esta' vacía
Observe la diferencia entre la sintaxis de la llamada a
ei7il)ty en el algoritmo de
la sección 2.1 y en el segmento de programa que
presentamos aquí. En el algoritmo v
representaba a una pila y la llamada a empty se expresaba
como
empty (s)
En esta sección, nos interesa la
implementación real de la pila y sus operaciones. Dado
que los parámetros en C se pasan mediante valor, la
única forma de modificar el argumento que se pasa a una
función, es pasar la dirección del argumento en lugar del
argumento mismo. Además, la definición original de
C (de Kemighan-Ritchie) y muchos compiladores de C
anteriores no permiten que se pase una estructura
como argumento, incluso si -,u valor no se altera. (Aunque esta
restricción se ha omitido en el ANSI de C, por lo general
es más eficiente pasar un apuntador cuando la estructura es
grande.) De esta manera, en funciones como
pop y push (las cuales modifican sus argumentos de
estructura),
al igual que emipty (que no lo hace) adoptamos la
convención de pasar la dirección de la estructura de
la pila, en lugar de la pila misma.
Tal vez se pregunte por qué nos molestamos en
definir la función emnty cuando podríamos escribir
simplemente ifs.top = = -l cada vez que deseáramos
verificar la condición de vacío. La respuesta es
que queremos hacer nuestros programas
más comprensibles y que el uso de la pila sea
independiente de su implementación. Una vez que
comprendemos el concepto de pila,
la frase "enipty(&s)", es más significativa que
la frase "s.t(,I) = = – 1 ". Si después debei-nos
introducir una mejor implementación de una pila, de modo
que "s.tol) = = – 1 " ya no tenga significado,
tendríamos que cambiar cada referencia al campo
identificador s.tol) en todo el programa. Por
otra parte, la frase "enipo," (&Y)", todavía
conservaría su significado, porque es un atributo
implícito en el concepto de pila
y no en la implementación de tal concepto. Para
revisar un programa que contenga una nueva implementación
de la pila, sólo se requeriría una posible
revisión de la declaración de la estructura
stack en el programa principal y volver a escribir la
función empty. (También es posible que la
forma de la llamada a ei;il)@i.? tuviera que modificarse para que
no usara una dirección.)
Acumular el conjunto de puntos problemáticos que
dependen de la implementación de unidades pequeñas
de fáciles de identificar es un método
importante para hacer más comprensible y modificable un
programa. Este concepto se conoce como modula y actua en
donde las funciones
individuales se aislan en módulos de bajo nivel
cuyas propiedades se verifican con facilidad. Después,
estos módulos de bajo nivel se usan mediante rutinas
más complejas, las cuales no se complican con los detalles
de los módulos de bajo nivel sino con sus funciones. De
esta forma, las rutinas complejas se aprecian por sí solas
como módulos a través de rutinas de un nivel
todavía más alto que las usan independientemente de
sus detalles internos.
Un programador siempre debe preocuparse por la
legibilidad del código que produce. Un poco de
atención a la claridad ahorrará gran cantidad de
tiempo de
depuración. Los programas grandes
y medianos casi nunca se corregirán la primera vez que se
ejecuten. Si se toman precauciones en el momento de escribir un
programa para asegurarse de que sea modificable y comprensible,
se reduce mucho el tiempo necesario
para ejecutarlo en forma correcta. Por ejemplo, el enunciado en
la función podría sustituirse por el enunciado
más corto y eficiente
return (ps->top == -l);
Este enunciado es precisamente equivalente al enunciado
más grande
if (ps->Igp== -l)
return(TRUE);
cise return(FALSE);
Esto se debe a que el valor de la expresion >top
== -l es TRUE (verdadero) si y sólo si la
condición ps- >top == -l es TRUE. Sin
embargo, es probable que si alguien lee el programa se sienta
mucho más cómodo si aparece el enunciado ¡f.
Con frecuencia, se encontrará con que si usa "trucos" del
lenguaje il
escribir programas, no
será capaz de descifrar sus propios programas
después de hacerlos a un lado por un día o
dos.
Aunque es cierto que a un programador en C le interesa
la economía
del código, también es importante considerar el
tiempo que sin
duda se dedicará a depurarlo. Un profesional experimentado
(en C u otro lenguaje) se
interesa constantemente en el equilibrio
adecuado entre la economía la claridad
del código.
Trabajo realizado Por B. N. William Andrade