PDF de programación - Tema 2. Pilas

Programación II
Tema 2. Pilas

Iván Cantador y Rosa Mª Carro
Escuela Politécnica Superior
Universidad Autónoma de Madrid

Contenidos

1

• El TAD Pila
• Estructura de datos y primitivas de Pila
• Implementación en C de Pila

• Implementación con top de tipo entero

• Ejemplos de aplicación de Pila

• Balanceo de paréntesis
• Evaluación de expresiones posfijo
• Conversión entre notaciones infijo, posfijo y prefijo

• Anexo

• Implementación con top de tipo puntero

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Contenidos

2

• El TAD Pila
• Estructura de datos y primitivas de Pila
• Implementación en C de Pila

• Implementación con top de tipo entero

• Ejemplos de aplicación de Pila

• Balanceo de paréntesis
• Evaluación de expresiones posfijo
• Conversión entre notaciones infijo, posfijo y prefijo

• Anexo

• Implementación con top de tipo puntero

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

El TAD Pila
• Pila (stack en inglés)

3

• Colección de elementos LIFO ‐ Last In, First Out: “el último que 

entra, el primero que sale”

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

El TAD Pila
• Definición de Pila

4

• Contenedor de elementos que son insertados y extraídos 

siguiendo el principio de que el último que fue insertado será el 
primero en ser extraído (LIFO – Last In, First Out)
‐ Los elementos se insertan de uno en uno: push (apilar)
‐ Los elementos se extraen de uno en uno: pop (desapilar)
‐ El último elemento insertado (que será el primero en ser extraído) es el 

único que se puede “observar” de la pila: top (tope, cima)

tiempo

push 1

push 2

push 3

pop 3

push 4

push 5

pop 5

pop 4

pop 2

pop 1

2
1

1

3
2
1

2
1

4
2
1

5
4
2
1

4
2
1

2
1

1

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

El TAD Pila
• Aplicaciones reales de las pilas

5

• En general, todas aquellas aplicaciones que conlleven:

‐ estrategias “vuelta atrás” (back tracking): la acción deshacer/undo
‐ algoritmos recursivos

• Ejemplos:

‐ Editores de texto: pila con los últimos cambios realizados sobre un documento
‐ Navegadores web: pila de direcciones con los sitios web más recientemente 

visitados

‐ Pila de programa: zona de memoria de un programa donde se guardan 

temporalmente los argumentos de entrada de funciones
‐ Comprobación del balanceo de (), {}, [] en compiladores
‐ Parsing de código XML/HTML, comprobando la existencia de etiquetas de 
comienzo <tag> y finalización </tag> de elementos en un documento XML

‐ Calculadoras con notación polaca inversa (posfijo): se convierten expresiones 

“infijo” a “posfijo” soportando complejidad superior a la de calculadoras 
algebraicas (p.e., realizan cálculos parciales sin tener que pulsar “=”)

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Contenidos

6

• El TAD Pila
• Estructura de datos y primitivas de Pila
• Implementación en C de Pila

• Implementación con top de tipo entero

• Ejemplos de aplicación de Pila

• Balanceo de paréntesis
• Evaluación de expresiones posfijo
• Conversión entre notaciones infijo, posfijo y prefijo

• Anexo

• Implementación con top de tipo puntero

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Estructura de datos y primitivas de Pila
• Una pila está formada por:

7

• datos: conjunto de elementos, en general del mismo tipo, ordenados 

implícitamente y accesibles desde un único punto: el tope

• tope: indicador de la posición del último elemento insertado; da lugar 

a una ordenación LIFO (last in, first out)

7

6

5

4

3

2

1

0

x
x
x
x
x

datos

4
tope

(en este dibujo asumimos que la pila
tiene tamaño máximo de 8, pero no
tiene por qué ser siempre ese valor)

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Estructura de datos y primitivas de Pila

8

• Primitivas

Pila pila_crear(): crea, inicializa y devuelve una pila
pila_liberar(Pila s): libera (la memoria ocupada por) la pila
boolean pila_vacia(Pila s): devuelve true si la pila está vacía y false si no
boolean pila_llena(Pila s): devuelve true si la pila está llena y false si no
status pila_push(Pila s, Elemento e): inserta un dato en una pila
Elemento pila_pop(Pila s): extrae el dato que ocupa el top de la pila
Elemento pila_getTop(Pila s): devuelve el dato que ocupa el top de la pila 

sin extraerlo de ella

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Estructura de datos y primitivas de Pila
• EdD en C

• datos: en este tema será un array de punteros: Elemento *datos[];
• top: en este tema se declarará de 2 maneras (versiones) distintas

• V1: Como un entero: int top;
• V2: Como un puntero a un elemento del array: Elemento **top;

9

7

6

5

4

3

2

1

0

x

x

x

x

x

7

6

5

4

3

2

1

0

x

x

x

x

x

datos

Versión 1

datos

top
Versión 2 (en anexo)

4
top

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Contenidos

10

• El TAD Pila
• Estructura de datos y primitivas de Pila
• Implementación en C de Pila

• Implementación con top de tipo entero

• Ejemplos de aplicación de Pila

• Balanceo de paréntesis
• Evaluación de expresiones posfijo
• Conversión entre notaciones infijo, posfijo y prefijo

• Anexo

• Implementación con top de tipo puntero

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Implementación en C de Pila

11

• Implementación con top de tipo entero

• Asumimos la existencia del TAD Elemento
• EdD de Pila mediante un array

// En pila.h
typedef struct _Pila Pila;
// En pila.c
#define PILA_MAX 8
struct _Pila {

Elemento *datos[PILA_MAX];
int

top;

};

7

6

5

4

3

2

1

0

4
top

datos

x

x

x

x

x

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Implementación en C de Pila
• Implementación con top de tipo entero

• Asumimos la existencia del TAD Elemento que, entre otras, 

tiene asociadas las primitivas liberar y copiar:
void elemento_liberar(Elemento *pe);
Elemento *elemento_copiar(const Elemento *pe);

• Primitivas (prototipos en pila.h)

Pila *pila_crear();
void pila_liberar(Pila *ps);
boolean pila_vacia(const Pila *ps);
boolean pila_llena(const Pila *ps);
status pila_push(Pila *ps, const Elemento *pe);
Elemento *pila_pop(Pila *ps);

• Estructura de datos (en pila.c)

struct _Pila {

Elemento *datos[PILA_MAX];
int

top;

};

7

6

5

4

3

2

1

0

4
top

datos

12

x

x

x

x

x

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Implementación en C de Pila
• Implementación con top de tipo entero

• Asumimos la existencia del TAD Elemento que, entre otras, 

tiene asociadas las primitivas liberar y copiar:
void elemento_liberar(Elemento *pe);
Elemento *elemento_copiar(const Elemento *pe);

• Primitivas (prototipos en pila.h)

Pila *pila_crear();
void pila_liberar(Pila *ps);
boolean pila_vacia(const Pila *ps);
boolean pila_llena(const Pila *ps);
status pila_push(Pila *ps, const Elemento *pe);
Elemento *pila_pop(Pila *ps);

• Estructura de datos (en pila.c)

struct _Pila {

Elemento *datos[PILA_MAX];
int

top;

};

7

6

5

4

3

2

1

0

4
top

datos

13

x

x

x

x

x

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Implementación en C de Pila
• Implementación con top de tipo entero

14

Pila *pila_crear() {
Pila *ps = NULL;
int i;
ps = (Pila *) malloc(sizeof(Pila));
if (ps == NULL) {

return NULL;

}

for (i=0; i<PILA_MAX; i++) { // Bucle opcional

ps->datos[i] = NULL;

}
ps->top = -1;
return ps;

}

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

vacía

7

6

5

4

3

2

1

0

ps

‐1
top

datos

Implementación en C de Pila
• Implementación con top de tipo entero
Existe: void elemento_liberar(Elemento *pe);
void pila_liberar(Pila *ps) {

int i;

if (ps != NULL) {

for (i=0; i<=ps->top; i++) {

elemento_liberar(ps->datos[i]);
ps->datos[i] = NULL;

}
free(ps);
// ps = NULL; se hace fuera, tras llamar
// a pila_liberar

}

}

4
top

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

15

7

6

5

4

3

2

1

0

ps

datos

x

x

x

x

x

Implementación en C de Pila
• Implementación con top de tipo entero
Existe: void elemento_liberar(Elemento *pe);
void pila_liberar(Pila *ps) {

int i;

if (ps != NULL) {

for (i=0; i<=ps->top; i++) {

elemento_liberar(ps->datos[i]);
ps->datos[i] = NULL; // Opcional

}
free(ps);
// ps = NULL; se hace fuera, tras llamar
// a pila_liberar

}

}

16

7

6

5

4

3

2

1

0

ps

datos

x

x

x

x

x

4
top

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Implementación en C de Pila
• Implementación con top de tipo entero
Existe: void elemento_liberar(Elemento *pe);
void pila_liberar(Pila *ps) {

int i;

if (ps != NULL) {

for (i=0; i<=ps->top; i++) {

elemento_liberar(ps->datos[i]);
ps->datos[i] = NULL; // Opcional

}
free(ps);
// ps = NULL; se hace fuera, tras llamar
// a pila_liberar

}

}

4
top

Programación II – Tema 2: Pilas

Escuela Politécnica Superior

Universidad Autónoma de Madrid

17

7

6

5

4

3

2

1

0

ps

datos

Implementación en C de Pila
• Implementación con top de tipo entero

• Asumimos la existencia del TAD Elemento que, entre otras, 

tiene asociadas las primitivas liberar y copiar:
void elemento_liberar(Elemento *pe);
Elemento *elemento_copiar(const Elemento *pe);

• Primitivas (prototipos en pila.h)

Pila *pila_crear();
void pila_liberar(Pila *ps);
boolean pila_vacia(const Pila *ps);
boolean pila_llena(const Pila *ps);
status pila_push(Pila *ps, const Elemento *pe);
Elemento *pila_pop(Pila *ps);

• Estructura de datos (en