PILAS

PILAS

Concepto de pila:

Una pila es una estructura de datos lineal en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella.

     Tipos de pilas:

• Estatica
• Dinamica

         Operaciones con Pilas

PUSH (insertar).- Agrega un elementos a la pila en el extremo llamado tope.

POP (remover).- Remueve el elemento de la pila que se encuentra en el extremo llamado tope.

VACÍA.- Indica si la pila contiene o no contiene elementos.

LLENA.- Indica si es posible o no agregar nuevos elementos a la pila. 

      Aplicaciones de Pilas

Las pilas son utilizadas amplia mente 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.

    Notación Postfija e In-fija

notacion posfija :

el orden es primer operando

COLAS

COLAS:

En Programación, se le llama “Cola” al Tipo de Dato Abstracto que es una Lista en la que sus elementos se introducen (Encolan) únicamente por un extremo que le llamamos “Final de la Cola” y se remueven (Desencolan) únicamente por el extremo contrario al que le llamamos “Frente de la Cola” o “Principio de la Cola”.

 OPERACIONES BÁSICAS: 

• Crear: se crea la cola vacía.

• Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.

• Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.

• Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

• Vacía: devuelve cierto si la pila está vacía o falso en caso contrario (empty).

TIPOS DE COLAS: 

• Cola Simple: Estructura lineal donde los elementos salen en el mismo orden en que llegan.
• Cola de Prioridades: Estructura lineal en la cual los elementos se insertan en cualquier posición de la cola y se remueven solamente por el frente.

• Cola circular: Representación lógica de una cola simple en un arreglo.

• Cola Doble (Bicola): Estructura lineal en la que los elementos se pueden añadir o quitar por cualquier extremo de la cola (Cola bidireccional).

REPRESENTACIÓN EN MEMORIA ESTÁTICA Y DINÁMICA: 

• Usando la memoria estática: arreglo con tamaño fijo y frente fijo o movible o representación circular. 

•  Usando la memoria dinámica: Listas ligadas.

APLICACIÓNES:

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

LISTA

LISTA:

Una lista es una estructura de datos dinámica que cumple las siguientes características:

• Dispone de un numero variable de elementos (desde cero hasta "n"). Su tamaño únicamente se limita por la cantidad de memoria que haya disponible en el sistema. Si la lista tiene cero elementos recibe el nombre de "Lista vacía".
• El primer elemento de la lista, cuando ésta no está vacía es conocido y se puede acceder a él siempre que se desee.
• Los elementos de la lista guardan una relación de orden (o precedencia), de forma que para cada uno de ellos es posible saber cual es su "elemento siguiente".

OPERACIONES CON LISTAS

a) Crear una lista.

Lista = Nulo

b) Insertar un nodo a la lista

c) Eliminar un elemento de la lista

TIPOS DE LISTAS:

• Lista simplemente enlazada
• Lista doblemente enlazada
• Lista circular

LISTA SIMPLEMENTE ENLAZADA

Las listas enlazadas o encadenadas son aquellas listas cuyos elementos se encuentran almacenados en posiciones de memoria no contiguas. En este tipo de listas, los nodos tienen la estructura de auténticos registros divididos en unidades de tratamiento mas pequeñas denominadas campos.

Cada nodo está formado por un mínimo de dos campos:

a) Campo información (Campo que contiene el dato)

b) Campo indicador o puntero (Campo que actúa de enlace con el siguiente nodo de la lista en secuencia lógica).

Por convenio: 

a) Cuando se crea una lista, esta debe estar inicialmente vacía.

b) El campo puntero correspondiente al ultimo nodo de la lista apunta a un valor Nulo.

c) Para acceder a un nodo de la lista, se parte del nodo inmediatamente anterior, a excepción del primer nodo, al cual se accede a través de un enlace especial o puntero externo a la lista.

LISTA DOBLEMENTE ENLAZADA

Son aquellas que pueden recorrerse en amabas direcciones gracias a que los nodos que la componen están formados por tres campos:

a) Campo información

b) Campo enlace que apunta al nodo anterior ( el cual nos permite retroceder o recorrer la lista hacia atrás).

c) Un segundo campo enlace que apunta al nodo siguiente de la lista.

LISTAS CIRCULARES

Se caracterizan porque el campo puntero del último nodo, en lugar de apuntar a un valor Nulo, apunta al primer nodo o elemento de la lista, convirtiéndose en una estructura de datos circular.