PDF de programación - Estructuras de datos: Pilas, Colas, Listas

Pilas
Colas
Listas

Estructuras de datos: Pilas, Colas, Listas

Algoritmos

Facultad de Informática
Universidad de A Coruña

Algoritmos

Pilas, Colas, Listas

Table of Contents

Pilas
Colas
Listas

1 Pilas

2 Colas

3 Listas

Algoritmos

Pilas, Colas, Listas

Table of Contents

Pilas
Colas
Listas

1 Pilas

2 Colas

3 Listas

Algoritmos

Pilas, Colas, Listas

Pilas

Pilas
Colas
Listas

Acceso limitado al último elemento insertado
Operaciones básicas: apilar, desapilar y cima.

desapilar o cima en una pila vacía es un error en el TDA pila.
Quedarse sin espacio al apilar es un error de implementación.

Cada operación debería tardar una cantidad constante de tiempo
en ejecutarse.

Con independencia del número de elementos apiladas.

Algoritmos

Pilas, Colas, Listas

Pseudocódigo: Implementación a base de vectores (i)

Pilas
Colas
Listas

tipo Pila = registro
Cima_de_pila : 0..Tamaño_máximo_de_pila
Vector_de_pila : vector [1..Tamaño_máximo_de_pila]

de Tipo_de_elemento

fin registro

procedimiento Crear Pila ( P )
P.Cima_de_pila := 0
fin procedimiento

función Pila Vacía ( P ) : test

devolver P.Cima_de_pila = 0

fin función

Algoritmos

Pilas, Colas, Listas

Pseudocódigo: Implementación a base de vectores (ii)

Pilas
Colas
Listas

procedimiento Apilar ( x, P )

si P.Cima_de_pila = Tamaño_máximo_de_pila entonces

error Pila llena

sino

P.Cima_de_pila := P.Cima_de_pila + 1;
P.Vector_de_pila[P.Cima_de_pila] := x

fin procedimiento
función Cima ( P ) : Tipo_de_elemento

si Pila Vacía (P) entonces error Pila vacía
sino devolver P.Vector_de_pila[P.Cima de Pila]

fin función
procedimiento Desapilar ( P )

si Pila Vacía (P) entonces error Pila vacía
sino P.Cima_de_pila := P.Cima_de_pila - 1

fin procedimiento

Algoritmos

Pilas, Colas, Listas

Table of Contents

Pilas
Colas
Listas

1 Pilas

2 Colas

3 Listas

Algoritmos

Pilas, Colas, Listas

Colas

Pilas
Colas
Listas

Operaciones básicas: insertar, quitarPrimero y primero.
Cada rutina debería ejecutarse en tiempo constante.

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

La implementación circular devuelve cabeza y fin al principo del
vector cuando rebasan la última posición.

final

1) Crear Cola (C)

cabeza

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

La implementación circular devuelve cabeza y fin al principo del
vector cuando rebasan la última posición.

final

1) Crear Cola (C)

2) Insertar en Cola (a,C)

cabeza

final
a
cabeza

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

La implementación circular devuelve cabeza y fin al principo del
vector cuando rebasan la última posición.

final

1) Crear Cola (C)

2) Insertar en Cola (a,C)

3) Insertar en Cola (b,C)

cabeza

final
a
cabeza

a
cabeza

final
b

Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

Implementación circular a base de vectores (i)

4) Insertar en Cola (c,C)

a
cabeza

b

final
c

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

4) Insertar en Cola (c,C)

5) Insertar en Cola (d,C)

a
cabeza

a
cabeza

b

b

final
c

c

final
d

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

4) Insertar en Cola (c,C)

5) Insertar en Cola (d,C)

a
cabeza

a
cabeza

b

b

6) Quitar Primero (C)

b
cabeza

final
c

c

c

final
d

final
d

Algoritmos

Pilas, Colas, Listas

Implementación circular a base de vectores (i)

Pilas
Colas
Listas

4) Insertar en Cola (c,C)

5) Insertar en Cola (d,C)

a
cabeza

a
cabeza

b

b

6) Quitar Primero (C)

7) Insertar en Cola (e,C)

final
e

b
cabeza

b
cabeza

Algoritmos

Pilas, Colas, Listas

final
c

c

c

c

final
d

final
d

d

Pilas
Colas
Listas

Pseudocódigo (i)

tipo Cola = registro

Cabeza_de_cola, Final_de_cola: 1..Tamaño_máximo_de_cola
Tamaño_de_cola : 0..Tamaño_máximo_de_cola
Vector_de_cola : vector [1..Tamaño_máximo_de_cola]

de Tipo_de_elemento

fin registro
procedimiento Crear_Cola ( C )

C.Tamaño_de_cola := 0;
C.Cabeza_de_cola := 1;
C.Final_de_cola := Tamaño_máximo_de_cola

fin procedimiento
función Cola_Vacía ( C ) : test
devolver C.Tamaño_de_cola = 0

fin función

Algoritmos

Pilas, Colas, Listas

Pseudocódigo (ii)

Pilas
Colas
Listas

procedimiento incrementar ( x ) (* privado *)
si x = Tamaño_máximo_de_cola entonces x := 1
sino x := x + 1

fin procedimiento

procedimiento Insertar_en_Cola ( x, C )

si C.Tamaño_de_Cola = Tamaño_máximo_de_cola entonces

error Cola llena

sino

C.Tamaño_de_cola := C.Tamaño_de_cola + 1;
incrementar(C.Final_de_cola);
C.Vector_de_cola[C.Final_de_cola] := x;

fin procedimiento

Algoritmos

Pilas, Colas, Listas

Pseudocódigo (iii)

Pilas
Colas
Listas

función Quitar_Primero ( C ) : Tipo_de_elemento

si Cola_Vacía ( C ) entonces

error Cola vacía

sino

C.Tamaño_de_cola := C.Tamaño_de_cola - 1;
x := C.Vector_de_cola[C.Cabeza_de_cola];
incrementar(C.Cabeza_de_cola);
devolver x

fin función
función Primero ( C ) : Tipo_de_elemento

si Cola_Vacía ( C ) entonces

error Cola vacía

sino

devolver Vector_de_cola[C.Cabeza_de_cola]

fin función

Algoritmos

Pilas, Colas, Listas

Table of Contents

Pilas
Colas
Listas

1 Pilas

2 Colas

3 Listas

Algoritmos

Pilas, Colas, Listas

Listas

Pilas
Colas
Listas

Operaciones básicas:

Visualizar su contenido.
Buscar la posición de la primera ocurrencia de un elemento.
Insertar y Eliminar un elemento en alguna posición.
Buscar k esimo, que devuelve el elemento
de la posición indicada

Algoritmos

Pilas, Colas, Listas

Implementación de listas a base de vectores

Pilas
Colas
Listas

Tiene que declararse el tamaño de la lista.

Exige sobrevaloración.
Consume mucho espacio.

Complejidad computacional de las operaciones:

Buscar k esimo, tiempo constante
Visualizar y Buscar, tiempo lineal.
Insertar y Eliminar son costosas.

Insertar o eliminar un elemento exige, en promedio,
desplazar la mitad de los valores, O(n).
La construcción de una lista o la eliminación
de todos sus elementos podría exigir un tiempo cuadrático.

Algoritmos

Pilas, Colas, Listas

Implementación de listas a base de apuntadores

Pilas
Colas
Listas

Cada nodo apunta al siguiente; el último no apunta a nada.
La lista es un puntero al primer nodo (y al último).
Complejidad computacional de las operaciones:

Visualizar y Buscar, tiempo lineal.
Buscar k esimo, tiempo lineal.
Eliminar realiza un cambio de apuntadores y
una orden dispose, O(1).

Usa Buscar anterior cuyo tiempo de ejecución es lineal.
Insertar tras una posición p require una llamada a new y
dos maniobras con apuntadores, O(1).

Buscar la posición p podría llevar tiempo lineal.

Un nodo cabecera facilita la inserción y la eliminación al comienzo
de la lista.

Algoritmos

Pilas, Colas, Listas

Implementación de listas doblemente enlazadas

Pilas
Colas
Listas

Cada nodo apunta al siguiente y al anterior.
Duplica el uso de la memoria necesaria para los punteros.
Duplica el coste de manejo de punteros al insertar y eliminar.
La eliminación se simplifica.

No es necesario buscar el elemento anterior.

Algoritmos

Pilas, Colas, Listas

Pseudocódigo: Implementación con un nodo cabecera (i)

Pilas
Colas
Listas

tipo PNodo = puntero a Nodo

Lista = PNodo
Posición = PNodo
Nodo = registro

Elemento : Tipo_de_elemento
Siguiente : PNodo

fin registro

procedimiento Crear Lista ( L )

nuevo ( tmp );
si tmp = nil entonces error Memoria agotada
sino

tmpˆ.Elemento := { nodo cabecera };
tmpˆ.Siguiente := nil;
L := tmp

fin procedimiento

Algoritmos

Pilas, Colas, Listas

Pseudocódigo: Implementación con un nodo cabecera (ii)

Pilas
Colas
Listas

función Lista Vacía ( L ) : test

devolver Lˆ.Siguiente = nil

fin función

función Buscar ( x, L ) : posición de la 1a ocurrencia

o nil

p := Lˆ.Siguiente;
mientras p <> nil y pˆ.Elemento <> x hacer

p := pˆ.Siguiente;

devolver p
fin función
función Último Elemento ( p ) : test { privada }

devolver pˆ.Siguiente = nil

fin función

Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

Pseudocódigo: Implementación con un nodo cabecera (iii)

función Buscar Anterior ( x, L ) : posición anterior a x

o a nil { privada }

p := L;
mientras pˆ.Siguiente <> nil y

pˆ.Siguienteˆ.Elemento <> x hacer

p := pˆ.Siguiente;

devolver p
fin función
procedimiento Eliminar ( x, L )

p := Buscar Anterior ( x, L );
si Último Elemento ( p ) entonces error No encontrado
sino tmp := pˆ.Siguiente;

pˆ.Siguiente := tmpˆ.Siguiente;
liberar ( tmp )

fin procedimiento

Algoritmos

Pilas, Colas, Listas

Pseudocódigo: Implementación con un nodo cabecera (iv)

Pilas
Colas
Listas

procedimiento Insertar ( x, L, p )

{ Inserta después de la posición p }

nuevo ( tmp );
si tmp = nil entonces
error Memoria agotada

sino

tmpˆ.Elemento := x;
tmpˆ.Siguiente := pˆ.Siguiente:
pˆ.Siguiente := tmp

fin procedimiento

Algoritmos

Pilas, Colas, Listas