****PILAS****
Una
pila es una lista ordinal o estructura de datos en la que el modo de acceso a
sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar,
primero en salir) que permite almacenar y recuperar datos.
En consecuencia es importante definir
el tamaño de la pila, así como una variable auxiliar a la que se denomina TOPE,
se utiliza para indicar el ultimo elemento que se inserto en la pila, en la
figura anterior se presenta n dos alternativa de presentar un a pila,
utilizando arreglos.
**Política**
Las pilas son listas con una política
de inserción y borrado de elementos especial, por esta razón si no tienes claro
el concepto de lista.
La regla utilizada por una pila es
eliminar siempre el elemento que ha estado en la colección de la menor cantidad
de tiempo. Esta política se conoce como
el último en entrar primero en salir o LIFO.
**Elementos**
Una pila es una estructura en donde
los elementos son insertados y retirados del tope (top) de la misma, debido a
ello el comportamiento de una pila se conoce como LIFO (último en entrar,
primero en salir).
**Aplicación**
Las pilas son una estructura de datos
muy usada en la solución de diversos de
tipos de problemas, en el área de la computación. Si se insertaran los
elementos lunes, martes, miércoles, jueves y viernes en PILA y conforme pasa
los días indicados se elimina con el fin de contabilizarlos.
**Algoritmo**
Algoritmo: Pila _Vacia
(Este
algoritmo verifica si una estructura tipo pila -PILA- está vacía, asignando a
BAND el
valor de
verdad correspondiente. La pila se implementa en un arreglo unidimensional.
TOPE
es un
parámetro de tipo entero. BAND es un parámetro de tipo booleano)
Si (TOPE =O)
(Verifica
si no hay elementos almacenados en la pila)
entonces
Hacer BAND oE-
VERDADERO
(La pila está vacía)
si no
Hacer BAND oE-
FALSO
(La pila no está vacía)
(Fin del condicional
del paso 1)
Algoritmo: Pila_llena
Pila_llena (PILA, TOPE, MAX, BAND)
{Este
algoritmo verifica si una estructura tipo pila -PILA- está llena, asignando a B~ ;O
valor de
verdad correspondiente. La pila se implementa en un arreglo unidimensional de
_t-\..X
elementos.
TOPE es un parámetro de tipo entero. BAND es un parámetro de tipo
boo
Si (TOPE =MAX)
entonces
Hacer BAND oE-
VERDADERO
(La pila está llena)
si no
Hacer BAND oE-
FALSO
(La pila no está llena)
¿. (Fin
del condicional del paso 1)
**Métodos**
Crear: se
crea la pila vacía. (constructor)
Tamaño: regresa
el numero de elementos de la pila. (size)
Apilar: se
añade un elemento a la pila.(push)
Desapilar: se
elimina el elemento frontal de la pila.(pop)
Cima: devuelve
el elemento que esta en la cima de la pila. (top o peek)
Vacía: devuelve
cierto si la pila está vacía o falso en caso contrario (empty).
*****COLAS*****
Una cola es simplemente un lugar para
almacenar cosas, donde esas cosas se insertan una detrás de otra y para extraer
siempre se lo hace por adelante de la cola donde se encuentra el primer
elemento. Una cola funciona como una fila o cola de personas, que esperan su
turno para ser atendidas, la primera persona atendida es siempre la primera de
la fila y cuando llega una persona y queremos incorporarla a cola o adicionarla
debemos hacerlo por detrás de la última persona en la cola.
**Elementos**
Un elemento se inserta en la cola
(parte final) de la lista y se suprime o elimina por la frente (parte inicial,
cabeza) de la lista. Las aplicaciones utilizan una cola para almacenar
elementos en su orden de aparición o concurrencia. Los elementos se eliminan
(se quitan) de la cola en el mismo orden en que se almacenan
** Políticas**
Las colas tiene una política de
inserción y borrado de elementos especial, por esta razón si no tienes claro el
concepto de lista. Los elementos se
eliminan (se quitan) de la cola en el mismo orden en que se almacenan.
La regla utilizada para una cola es
eliminar siempre el elemento que ha estado en la colección de la mayor cantidad
de tiempo. Esta política se conoce como
la primera en entrar primero en salir o FIFO.
** Métodos**
Ahora una vez teniendo esta estructura hay que
definir los métodos principales para manejar una cola, estos métodos son:
esVacia()
: boolean
|
Retorna
verdad si la cola esta vacía es decir no tiene ningún elemento, para esto
solo se pregunta si inicio es igual afín.
|
esLlena()
: boolean
|
Retorna
verdad si es que la cola esta llena, pasa cuando se ha llenado todo el
vector, la cantidad de elemento que permite la cola lo determina la
variable MAXIMO.
|
adicionar(int
a)
|
Adiciona
un nuevo elemento a la cola, para esto solo se incrementa la variable fin y
se coloca el elemento en esa posición.
|
eliminar()
: int
|
Extrae
el primer elemento de la cola, para esto se retorna la posición inicio +
1 del vector y se incrementa inicioen 1.
|
tamanio()
: int
|
retorna
la cantidad de elementos que tiene la cola, para realizar esto se realiza la
resta fin - inicio.
|
copiar(Cola
B)
|
copia
tal cual la cola B a la cola destino, al finalizar cola B queda totalmente
vacía. Este método es muy útil al momento de hacer operaciones con colas.
|
** Aplicación**
Agregar
(push): Para insertar un elemento hay que introducir, en el campo de texto del
diálogo lanzado al pulsar el botón Insertar, el valor deseado. Este valor puede
ser un número entero o una cadena de caracteres.
Quitar
o borrar (pop): Si se desea borrar un nodo se debe seleccionar dicho nodo y
pulsar el botón Borrar.
Vaciar
lista: Esta acción elimina todos los elementos que contiene la cola.
***Algoritmos***
Algoritmo: Inserta_cola
1. Si
(FINAL <
MAX)
{Verifica que hay espacio libre}
entonces
Hacer FINAL +-
FINAL
+
1
{Actualiza FINAL} y COLA[FINAL] +- DATO
1.1 Si (FINAL
= 1) entonces {Se insertó el primer elemento de COLA}
Hacer FRENTE +-
1
1.2 {Fin del condicional
del paso 1.1}
si
no
Escribir
"Desbordamiento - Cola llena"
2. {Fin del
condicional del paso l}
Algoritmo: Elimina_cola
{Este
algoritmo elimina el primer elemento de una estructura tipo cola y lo almacena
en DATO.
FRENTE YFINAL
son los punteros que indican, respectivamente, el inicio y fin de la cola}
1. Si
(FRENTE,. O) {Verifica que la cola no esté vacía}
entonces
Hacer DATO +-
COLA
[FRENTE]
1.1 Si (FRENTE = FINAL)
{Si hay un solo elemento}
entonces
Hacer FRENTE +-
Oy
FINAL +- O{Indica COLA vacía}
si
no
Hacer FRENTE +-
FRENTE
+
1
1.2 {Fin del condicional
del paso l.l}
si
no
Escribir "Subdesbordamiento - Cola
vacía"
2. {Fin del
condicional del paso l}
*******LISTAS*******
Una lista es una colección ordenada de valores.
Una lista puede contener cualquier cosa.
La lista enlazada básica es la lista
enlazada simple la cual tiene un enlace por nodo. Este enlace a punta al
siguiente nodo en la lista, o al valor NULL
o a la lista vacía, si es el último nodo.
***Elemento***
Una
lista es una colección o cargas de elementos,
El recorrido en una lista enlazada es simple, empezamos por el primer
nodo y pasamos al siguiente hasta que la lista llegue al final.
***Política***
Los ArrayList, en cambio, pueden
almacenar un número variable de elementos sin estar limitados por un número
prefijado.
Insertar. Supongamos que desea insertar un
nuevo nodo en una lista enlazada. El lugar más
fácil de hacerlo es en el principio de la lista.
Quitar. Supongamos que desea eliminar el
primer nodo de una lista.
Esta operación es aún más fácil: basta con asignar a la primera first.next
valor.
***Métodos***
Para
el caso de las listas sin nodo de cabecera, se usará la expresión TOP para referenciar al primer nodo
de la lista, y TOP(dato), TOP(liga) para
hacer referencia al dato almacenado y a la liga al siguiente nodo
respectivamente.
***Aplicación***
A veces, las listas enlazadas
son usadas para implementar arrays asociativos, y estas en el contexto de las llamadas
listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay
mejores formas de implementar éstas estructuras, por ejemplo con árboles
binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es
dinámicamente creada fuera de un subconjunto propio de nodos semejante a un
árbol, y son usadas más eficientemente para recorrer ésta serie de datos
***Algoritmo***
Algoritmo
de Creación
top<--NIL
repite
new(p)
leer(p(dato))
si
top=NIL entonces
top<--p
en caso contrario
q(liga)<--p
p(liga)<--NIL
q<--p
mensaje('otro
nodo?')
leer(respuesta)
hasta
respuesta=no
Algoritmo
para Recorrido
p<--top
mientras
p<>NIL haz
escribe(p(dato))
p<--p(liga:)
Algoritmo
para insertar al final
p<--top
mientras p(liga)<>NIL haz
p<--p(liga)
new(q)
No hay comentarios:
Publicar un comentario