AYUDANTIA 3: PILAS- COLAS
Carlos Pulgar R.
Mail: [email protected]
Página Ayudantía: http://capulgar.wordpress.com/
PARTE 1: PILAS

¿Qué es una Pila?


Son un tipo especial de lista, conocidas como listas
LIFO (Last In, First Out: el último en entrar es el
primero en salir). Los elementos se "amontonan" o
apilan, de modo que sólo el elemento que está encima
de la pila puede ser leído, y sólo pueden añadirse
elementos encima de la pila.
¿Operaciones sobre Pilas?
Ver si esta Vacia.
 Push: Añadir un elemento al final de la pila.
 Pop: Devuelve el elemento almacenado en el tope
(nodo, que dependiendo de la implementación puede
ser el 1° o el que apunta a NULL, pero el mas general
y simple de implementar es eliminar el 1°) y elimina
el nodo.

PARTE 2: COLAS

¿Qué son las Colas?


Tipo de listas, conocidas como listas FIFO (First In,
First Out: El primero en entrar es el primero en
salir). Los elementos se almacenan en fila, pero sólo
pueden añadirse por un extremo y leerse por el otro.
¿Operaciones sobre Colas?
Insertar (Encolar).
 Eliminar (Desencolar).
 Ver si esta vacia.


Otros tipos de colas

Colas de prioridad
EJERCICIOS
1.
2.
3.
4.
Está programando un software de edición de texto, y quiere
implementar una opción de “Deshacer” (el típico CTRL-Z).
¿Qué tipo de estructura de datos usaría para guardar los
datos que requiere Deshacer? Justifique.
Escriba la definición struct que se requiere para un nodo de
una lista doblemente enlazada a través de punteros.
Declaramos una variable int *x;. Si luego escribimos p1=x;
p2=*x; p3=&x; ¿De qué tipo deberían ser p1, p2 y p3? En
palabras, ¿qué le estamos asignando a cada p?
Programe en C una función que permite intercambiar dos
nodos vecinos (los nodos con el contenido y no sólo el
contenido) en una lista cuyos nodos están enlazados a través
de punteros. Los nodos a intercambiar no son el primero ni el
último en una lista con por lo menos 4 elementos. Un
puntero p apunta al primero de los dos nodos. El puntero
lista apunta a la lista. Esta función será una nueva función
del TDA lista.
EJERCICIOS
5.
6.
La Empresa de Ferrocarriles del Estado (EFE) para
realizar su traslado de pasajeros hacia el Sur, ha ido
apilando los carros respectivos en una línea de tren en
una estación; (ver figura). La locomotora se toma como un
carro más.
Justo antes de salir; su conductor se percata que uno sus
carros está defectuoso. Ayúdele a escribir una función
para sacar el carro defectuoso de la línea y dejar los
demás carros en el orden que estaban (misma línea), para
poder cumplir con el itinerario previsto. Los carros tienen
asignado una sigla. El carro defectuoso tiene asignada la
abreviatura “EFE29”. No se sabe en qué lugar está el
carro defectuoso ni tampoco el número de carros
del tren.
Implementar una función Mezcla2 que tenga como
parámetros dos listas de enteros ordenados de menor a
mayor y que devuelva una nueva lista como unión de
ambas con sus elementos ordenados de la misma forma.
RESPUESTAS
1.
2.
Una pila, ya que al apretar CTRL-Z desharemos
primero lo último que habíamos hecho, luego lo
anterior, etc. (es “LIFO”).
stypedef struct NODO
{
tipo dato;
struct NODO *siguiente;
struct NODO *anterior;
} nodo;
3.
ooo
int *p1; /*asignamos un puntero a entero */
int p2; /*asignamos un entero */
int **p3; /*asignamos un puntero a un puntero a
entero */
RESPUESTAS
4)
void intercambia(lista *list, lista *p)
{ lista *aux;
aux=list;
while(aux->sgte!=p)
aux=aux->sgte;
aux->sgte=p->sgte;
p->sgte=p->sgte->sgte;
aux->sgte->sgte=p;
}
RESPUESTAS
5.
void Tren(TPila * tope, TElemento cod)
{
TPila * tope1;
while ( tope -> info != cod)
{
Push(tope1, tope -> info);
Pop(tope);
}
Pop(tope);
while(tope1 != Null)
{
Push(tope, tope1 ->info);
Pop(tope1);
}
}
Descargar

Ayudantia-3-23.04.10