Colas Y Pilas

PILAS

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áticadebido 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.

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.

Operaciones

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

• Crear: se crea la pila vacía. (constructor)

• Tamaño: regresa el número de elementos de la pila. (size)

• Apilar: se añade un elemento a la pila.(push)

• Desapilar: se elimina el elemento frontal de la pila.(pop)

• Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)

• Vacía: devuelve cierto si la pila está sin elementos o falso en caso de que contenga uno. (empty).

ESPECIFICACIONES

ESPECIFICACIÓN SEMANTICA Y SINTACTICA

• pila crear ()

Efecto: Devuelve un valor del tipo pila preparado para ser usado y que contiene un valor de pila vacia.Esta operación es la misma que la de las listas generales.

• void destruir (pila *P)

Argumentos: Una pila P.

Efecto: Libera los recursos que mantienen la lista P de forma que para volver a usarla se debe asignar una nueva pila con la operación de creación. Esta operación es la misma que la de las listas generales.

• telemento tope (pila P)

Argumentos: Una pila P que debe ser no vacía.

Efecto: Devuelve el elemento en la cabeza de la pila P. Si, como es lógico, identificamos la cabeza de una pila con la posición 1, entonces TOPE(P) puede escribirse en términos de operaciones de listas como ELEMENTO (PRIMERO(P),P).

• void pop (pila P)

Argumentos: Una pila P que debe ser no vacía. Es modificada.

Efecto: Borra el elemento del tope de la pila P, esto es, BORRA (PRIMERO(P),P). Algunas veces es conveniente implementar POP como una función que devuelve el elemento que acaba de borrar.

• void push (telemento x, pila P)

Argumentos:

x: Un elemento que deseamos poner en la pila.

p: Una pila P valí donde deseamos poner el elemento x.

Efecto:Inserta el elemento x en el tope de la pila P. El elemento tope antiguo se convierte en el siguiente al tope y asi sucesivamente. En términos de primitivas de listas esta operación es INSERTA (x,PRIMERO(P),P).

• int vacia (pila P)

Argumentos: Una pila P.

Efecto: Devuelve si P es una pila vacía.

TIPOS DE PILAS IMPLEMENTADAS CON ARREGLOS Y PUNTEROS

Implementación en base a Punteros: Para la implementación se requiere de celdas con dos componentes, uno destinado a almacenamiento de los datos y otro a un apuntador para indicar la posición de la siguiente celda. Adicionalmente se necesita de otro puntero llamado cima, el que nos proporciona la dirección de última celda en ser colocada en la pila.

Para añadir un elemento X a la pila se debe crear una nueva celda. A X se lo almacena en el campo correspondiente, y el puntero de la nueva celda debe estar dirigido a la celda señalada por cima. Para concluir, cima ahora apuntará a la nueva celda. Este proceso se muestra en el siguiente gráfico:

La eliminación se lleva a cabo por el mismo extremo de la pila. Se toma al elemento de la celda a la que apunta cima y hacemos que cima señale a la dirección que indica el puntero de dicha celda. Finalmente eliminamos la celda.

Implementación con Arreglos

Para la implementación necesitamos un arreglo de dimensión N, al que llamaremos Pila, y un número representado por cima, que corresponde al índice en el arreglo, del último elemento en ser insertado. Para insertar un elemento Y en la Pila, primero se debe comprobar si cima no es igual a N. En caso de ser menor a N se hace lo siguiente:

Cima=cima+1

Pila(cima)=Y

La eliminación consiste en tomar al último elemento en ser insertado y decrementar en una unidad a cima. Cuyo procedimiento se presenta a continuación:

Y=Pila(cima)

Cima=cima-1

Antes de tomar sacar al último elemento de la estructura se debe verificar si cima es diferente de cero, pues si éste fuera el caso la pila estaría vacía.

COLAS

Una cola, es una estructura en la cual se almacenan elementos (en orden de llegada), es decir que, se ingresan los elementos por la parte final de la estructura y se eliminan (o

...