Estructura De Datos

ESTRUCTURA PILA

Pila o stack es una lista de elementos a la cual se puede insertar o eliminar elementos únicamente por uno de los extremos (llamado tope). Por tal motivo, el último elemento que se inserta en la pila es el primero que se saca. (last-in first-out) (LIFO) (Ultimo en entrar primero en salir). Las pilas pertenecen al grupo de estructuras de datos lineales, ya que los componentesocupan lugares sucesivos en la estructura.

La pila puede ser implementada por medio de arreglos o listas ligadas.

UNA PILA DE SEIS ELEMENTOS:

| |
|F |
|E |
|D |
|C |
|B|
|A |

OPERACIONES BASICAS EN UNA PILA.

PUSHED. OPERACIÓN QUE AGREGA UN ELEMENTO EN LA PILA. DADA UNA PILA S Y UN LEMENTO I LA OPERACIÓN PUSH(S,I) SE DEFINE COMO LA ACCION DE AGREGAR EL ELEMENTO I A LA PARTE SUPERIOR DE LA PILA S.

POP. OPERACIÓN QUE RETIRA UN ELEMENTO SUPERIOR Y LO REGRESA COMO UN VALORDE LA FUNCION POP(S). LA OPERACIÓN I:=POP(S) RETIRA EL ELEMENTO DE LA PARTE SUPERIOR DE LA PILA S Y ASIGNA SU VALOR A I.

Si una pila contiene un solo elemento y se realiza la operación de retiro la pila resultante no contendrá elementos y en ese caso se denomina pila vacía. Aunque la operación de push es aplicable a cualquier pila la operación de pop no es aplicable a una pila vacía porque estapila no tiene elementos para ser retirados. Por lo tanto antes de aplicar la operación de retiro a una pila debemos asegurarnos de que no este vacía.

EMPTY. OPERACIÓN DE VERIFICAR SI LA PILA ESTA VACIA.

STACKTOP. OPERACIÓN PARA DETERMINAR EL ELEMENTO SUPERIOR DE LA PILA SIN RETIRARLO. ESTA OPERACIÓN SE PUEDE DESCOMPONER EN OPERACIONES DE POP Y PUSH.

Al igual que la operación pop stacktopno esta definida para una pila vacía. El resultado de tratar ilegalmente de retirar o accesar un elemento de una pila vacía se denomina underflow. Un bajo flujo puede evitarse si se asegura que empty(s) es falso antes de intentar la operación pop(s) o stacktop(s).

UTILIZACION DE UNA PILA.

1. Llamadas a subprogramas. Cuando se tiene un programa que llama a un subprograma, internamente seusan pilas para guardar el estado de las variables del programa en el momento que se hace la llamada, también permite guardar la dirección del programa o subprograma desde donde se hizo la llamada a otros subprogramas para poder regresar y seguir ejecutándolo a partir de la instrucción inmediata a la llamada.
2. Recursión. En algunos lenguajes no se dispone de esta herramienta por lo tanto sesimula a través de una pila. La recursion es la definición de un objeto en términos de una forma simple de él mismo.
3. Tratamiento de expresiones aritméticas. Un problema interesante en computación (en la creación de compiladores) es poder convertir expresiones en notación infija a su equivalente en notación postfija (o prefija).

Explicaremos y ejemplificaremos la última aplicación de lapila:

NOTACION POLACA POSTFIJA O PREFIJA

Dada la expresión A + B se dice que está en notación infija o entrefija debido a la posición del operador (+), entre los operandos (A y B).

Dada la expresión AB+ se dice que está en notación postfija debido a la posición del operador (+), después de los operandos (A y B).

Dada la expresión +AB se dice que está en notación prefija debido a laposición del operador (+), antes de los operandos (A y B).

La ventaja de usar expresiones en notación polaca postfija o prefija radica en que no son necesarios los paréntesis para indicar orden de operación, ya que éste queda establecido por la ubicación de los operadores con respecto a los operandos.

Para convertir una expresión dada en notación infija a una en notación postfija o prefija...