• Author / Uploaded
• Betty Garcia

Citation preview

Pilas y colas

PILAS Una colección de datos a los cuales se les puede acceder mediante un extremo, que se conoce generalmente como tope. Una pila representa una estructura lineal de datos en que se puede agregar o quitar elementos únicamente por uno de los dos extremos. En consecuencia, los elementos de una pila se eliminan en el orden inverso al que se insertaron. Debido a esta característica, se le conoce como estructura LIFO (last input, first output). Existen muchos casos prácticos en los que se utiliza la idea de pila:  Las pilas con estructuras lineales como los arreglos, ya que sus componentes ocupan lugares sucesivos en la ED y c/u tienen un único sucesor/predecesor, con excepción del primero/último.

Representación de pilas Las pilas no son estructuras fundamentales de datos; es decir no están definidas como tales en los lenguajes de programación. Las pilas para su representación requieren el uso de estructuras de datos, como:

 Arreglos Usando arreglos: Define un arreglo de una dimensión (vector) donde se almacenan los elementos como se muestra en el cuadro. TOPE: Apunta hacia el elemento que se encuentra en el extremo de la pila. (Inicialmente es -1).

 Listas Una lista es una colección lineal de elementos llamados nodos donde el orden de los mismos se establece mediante punteros o referencias y existe un puntero/referencia especial llamado inicio para localizar al primer elemento.

Operaciones básicas con pilas Considerando que se tiene una pila con una capacidad para almacenar un número máximo de elementos –MAX-y que el último de ellos se indica con TOPE, a continuación se presentan los algoritmos de las operaciones mencionadas. Si la pila está vacía, entonces TOPE es igual a 0.

Página 1 de 7

Pilas y colas  Pila_vacía Algoritmo: PILA_vacia (PILA, TOPE, BAND) {Este algoritmo verifica si una estructura tipo pila –PILA—esta vacía, asignando a BAND el valor de verdadero correspondiente. La primera pila se implementa en un arreglo unidimensional de TOPE es un parámetro de tipo entero. BAND es un parámetro de tipo Booleano} 1. Si (TOPE=0) (Verifica si no hay elementos almacenados en la pila) entonces hacer BAND VERDADERO (La pila esta vacía) si no Hacer BAND FALSO (La pila no está llena) 2. {Fin del condicional paso 1}

 Pila_llena Algoritmo: PILA_llena (PILA, TOPE, MAX, BAND) (Este algoritmo verifica si una estructura tipo pila –PILA—esta vacía, asignando a BAND el valor de verdadero correspondiente. La primera pila se implementa en un arreglo unidimensional de MAX es un parámetro de tipo entero. BAND es un parámetro de tipo Booleano} 1. Si (TOPE=MAX) entonces hacer BAND VERDADERO {La pila esta llena} si no Hacer BAND FALSO {La pila no esta llena} 2. {Fin del condicional paso 1}

 Insertar un elemento – push-en la pila Algoritmo: Pone (PILA, TOPE, MAX, DATO) (Este algoritmo agrega el elemento DATO es una estructura tipo pila –PILA— si la misma no estaba llena. Actualiza el valor de TOPE. MAX representa el número máximo de elementos que puede almacenar PILA. TOPE es un parámetro de tipo entero) 1. Lamar a Pila_llena con PILA, TOPE, MAX y BAND 2. Si (BAND=VERDADERO) entonces Escribir ―Desordenamiento – Pila llena‖ si no Hacer TOPE TOPE + 1 Pila [TOPE] DATO

Página 2 de 7

Pilas y colas {Actualizar TOPE e insertar el nuevo elemento en el TOPE de Pila} 3. {Fin del condicional paso 2)

 Eliminar -pop –de la pila Algoritmo: QUITA (PILA, TOPE, DATO) {Este algoritmo saca un elemento DATO es una estructura tipo pila –PILA—, si esta no se encuentra vacía. El elemento que se elimine en el que se encuentran en la posición indicada por TOPE} 1. Lamar a Pila_vacia con PILA, TOPE y BAND 2. Si (BAND=VERDADERO) entonces Escribir ―Subdesordenamiento – Pila Vacía‖ si no Hacer DATO PILA [TOPE] y TOPE 3. {Fin del condicional paso 2}

TOPE -1 {Actualiza TOPE}

Aplicaciones de pilas Las pilas son un EDs muy usadas en la solución de diversos tipos de problemas, en el área de computación. Algunos de los casos más representativos de aplicación de las mismas son:    

Llamadas a subprogramas Recursividad Tratamiento de expresiones aritméticas Ordenación

Llamadas a subprogramas Cuando se tiene un programa que llama a un subprograma, también conocido como módulo o función, internamente se usan pilas para guardar el estado de las variables del programa, así como instrucciones pendientes de ejecución en el momento que se hace la llamada. Cuando termina la ejecución del subprograma, los valores almacenados en la pila se recuperan para continuar con la ejecución del programa en el punto en el cual fue interrumpido. Además de las variables se recupera la dirección del programa en la que se hizo la llamada, porque a esa posición se regresa el control del proceso.

Recursividad La recursión es un recurso que permite expresa soluciones simples y naturales aciertos tipos de problema, hay que tomar en cuenta que todos los problemas son naturales recursivos; algunos si y algunos no. Los arboles estos representan las estructuras de datos, no lineales y

Página 3 de 7

Pilas y colas dinámicas más eficientes que existan en la computación, es decir que en cualquier actividad de programación que se realice con árboles se utiliza la recursividad. La recursión se puede representar de dos maneras diferentes:  Directa  Indirecta Función de la recursividad Las pilas pueden ser usadas para implementar la recursión en programas. Una función o procedimiento recursivo es aquel que se llama a sí mismo.  Algoritmos datos

Ejemplos:  Factorial  Números de Fibonacci  Torres de Hanoi

de

Ordenamiento

de

Tratamiento de expresiones aritméticas Consiste en convertir expresiones en notación infija a su equivalente en notación prefijado posfija.

Ordenación Significa reagrupar o reorganizar un conjunto de datos u objetos en secuencia especifica.

Ejemplo: // Funcion factorial public static int factorial(int n) { if (n