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