Pilas Colas Listas

Pilas Colas Listas

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

J. Santiago Jorge sjorge@udc.es

Algoritmos

Pilas, Colas, Listas

Pilas Colas Listas

´ndice I

1

Pilas

2

Colas

3

Listas

Algoritmos

Pilas, Colas, Listas

Pilas Colas Listas

´ Referencias bibliograficas

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

Algoritmos

Pilas, Colas, Listas

Pilas Colas Listas

´ndice I

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 TDApila. ı ´ Quedarse sin espacio al apilar es un error de implementacion. ´ Cada operacion deber´a tardar una cantidad constante de tiempo ı en ejecutarse.
Con independencia del numero de elementos apiladas. ´

Algoritmos

Pilas, Colas, Listas

Pilas Colas Listas

´ ´ Pseudocodigo: Implementacion a base de vectores (i)
tipo Pila = registro Cima_de_pila : 0..Tama˜o_m´ximo_de_pila n aVector_de_pila : vector [1..Tama˜o_m´ximo_de_pila] n a de Tipo_de_elemento fin registro procedimiento Crear Pila ( P ) P.Cima_de_pila := 0 fin procedimiento funci´n Pila Vac´a ( P ) : test o ı devolver P.Cima_de_pila = 0 fin funci´n o
Algoritmos Pilas, Colas, Listas

Pilas Colas Listas

´ ´ Pseudocodigo: Implementacion a base de vectores (ii)
procedimiento Apilar ( x, P ) si P.Cima_de_pila =Tama˜o_m´ximo_de_pila entonces n a 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 o si Pila Vac´a (P) entonces error Pila vac´a ı ı sino devolver P.Vector_de_pila[P.Cima de Pila] fin funci´n o 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 Colas Listas

´ 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); voiddesapilar(pila *); /* ERRORES: cima o desapilar sobre la pila vac´a ı apilar sobre la pila llena */
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

´ndice I

1

Pilas

2

Colas

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

´ Implementacion circular a base de...