Pilas, listas enlazadas y expresiones (InFija, PreFija Y PosFija) (página 2)

PILAS DINÁMICAS (STACK)

Es la mas sencilla de las estructuras
dinámicas de datos. las
pilas son
utilizadas sobre todo por los sistemas
operativos y controladores de lenguaje de
alto nivel, una pila es dinámica porque crece y se encoge a mediada
que sea necesario o para trabajar con pilas es importante definir
los siguientes procedimientos:

PUSH.- Poner datos en la pila.

POP.- sacar datos de la pila

ERROR.- Pueden sacar datos de pilas
vacías.

APLICACIÓN DE LAS PILAS

Las pilas son utilizadas ampliamente para solucionar una
amplia variedad de problemas. Se
utiliza en compiladores,
sistemas
operativos y en programas de
aplicación. Su implementación se puede hacer
mediante Arrays Y Mediante listas enlazadas.

Un ejemplo de sus aplicaciones podrían ser los
siguientes:

• Los Navegadores en Internet
  almacenan en una pila las direcciones de los sitios
  más recientemente visitados.
• Los editores de texto
  proporcionan normalmente un botón deshacer que cancela
  las operaciones
  de edición recientes y restablece el
  estado
  anterior del documento.

ARRAY

Un array es una estructura de
datos caracterizada por un acceso muy
rápido a cualquiera de sus posiciones, ası como por
un uso optimo de espacio en memoria
(Suponiendo que todas sus posiciones estén ocupadas). Sin
embargo, no resulta adecuado en una gama amplia de problemas
debido especialmente a limitaciones como las
siguientes:

• Es una estructura
  de datos estática, en el sentido de que no puede
  crecer o decrecer para adaptarse a las necesidades de uso. Su
  tamaño debe ser conocido en el momento en que se crea.
  Esta limitación puede dar lugar al desperdicio de
  memoria debido a que su tamaño sea superior al
  realmente necesario o, por el contrario, a la
  finalización abrupta o ordinaria del programa
  debido a que sobrepase su tamaño máximo. Una
  posible solución a este problema consiste en, cada vez
  que sea necesario redimensionar el array, crear uno nuevo y
  copiar los datos al mismo desde el array
  original.
• Algunas operaciones útiles para el manejo de
  datos en estructuras lineales tienen coste lineal en un
  array, lo cual puede suponer una limitación cuando el
  tamaño del array es grande.

LISTAS ENLAZADAS

Una lista enlazada, también llamada lista
encadenada, es una estructura de datos lineal que no presenta las
limitaciones que presenta un array. Sin embargo, son menos
eficientes en el uso de memoria que los arrays, y
algunas operaciones que en un array requieren un
tiempo
constante (por ejemplo, el acceso a una posición
cualquiera del array dado su ındice), en una lista enlazada
tienen complejidad lineal. Por tanto, dependiendo del problema
concreto,
resultara más adecuado utilizar un array o
una lista enlazada.

Una lista enlazada es una estructura de datos lineal
compuesta por nodos, en la cual cada nodo almacena un dato y una
referencia al nodo que le sigue en la estructura. En la siguiente
figura se representa gráficamente un ejemplo de lista
enlazada.

Figura. Ejemplo de lista enlazada. Los
rectángulos representan nodos. Las flechas, referencias al
siguiente nodo. Los rectángulos internos, los datos de
cada nodo.

La lista contiene una referencia al primer nodo de la
misma. A partir de este, cada nodo tiene una referencia al
siguiente, hasta el último, cuya referencia al siguiente
nodo tiene valor null. En
problemas en los cuales el acceso al último nodo debe ser
eficiente, no solo se almacena una referencia al primer nodo,
sino también al último.

En una lista enlazada el acceso al primer y
último nodo es muy eficiente. Sin embargo, el acceso a un
nodo intermedio requiere recorrer la lista desde el principio
hasta la posición de dicho nodo. En muchos problemas, sin
embargo, solo es necesario acceder a las posiciones de los
extremos, por lo que esto no supone una
limitación.

EXPRESIONES InFija, PreFija Y
PosFija

• PreFija:

La Expresión o Notación PreFija nos
indica que el operador va antes de los operandos sus
características principales son:

-Los operandos conservan el mismo orden que la
notación infija equivalente.

-No requiere de paréntesis para indicar el
orden de precedencia de operadores ya que el es una
operación.

-Se evalúa de izquierda a derecha hasta que
encontrémosle primer operador seguido inmediatamente de
un par de operandos.

-Se evalúa la expresión binaria y el
resultado se cambia como un nuevo operando. Se repite este
hasta que nos quede un solo resultado.

Notación prefija: El orden es operador,
primer operando, segundo operando

• InFija:

La Expresión o Notación InFija es la
forma mas común que utilizamos para escribir expresiones
matemáticas, estas notaciones se refiere
a que el operador esta entre los operandos. La notación
infija puede estar completamente parentizada o puede basarse en
un esquema de precedencia de operadores así como el uso
de paréntesis para invalidar los arreglos al expresar el
orden de evaluación de una
expresión:

3*4=12

3*4+2=14

3*(4+2)=18

Notación infija: La
notación habitual. El orden es primer operando, operador,
segundo operando.

• PosFija:

Como su nombre lo indica se refiere a que el operador
ocupa la posición después de los operandos sus
características principales son:

-El orden de los operandos se conserva igual que la
expresión infija equivalente no utiliza
paréntesis ya que no es una operación
ambigua.

-La operación posfija no es exactamente lo
inverso a la operación prefija equivalente:

(A+B)*C AB+C*

Notación postfija: El orden es primer
operando, segundo operando, operador.

EJEMPLO:

Si deseamos representar las expresiones (2+(3*4)) =
x y ((2+3)*4)= x en las tres notaciones
mencionadas, el resultado sería:

EJERCICIOS

1. CONVERSIÓN EXPRESIÓN INFIJA A
   POSFIJA

El siguiente algoritmo
traduce una expresión en notación infija a
notación postfija:

• Entrada: Una lista que contiene los
  términos de la ecuación en notación infija
  (la notación habitual).
• Salida: Una lista que contiene los
  términos de la ecuación en notación
  postfija.
• Datos locales: Una pila, que va a contener
  operadores y paréntesis izquierdos.

INICIO

Crear pila y la lista de salida, inicialmente
vacias.

MIENTRAS lista de entrada no este vacia
y

no se ha encontrado ningun error HACER

Extraer el primer termino de la lista (lo llamaremos
E)

SEGUN-SEA E

CASO E es número :

Insertar E al final de la lista de salida

CASO E es la variable x
:

Insertar E al final de la lista de salida

CASO E es un paréntesis izquierdo
:

Insertar E en la pila

CASO E es un paréntesis derecho
:

MIENTRAS La pila no este vacía
y

su cima no sea un paréntesis izquierdo
HACER

Extraer elemento de la pila

Insertarlo al final de la lista de salida

FIN-MIENTRAS

SI Encontramos el parentesis izquierdo
ENTONCES

Extraerlo de la pila y destruirlo

SINO

Se ha detectado un ERROR 2

FIN-SI

Destruir E

CASO E es un operador :

MIENTRAS La pila no este vacía
y

su cima sea un operador

de precedencia mayor o igual que la de E
HACER

Extraer elemento de la pila

Insertarlo al final de la lista de salida

FIN-MIENTRAS

Insertar E en la pila

FIN-SEGUN-SEA

FIN-MIENTRAS

MIENTRAS Pila no esté vacía
HACER

Extraer elemento de la pila

Insertarlo al final de la lista de salida

FIN-MIENTRAS

Destruir pila

FIN

CONCLUSIÓN

Para concluir tenemos que las pilas las listas
enlazadas, todos sus métodos y
las diferentes expresiones son una de las herramientas
utilizadas para programar y procesar de una manera automatizada
todos los sistemas que
usamos DIA tras DIA en relación a técnicas o
métodos para agilizar operaciones se refiere, es su
principio fundamental dar soluciones a
procesos que
ameritan de largos pasos que dan como resultado el control de un
asusto. Estas herramientas son uno de los instrumentos más
usados en la programación para estructurar y organizar
información.

REFERENCIAS
BIBLIOFRÁFICAS

• Metodología de la Programación,
  PROGRAMACION
  ESTRUCTURADA,

Luis Joyanes Aguilar, Editorial
McGraw-Hill.

• Estructura de Datos , Algoritmos, Abstracción y objetos, Luis
  Joyanes y Ignacio Salonero Martinez, Editorial
  McGraw-Hill
• Guía de Teoría Computación de la UneT
• www.universia.com
• www.altavista.com

Playblue Quintana

San Cristóbal Febrero 2007