Pilas Colas Listas

Pilas
Colas
Listas

Estructuras de datos: Pilas, Colas, Listas
Algoritmos
´ - Fac. de Informatica
´
Dep. de Computacion
˜
Universidad de A Coruna

J. Santiago Jorge
sjorge@udc.es

Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

´Indice

1

Pilas

2

Colas

3

Listas

Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

´
Referencias bibliograficas

M. A. Weiss. Listas, pilas y colas. EnEstructuras de datos y
´
algoritmos, cap´ıtulo 3, paginas
45–92. Addison-Wesley
Iberoamericana, 1995.
˜ Mar´ı. Implementacion
´ de estructuras de datos. En
R. Pena
˜ de Programas. Formalismo y abstraccion,
´ cap´ıtulo 7,
Diseno
´
´ 1998.
paginas
257–290. Prentice Hall, segunda edicion,
G. Brassard y T. Bratley. Estructura de datos. En Fundamentos
´
de algoritmia, cap´ıtulo 5, paginas
167–210.Prentice Hall, 1997.

Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

´Indice

1

Pilas

2

Colas

3

Listas

Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

Pilas

Acceso limitado al ultimo
elemento insertado
´
´
Operaciones basicas:
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 deimplementacion.
´ deber´ıa tardar una cantidad constante de tiempo
Cada operacion
en ejecutarse.
Con independencia del numero
de elementos apiladas.
´

Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

´
´ a base de vectores (i)
Pseudocodigo:
Implementacion
tipo Pila = registro
Cima_de_pila : 0..Tama˜
no_m´
aximo_de_pila
Vector_de_pila : vector [1..Tama˜
no_m´
aximo_de_pila]
de Tipo_de_elemento
finregistro
procedimiento Crear Pila ( P )
P.Cima_de_pila := 0
fin procedimiento
funci´
on Pila Vac´
ıa ( P ) : test
devolver P.Cima_de_pila = 0
fin funci´
on
Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

´
´ a base de vectores (ii)
Pseudocodigo:
Implementacion
procedimiento Apilar ( x, P )
si P.Cima_de_pila = Tama˜
no_m´
aximo_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´
on 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´
on
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

Pilas
ColasListas

´
Codigo
C: pilas.h
#ifndef TAMANO_MAXIMO_PILA
#define TAMANO_MAXIMO_PILA 10
#endif
typedef int tipo_elemento;
typedef struct {
int cima;
tipo_elemento vector[TAMANO_MAXIMO_PILA];
} pila;
void crear_pila(pila *);
int pila_vacia(pila);
void apilar(tipo_elemento, pila *);
tipo_elemento cima(pila);
void desapilar(pila *);
/* ERRORES: cima o desapilar sobre la pila vac´
ıa
apilar sobre la pilallena */
Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

´
Codigo
C: pilas.c (i)
#include
#include
#include "pilas.h"
void crear_pila(pila *p) {
p->cima = -1;
}
int pila_vacia(pila p) {
return (p.cima == -1);
}
void apilar(tipo_elemento x, pila *p) {
if (++p->cima == TAMANO_MAXIMO_PILA) {
printf("error: pila llena\n"); exit(EXIT_FAILURE);
}
p->vector[p->cima] = x;
}Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

´
Codigo
C: pilas.c (ii)
tipo_elemento cima(pila p) {
if (pila_vacia(p)) {
printf("error: pila vacia\n");
exit(EXIT_FAILURE);
}
return p.vector[p.cima];
}
void desapilar(pila *p) {
if (pila_vacia(*p)) {
printf("error: pila vacia\n");
exit(EXIT_FAILURE);
}
p->cima--;
}
Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

´Indice

1

Pilas

2Colas

3

Listas

Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

Colas

´
Operaciones basicas:
insertar, quitarPrimero y primero.
Cada rutina deber´ıa ejecutarse en tiempo constante.

Algoritmos

Pilas, Colas, Listas

Pilas
Colas
Listas

´ circular a base de vectores (i)
Implementacion
´ circular devuelve cabeza y fin al principo del
La implementacion
´
vector cuando rebasan la ultima...

Leer documento completo

Regístrate para leer el documento completo.