ESTRUCTURA LIFO:
PILAS DE DATOS
1. PILAS
Una pila es un método de
estructuración datos
usando la forma LIFO
(último en entrar, primero
en salir), que permite
almacenar y recuperar
datos.
Una pila es un
Los objetos se pueden
contenedor de objetos
insertar en cualquier
que se insertan y
momento, pero sólo el
extraen de acuerdo al
último (el insertado más
principio de último en
reciente) objeto puede
entrar, primero en salir
ser extraído.
(last-in-first-out, LIFO).
Operaciones de las Pilas
• InicializarPila(Pila)
Efecto: recibe una pila y la inicializa para su trabajo normal.
• EliminarPila(Pila)
Efecto: recibe una pila y la libera completamente
• EstaVacia(Pila)
retorna -> Boolean
• Efecto: Devuelve true si esta vacia y false en caso contrario
•Pop(Pila)
InicializarPila(Pila)
Efecto: recibe una pila y la inicializa
retorna para su trabajo normal.
-> elemento
•Efecto:
EliminarPila(Pila)
Recibe la pila, remueve el elemento tope y lo retorna
Excepcion: Sirecibe
Efecto: la pila una
estapila y laproduce
vacia, libera completamente
error
•• EstaVacia(Pila)
Push(pila, elemento)
Efecto: Toma la pila yretorna
aumenta -> Boolean
su tamaño, poniendo
el elemento en la cima de la pila
•• Efecto: Devuelve true si esta vacia y false en caso contrario
TopePila(Pila)
Pop(Pila) retorna -> elemento
Efecto: Devuelve el elemento retorna
cima->deelemento
la pila.
Efecto: Recibe
Excepcion: Si lalapila
pila, remueve
esta el elemento
vacía produce error.tope y lo retorna
Excepcion: Si la pila esta vacia, produce error
• Push(pila, elemento)
Efecto: Toma la pila y aumenta su tamaño, poniendo
el elemento en la cima de la pila
•
OPERACIONES BASICAS DE LA PILA:
Push
Pop
Inserta un elemento en la pila, cuando Remueve el elemento tope de la
se puede pila, y lo devuelve.
Si la pila esta llena, no se puede Recuerde, el tope cambia
insertar Si la pila esta vacía, no se puede
Error sacar nada
Error, y devuelve valor invalido
Este elemento es el nuevo tope
El tope aumenta
ANALISIS
• Cada elemento ingresado
puede ser “metido” en la pila
Una vez llenada la pila,
• Ejemplo: Solo hay que “sacar”,
elemento tras elemento
Hasta que la pila quede
vacía
7 5 3 1
OTRAS OPERACIONES
Al remover el ultimo elemento de una pila esta queda
vacía
Una vez vacía, no se pueden “sacar” mas elementos de
la pila
Antes de sacar un elemento de la pila
Debemos saber si la pila Esta Vacía?: EstaVacia(s)
El tope de la pila siempre esta cambiando
Deberíamos poder “revisar” el elemento tope de la pila:
TopePila(s)
Si la pila esta vacía, no debe existir un valor tope
El tratar de remover elementos o acceder a elementos de
una pila vacía se llama SUBDESBORDAMIENTO de la
pila.
Elementos de la pila
Puede contener información de cualquier tipo, es decir, es genérico
IMPLEMENTACIÓN UTILIZANDO
ARREGLOS:
Para implementar una pila utilizando un arreglo, basta con definir el arreglo del tipo
de dato que se almacenará en la pila.
2. COLAS
Una cola es una estructura de datos, caracterizada por ser una secuencia
de elementos en la que la operación de inserción push se realiza por un
extremo y la operación de extracción pop por el otro.
También se le llama estructura FIFO (del inglés First In First Out), debido a
que el primer elemento en entrar será también el primero en salir.
Ejemplos de colas:
Cola de Cola de Cola de
automóviles clientes en programas en
esperando una ventanilla espera de ser
servicio en del banco ejecutados
una para pagar un por una
gasolinera. servicio. computadora.
Simple
TIPOS
Doble DE Circular
COLAS
De
Prioridades
• Cola Simple:
• Estructura lineal donde los elementos salen en el
mismo orden en que llegan.
• Cola circular:
• Representación lógica de una cola simple en un
arreglo.
• 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 Doble (Bicola):
• Estructura lineal en la que los elementos se
pueden añadir o quitar por cualquier extremo de
la cola (Cola bidireccional).
Operaciones:
• 1.- Insertar A
• 2.- Insertar B
• 3-.Insertar C
• 4-.Remover Elemento
• 5-. Insertar D
• 6.- Remover Elemento
Operaciones básicas en Colas Simples
• Insertar:
• Almacena al final de la cola el elemento que se recibe
como parámetro.
• Eliminar:
• Saca de la cola el elemento que se encuentra al
frente.
• Vacía:
• Regresa un valor booleano indicando si la cola tiene o no
elementos (true – si la cola está vacía, false – si la cola
tiene al menos un elemento).
• Llena:
• Regresa un valor booleano indicando si la cola tiene
espacio disponible para insertar nuevos elementos (true
– si está llena y false si existen espacios disponibles).
Utilización:
• 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.
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ó.
Algoritmo para Encolar elementos:
Algoritmo Encolar(C: cola, X: ELEMENTO, resp: lógico)
temp: POSICION;
INICIO
Llena?(C,resp);
si resp = cierto entonces
Escribir “Cola llena”;
resp := falso;
sino {la cola no está llena, por lo que procedemos a añadir el elemento}
Obtener(temp);
temp .info := X;
temp.sgte := nil; {porque va a ser el último}
Vacía?(C,resp);
si resp = cierto entonces {será el primero}
C.prim := temp;
sino C.ult.sgte := temp; {será el siguiente al último}
finsi;
C.ult := temp; {porque es el nuevo último elemento}
C.longitud := C.longitud + 1; {pues ahora hay un elemento más en la cola}
finsi;
FIN
Algoritmo para Desencolar elementos
Algoritmo Desencolar(C: cola, X: ELEMENTO, resp: lógico)
temp: POSICION;
tam: numérico;
INICIO
Vacía?(C,resp);
si resp = cierto entonces
Escribir “Cola vacía”;
resp := falso;
sino
temp := C.prim;
E := temp.info;
Tamaño(C,tam);
si tam = 1 entonces
C.ult := nil;
finsi;
C.prim := temp.sgte; {si sólo había un elemento, será nil}
Liberar(temp);
C.longitud := C.longitud -1;
finsi;
FIN
INTEGRANTES:
• Cáceres Ortiz, Antony
• Garcia Paredes Karina
• Garcia Tejada Xiomara
• Infante Chancafe Ingrid
• Marín Abanto Yordy
• Oliva Moncada Eduardo
• Verástegui Arteaga Luis
