Pilas y colas en C++
Enviado por Yhoxin J Rossell • 20 de Marzo de 2022 • Informes • 1.900 Palabras (8 Páginas) • 385 Visitas
[pic 1]REPÚBLICA BOLIVARIANA DE VENEZUELA[pic 2]
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
VICEMINISTERIO DE EDUCACIÓN PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL POLITÉCNICA DE LA FUERZA ARMADA NACIONAL BOLIVARIANA
NÚCLEO FALCÓN; SEDE CORO
PERÍODO ACDÉMICO 1-2021
NOMBRE: Yhoxin Jesús Rossell Gómez C.I.: 28.289.663
CARRERA: Ingeniería de sistemas ASIGNATURA: Lenguaje de Programación I
FACILITADORA: MsC. Mariugenia Smith Aular
TÍTULO: PILAS Y COLAS EN C++
- PILAS
Las pilas (o stacks) son estructuras de datos que permiten dos tipos de operaciones:
- Apilar (push), poner un dato,
- Desapilar (pop), sacar un dato
La diferencia con las colas, es que las pilas, a la hora de sacar los datos (desapilarlos), el primer dato en salir es el último que se apiló. Esto se conoce como la propiedad LIFO (Last In, First Out).
Ejemplo:
[pic 3]
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.
[pic 4]
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.
Existen diferentes formas de crear pilas, por ejemplo, creando estructuras o clases que incluyan punteros (los cuales señalarán a una posición de memoria para cargar los datos), funciones para operar con otras pilas, otras clases dentro de la misma, etcétera. Sin embargo, crear una pila de esta manera puede resultar muy complejo y hace que el código sea más extenso, por lo que existe un método para crear las pilas ahorrando muchísimo código, utilizando una librería específicamente creada para esta función.
La librería stack permite el trabajar con pilas de una manera más dinámica, utilizando funciones propias de sí para modificarlas.
Ejemplo:
[pic 5]
Los comandos push, top y pop tienen la facultad de añadir un elemento, mostrarlo y eliminarlo respectivamente. Cabe recalcar que en las pilas no existen índices como en los arreglos, por lo que solo se puede acceder a un solo elemento, el cual es el de la cima; para acceder a uno en específico, hay que eliminar los demás elementos añadidos después de él, pero bajo ciertos criterios, como encontrar el elemento de mayor o menor tamaño.
Ejemplo:
[pic 6]
El resultado en este caso, sería el número 25 impreso en pantalla, puesto que es el número mayor dentro de la pila, y el número 21, último en entrar, fue eliminado, pasando a estar el 25 en la cima.
Pilas alojadas en arreglos:
Resulta conveniente el almacenamiento secuencial para el tratamiento de pilas. Podemos tener una variable que represente a la cima, que contenga el índice donde está ubicada la cima de la pila dentro del arreglo. Cuando la pila está vacía, la variable que represente a la cima va a ser igual a cero.
Por ejemplo, se puede definir una constante que tenga el valor máximo de elementos que podrá contener la pila, una cima con la última posición, un valor que se ingresará, y el arreglo mismo.
#define ELEMENTOS 10;
int tope = -1; (Inicializamos a la variable tope con el valor -1 para que represente a la pila vacía porque el primer elemento tiene índice 0.
int pila[ELEMENTOS];
int valor;
Un arreglo constituye el depósito de los elementos de la pila. El rango del arreglo debe ser lo suficientemente amplio para poder contener el máximo previsto de elementos de la pila. Un extremo del arreglo se considera el fondo de la pila, que permanecerá fijo, mientras que la cima estará cambiando de posición de manera dinámica mientras se ejecuta el programa.
Implementación de procedimientos recursivos mediante pilas:
Un procedimiento o función contiene tanto variables locales como argumentos ficticios o parámetros. A través de los argumentos se transmiten datos en las llamadas a los subprogramas, o bien, se devuelven valores al programa o subprograma invocador. Además, el subprograma debe guardar la dirección de retorno al programa que realiza la llamada. En el momento en que termina la ejecución de un subprograma el control pasa a la dirección guardada.
Ahora, el subprograma es recursivo, entonces además de la dirección de retorno, los valores actuales de las variables locales y argumentos deben de guardarse ya que se usarán de nuevo cuando el subprograma se reactive. Supongamos que se ha llamado al subprograma P, que tiene llamadas a sí mismo, es decir, es recursivo. El funcionamiento del programa recursivo P será: ü se crea una pila para cada argumento. ü se crea una pila para cada variable local. ü se crea una pila para almacenar la dirección de retorno. Cada vez que se hace una llamada recursiva a P, los valores actuales de los argumentos y de las variables locales se meten en sus pilas para ser procesadas posteriormente. Asimismo, cada vez que hay un retorno a P procedente de una llamada recursiva anterior, se restauran los valores de variables locales y argumentos de las cimas de las pilas. Para la obtención de la dirección de retorno es de suponer que el procedimiento P contiene una llamada recursiva en la sentencia N. Entonces guarda en otra pila la dirección de retorno, que será la sentencia siguiente, la N+1. De tal forma que cuando el nivel de ejecución del procedimiento P actual termine, o sea, alcance la sentencia end final, usará dicha pila de direcciones para volver al nuevo nivel de ejecución.
...