Pilas
1
Definición de Pila
Una pila (stack) es una colecciona ordenada
de elementos en la cual los datos se insertan o
se retiran por el mismo extremo llamado
“parte superior” de la pila.
2
Pila (Estructura
de datos)
Su nombre se deriva de la metáfora de una pila de platos
en una cocina.
La inserción y extracción de elementos de la pila siguen
el principio LIFO (Last In, First Out).
El último elemento en entrar es el único accesible en
cada momento.
3
Operaciones
básicas en Pilas
(Push)
Existe solamente un lugar en donde
cualquier elemento puede ser agregado
a la pila. Después de haber insertado el
nuevo elemento, G ahora es el
elemento en la cima.
4
Operaciones
básicas en Pilas
(Pop)
Basta indicar que sea retirado
un elemento. No podemos decir
“retirar C”, porque C no está en
la cima de la pila.
5
La dinámica de la pila, es decir, la
manera en cómo entran y salen los
datos a la estructura de datos se
Ejemplo denomina LIFO (Last In, First Out) o
UEPS (Último en Entrar, Primero en
Salir).
6
Utilidad de las pilas
El concepto de pila es muy importante en computación y en especial
en teoría de lenguajes de programación. En lenguajes procedimentales
como Pascal o C, la pila es una estructura indispensable, debido a las
llamadas a función. ¿Por qué?
Cuando ocurre una llamada a alguna función, el estado global del
sistema se almacena en un registro y éste en una pila. Cuando se
termina de ejecutar algún procedimiento, se recupera el registro que
está en la cima de la pila.
¿Otras aplicaciones de las Pilas?
7
Aplicaciones de las Pilas
Navegador Web Editores de texto
• Se almacenan los sitios • Los cambios efectuados se
previamente visitados. almacenan en una pila.
• Cuando el usuario quiere • Usualmente implementada
regresar (presiona el botón de como arreglo.
retroceso), simplemente se • Usuario puede deshacer los
extrae la última dirección (pop) cambios mediante la operación
de la pila de sitios visitados. “undo”, la cual extraer el estado
del texto antes del último
cambio realizado.
8
Es útil poder detectar si es que los paréntesis en un
archivo fuente están o no balanceados.
Se puede usar un stack: a+(b+c)*[(d+e])/f
Balance Pseudo-código:
Crear el stack.
de Mientras no se ha llegado al final del archivo de
entrada:
o Descartar símbolos que no necesiten ser
paréntesi balanceados.
o Si es un paréntesis de apertura: poner en el stack.
o Si es un paréntesis de cierre, efectuar un pop y
s comparar.
o Si son de igual tipo continuar
o Si son de diferente tipo: avisar el error.
o Si se llega al fin de archivo, y el stack no esta
vacío: avisar error.
9
Operaciones en Pilas
Las operaciones básicas de una pila son:
1. En la pila S, insertar un elemento e: push(S, e)
2. Retirar un elemento de la pila S: pop(S)
3. Verificar si la pila S está vacía: stackempty(S)
4. Saber cuál es el elemento en la cima de la pila S: stacktop(S)
11
La operación
Push
Esta operación sirve para insertar un elemento e en la pila
S, lo vamos a escribir como: push(S, e).
Después de hacer esta operación sucede que: El elemento
en la cima de la pila S ahora es e.
12
La operación
Push (2)
(1) La operación push recibe: la dirección de una
estructura pila y un elemento entero.
(2) Incrementa el tope (cima) de la pila para agregar el
elemento en una posición libre de la pila.
(3) Asignando el valor e en la casilla S->top.
13
La operación Pop
Esta operación sirve para retirar el elemento en la cima
de la pila S, lo vamos a escribir como: pop(S, e).
14
La operación Pop
(2)
(1) La función devuelve un tipo entero al recibir la
dirección de una variable de tipo estructura pila (struct
stack *).
Las líneas (4) y (5) son las mas importantes ya que se
almacena el valor que ser devuelto y se decrementa el
tope de la pila.
15
La operación
Stacktop
Esta función debe devolver un
número entero y dejar la pila
sin cambio. Para esto:
pop(&A)
Mostrar el elemento A
push(&A,elemento).
16
La operación
Stackempty
La operación stackempty se describe en el siguiente
segmento de código:
17
Ejemplo 1-Pilas
Crear un programa en C/C++ donde se implemente una pila junto con sus operaciones básicas
(push, pop, stacktop y stackempty).
18
Entregar un programa donde se utilice una
pila donde ahora se capture un dato de tipo
caracter (char).
Es prácticamente el mismo programa que el de
la actividad 303, sólo cambiará lo siguiente:
Actividad 304 El programa le pedirá al usuario que capture
un caracter, después le preguntará si quiere
capturar otro caracter.
En caso afirmativo, el programa volverá a
pedirle otro caracter. En caso negativo, se
procederá a sacar todos los datos de la pila y
mostrarlos en pantalla.
19
Análisis básico de
expresiones
Considérese la siguiente expresión matemática:
Cuya representación “lineal” es:
7 – ((x * ((x + y) / (j - 3)) + y) / (4 – 5/2))
¿Cómo saber si la expresión está correctamente
balanceada en cuanto a paréntesis se refiere?
20
Realizar una programa que utilice una pila
para evaluar una expresión algebraica o
matemática con paréntesis introducida por
ACTIVIDAD teclado por el usuario y nos diga si está
correcta (válida) o no.
305
¡NOSE ACEPTAN CAPTURAS DE
PANTALLA DEL CÓDIGO FUENTE!
21
Pseudocódigo para realizar la
comprobación
valido = true;
s = la pila vacía;
Mientras (no sea el fin de la cadena){
simbolo = texto[n];
Si( simbolo == ‘(’ )
push(s, simbolo);
DeLoContrario SI(simbolo == ‘)’ ) {
Si( estaVacia(s) )
valido = false;
22
Pseudocódigo para realizar la
comprobación(2)
DeLoContrario {
i = pop(s);
popPila(pila, simbolo);
}
}
n++;
} /* Mientras */
Si( NoEstaVacia(s) )
valido = false;
Si(valido)
Visualizar “La cadena es válida\n”;
DeloContrario
Visualizar “La cadena es inválida\n”;
23
Colas
24
La estructura de datos Cola
En una cola hay dos extremos, uno es llamado la parte
delantera y el otro extremo se llama la parte trasera de la cola.
En una cola, los elementos se retiran por la parte delantera y
se agregan por la parte trasera.
25
La estructura de datos
Cola
Su nombre se deriva de la metáfora de una cola de personas en una
taquilla.
La inserción y extracción de elementos de la cola siguen el principio
FIFO (first-in-first-out).
El elemento con más tiempo en la cola es el que puede ser extraído.
26
Operaciones en una cola
Las operaciones básicas de una cola son “enqueue” (meter) y “dequeue” (sacar)
enqueue: añade un nuevo elemento al final de la cola.
dequeue: elimina (saca) el primer elemento de la cola.
Otras operaciones usualmente incluidas en el tipo abstracto COLA son:
isEmpty (estáVacia): verifica si la cola está vacía.
isFull (estáLlena): verifica si la cola está llena.
27
Ejemplo de operaciones en una
cola
28
Aplicaciones de las colas
En general, operaciones en redes de computadoras.
• –Trabajos enviados a una impresora.
• –Solicitudes a un servidor.
Clientes solicitando ser atendidos por una telefonista.
29
Ejemplo-Cola
Crear un programa en C/C++ donde se implemente una cola junto con sus operaciones básicas
(encolar, desencolar y colavacía).
30
Crear un programa en C/C++ donde se
implemente una cola que guarde el nombre y
la edad de los clientes en un banco.
Genera una función que cuente cuántos
Actividad 306- elementos en la cola tienen la edad de 50 años
Ejercicio de o más y devuelva el resultado.
colas El programa deberá mencionar cuantos
clientes cumplen con el criterio de edad y
visualizar todos los elementos de cola.
31
Mediante programación en C++, desarrolla un
programa que permita:
Encolar: agrega un elemento a la cola.
VerCola: recorre toda la cola y visualiza su
contenido, sin sacarlos.
VaciarCola: saca todos los elementos de la
Actividad 307 cola.
Buscar: localiza un elemento que pudiera
estar en la cola.
Desencola: saca un elemento de la cola.
El elemento al que se hace referencia puede
ser de tipo entero o char.
32
