Recordando: Lista Simple Enlazada

Pilas o Stacks

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 2024

1/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

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/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

Lista Simple Enlazada: Inicializar

3/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

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/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

Lista Enlazada PRO

5/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

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/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

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/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

Lista Doblemente Enlazada PRO

8/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

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/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

Lista Doblemente Enlazada PRO+

10/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

Pilas o Stacks
TDA 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/Control+Y: 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: Búsqueda en Profundidad (DFS).
11/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

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/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

Pilas o Stacks

13/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

Pilas o Stacks: push()

14/26
 Recordando: Lista Simple Enlazada
Pilas o Stacks

Pilas o Stacks: pop()

15/26
 Listas Circulares
Colas o Queues.

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/26
 Listas Circulares
Colas o Queues.

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/26
 Listas Circulares
Colas o Queues.

Colas o Queues
TDA 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/26
 Listas Circulares
Colas o Queues.

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/26
 Listas Circulares
Colas o Queues.

Colas o Queues

20/26
 Listas Circulares
Colas o Queues.

Colas o Queues: enqueue()

21/26
 Listas Circulares
Colas o Queues.

Colas o Queues: dequeue()

22/26
 Listas Circulares
Colas o Queues.

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/26
 Listas Circulares
Colas o Queues.

Colas o Queues: enqueue()

24/26
 Listas Circulares
Colas o Queues.

Colas o Queues: dequeue()

25/26
 Listas Circulares
Colas o Queues.

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/26