ELO320 - Estructuras de Datos y Algoritmos
Tipos de Datos Abstracts
Pilas, Listas Circulares y Colas
Dr. Nicolás Gálvez R.
[Link]@[Link]
Ing. Civil Telemática - Departamento de Electrónica
1er Semestre 2022
1/1
Lista Simple Enlazada: Inicializar
Las listas, en su versión más básica, dependen de un puntero al
inicio de la lista. Éste suele llamarse header, cabecera o inicio.
C
#i n c l u d e <s t d i o . h>
t y p e d e f s t r u c t nodo{
i n t d a t o ; // dato , puede s e r l o que u d s . n e c e s i t e n
s t r u c t nodo ∗ s g t e ; // p u n t e r o a un nodo e n a l c e .
} nodo t ;
i n t main ( i n t a r g c , c h a r ∗∗ a r g v ){
n o d o t ∗ i n i c i o = NULL ;
// I n i c i a l i z a m o s l a l i s t a , con s u p u n t e r o de i n i c i o a p u n t a n d o a NULL
// E q u i v a l e n t e a l i s t a v a c ı́ a [ ]
return 0;
}
2/1
Lista Simple Enlazada: Inicializar
3/1
Lista Enlazada PRO
Existen otras implementaciones de listas enlazadas simples, donde
se incluyen más punteros y variables de control.
C
#i n c l u d e <s t d i o . h>
t y p e d e f s t r u c t nodo{
i n t d a t o ; // dato , puede s e r l o que u d s . n e c e s i t e n
s t r u c t nodo ∗ s g t e ; // p u n t e r o a un nodo e n a l c e .
} nodo t ;
i n t main ( i n t a r g c , c h a r ∗∗ a r g v ){
n o d o t ∗ i n i c i o = NULL ; // pueden u s a r un s t r u c t p a r a e s t o s d a t o s
n o d o t ∗ f i n a l = NULL ;
int largo = 0;
// E q u i v a l e n t e a l i s t a v a c ı́ a [ ]
// ¿ Para que s i r v e e s t a n u e v a f o r m a ?
// I m p l e m e n t e l a s f u n c i o n e s de é s t a c l a s e c o n s i d e r a n d o e s t a f o r m a .
return 0;
}
4/1
Lista Enlazada PRO
5/1
Lista Doblemente Enlazada
C
#i n c l u d e <s t d i o . h>
t y p e d e f s t r u c t nodo{
i n t d a t o ; // dato , puede s e r l o que u d s . n e c e s i t e n
s t r u c t nodo ∗ s g t e ; // p u n t e r o a un nodo s i g u i e n t e , e n a l c e .
s t r u c t nodo ∗ p r e v ; // p u n t e r o a un nodo p r e v i o , e n a l c e .
} nodo t ;
i n t main ( i n t a r g c , c h a r ∗∗ a r g v ){
n o d o t ∗ i n i c i o = NULL ;
// I n i c i a l i z a m o s l a l i s t a , con s u p u n t e r o de i n i c i o a p u n t a n d o a NULL
// E q u i v a l e n t e a l i s t a v a c ı́ a [ ]
return 0;
}
6/1
Lista Doblemente Enlazada PRO
Existen otras implementaciones de listas enlazadas simples, donde
se incluyen más punteros y variables de control.
C
#i n c l u d e <s t d i o . h>
t y p e d e f s t r u c t nodo{
i n t d a t o ; // dato , puede s e r l o que u d s . n e c e s i t e n
s t r u c t nodo ∗ s g t e ; // p u n t e r o a un nodo e n a l c e .
} nodo t ;
i n t main ( i n t a r g c , c h a r ∗∗ a r g v ){
n o d o t ∗ i n i c i o = NULL ; // pueden u s a r un s t r u c t p a r a e s t o s d a t o s
n o d o t ∗ f i n a l = NULL ;
int largo = 0;
// E q u i v a l e n t e a l i s t a v a c ı́ a [ ]
// ¿ Para que s i r v e e s t a n u e v a f o r m a ?
// I m p l e m e n t e l a s f u n c i o n e s de é s t a c l a s e c o n s i d e r a n d o e s t a f o r m a .
return 0;
}
7/1
Lista Doblemente Enlazada PRO
8/1
Lista Doblemente Enlazada PRO+
Existen otras implementaciones de listas enlazadas simples, donde
se incluyen más punteros y variables de control.
C
#i n c l u d e <s t d i o . h>
t y p e d e f s t r u c t nodo{
i n t d a t o ; // dato , puede s e r l o que u d s . n e c e s i t e n
s t r u c t nodo ∗ s g t e ; // p u n t e r o a un nodo e n a l c e .
} nodo t ;
i n t main ( i n t a r g c , c h a r ∗∗ a r g v ){
n o d o t ∗ i n i c i o = NULL ; // pueden u s a r un s t r u c t p a r a e s t o s d a t o s
n o d o t ∗ f i n a l = NULL ;
n o d o t ∗ a c t u a l = NULL ;
int largo = 0;
int pos actual = 0;
// E q u i v a l e n t e a l i s t a v a c ı́ a [ ]
// ¿ Para que s i r v e e s t a n u e v a f o r m a ?
// I m p l e m e n t e l a s f u n c i o n e s de é s t a c l a s e c o n s i d e r a n d o e s t a f o r m a .
return 0;
}
9/1
Lista Doblemente Enlazada PRO+
10/1
Pilas o Stacks
La pila o stack es estructura de datos que permite operar solo en uno de
sus extremos. Es de tipo LIFO: Last In, First Out. Puede ser
implementada con arreglos o listas.
Aplicaciones:
Control+Z o Control+Y/Control+Mayus+Z: Operaciones de
Desahcer o Rehacer (undo/redo).
Compilación: Formulas matemáticas en notacion de primer orden,
i.e. (x 1 (+ 2 3)) = x 1 + 2 3
Busqueda en árboles: Por ejemplo Búsqueda en Profundidad
(Deep-first Search o DFS).
11/1
Pilas o Stacks: Interfaz
push(): Ingresa un nuevo elemento en la pila.
pop(): Elimina el elemento superior de la pila.
peak(): Devuelve el valor del primer elemento en la pila.
is empty(): Revisa si la pila está vacı́a.
is full(): Revisa si la pila está llena (solo para tamños fijos).
¿Cómo se implementan?
12/1
Pilas o Stacks
13/1
Pilas o Stacks: push()
14/1
Pilas o Stacks: pop()
15/1
Listas Circulares
La lista circular es una variación de la lista simple/doble enlazada
en la cual, el primer elemento está conectado con el último
elemento, creando ası́ una estructura circular.
16/1
Listas Circulares
Ventajas:
Cualquier nodo puede ser la cabezera o final.
Si una estructura tiene dos punteros, ahora solo es necesario
uno.
Útil para lecturas reiterativas de elementos.
Aplicaciones:
Colas o Queues.
Buffers circulares dinámicos y estáticos.
Planificacion de ejecución de componentes de CPU.
Todo tipo de round robin scheduling.
17/1
Colas o Queues
La cola o queue es una estructura de datos que permite operar en un
extremo para entrada y en otro extremo para salida. Simula el
comportamiento de una fila o cola. Es de tipo FIFO: First In, First
Out. Puede ser implementada con arreglos o listas.
Aplicaciones:
Planificación de recursos. Priorización.
Colas de impresión.
Comunicación asincrónica e interrupciones de sistema.
Teorı́a de Colas.
18/1
Pilas o Stacks: Interfaz
enqueue(): Ingresa un nuevo elemento al final de la cola.
dequeue(): Elimina el primer elemento de la cola.
size(): Devuelve el tamaño de la queue.
check(): Devuelve el valor de un elemento de la cola.
is empty(): Revisa si la queue está vacı́a.
is full(): Revisa si la queue está llena (solo para tamños
fijos).
¿Cómo se implementan?
19/1
Pilas o Stacks
20/1
Pilas o Stacks: enqueue()
21/1
Pilas o Stacks: dequeue()
22/1
Colas o Queues Circulares
Es una fila o cola que se implementa utilizando estructuras de
datos circulares, i.e., listas enlazadas circulares.
Ventaja principal, necesita sólo puntero para ser manejada, en la
posición final. No hay necesidad de recorrer toda la fila para poder
hacer cambios.
23/1
Pilas o Stacks: enqueue()
24/1
Pilas o Stacks: dequeue()
25/1
Desafı́o
Desarrolle un programa que:
Invierta una palabra utilizando pilas.
Inveirta una palabra usando queues.
Invierta una lista utilizando stacks.
Invierta una lista utilizando colas.
26/1