Guía 08 - TAD Pila

UNIVERSIDAD ANDINA DEL CUSCO
FACULTAD DE INGENIERÍA Y ARQUITECTURA

ESCUELA PROFESIONAL DE INGENIERÍA DE SISTEMAS
ESTRUCTURA DE DATOS
Guía de estudio Nº 08: TAD Pila.
Fecha: octubre 2022

Semestre: 2022-II
I. COMPETENCIAS A LOGRAR
Durante el desarrollo de la guía el estudiante:
● Conocerá y aplicará los conceptos de la estructura de datos Pila.
● Realizará correctamente los algoritmos propuestos de implementación de una Pila.
● Aplicará los algoritmos desarrollados en casos reales.
● Entenderá las ventajas de la implementación de la estructura de datos Pila.
II. DESARROLLO
La pila (o stack) es una estructura de datos lineal y dinámica, en la cual el elemento
obtenido a través de la operación ELIMINAR está predefinido, debido a que implementa la
política Last-In, First-Out (LIFO), esto es, el último elemento que se agregó es el primer
que se elimina.
Las operaciones que se pueden realizar sobre una pila son INSERTAR (que es llamada
PUSH) y ELIMINAR (que es llamada POP). Debido a la política LIFO que implementa esta
estructura, el orden en el que los elementos son extraídos de la pila (POP) es inverso al
orden en el que los elementos fueron insertados en la pila (PUSH). Además, el único
elemento accesible de la pila es el que está hasta arriba y que se conoce como tope de la
pila.
Para poder diseñar un algoritmo que defina el comportamiento de una pila se deben
considerar 3 casos para ambas operaciones (push y pop):
• Estructura vacía (caso extremo).
• Estructura llena (caso extremo).
• Estructura con elemento(s) (caso base).
Una pila vacía no contiene elemento alguno dentro de la estructura y el tope de la misma
apunta a nulo (Figura 1).
Figura 1
ESTRUCTURA DE DATOS
En una pila vacía no es posible realizar POP, debido a que la estructura no contiene
información.
Cuando la pila está vacía sí se puede realizar PUSH, en tal caso, el nodo que entra a la
estructura sería el único elemento de la pila y el tope apuntaría a él (Figura 2).
Figura 2
Por definición, una estructura de datos tipo pila tiene un tamaño fijo. Cuando la pila ha
almacenado el número máximo de nodos definido, se dice que la pila está llena (Figura 3).
Figura 3
En una pila llena no es posible hacer PUSH de un nuevo elemento, ya que se ha alcanzado
el tamaño máximo permitido.
Cuando la pila está llena se puede hacer POP de la información contenida en la estructura.
En tal caso, el tope apunta al elemento siguiente de la estructura (Figura 4).
ESTRUCTURA DE DATOS
Figura 4
Una pila que contiene elementos (sin llegar a su máxima capacidad) representa el caso
general.
En una pila con elementos se pueden realizar PUSH. En tal caso, el tope apuntara al
elemento que se insertó y el nuevo elemento apunta al elemento al que apuntaba tope
(Figura 5).
Figura 5
En una pila con elementos es posible realizar POP. En tal caso, el nodo al que apunta tope
se extrae y ahora tope apunta al elemento al que apuntaba éste (sucesor) (Figura 4).
Las funciones asociadas con la pila utilizando arreglos son:

• vacío() – Devuelve si la pila está vacía – Complejidad de tiempo: O(1)
• size() – Devuelve el tamaño de la pila – Complejidad de tiempo: O(1)
• top() – Devuelve una referencia al elemento superior de la pila – Complejidad de
tiempo: O(1)
ESTRUCTURA DE DATOS
• push(a) – Inserta el elemento 'a' en la parte superior de la pila – Complejidad de

tiempo: O(1)
• pop() - Elimina el elemento superior de la pila - Complejidad de tiempo: O(1)
Las funciones asociadas con la pila utilizando listas enlazadas son:

• getSize(): obtiene la cantidad de elementos en la pila.
• isEmpty(): devuelve True si la pila está vacía, False en caso contrario.
• peek(): devuelve el elemento superior de la pila. Si la pila está vacía, genera una
excepción.
• push(value): Inserta un valor en la cabeza de la pila.
• pop(): elimina y devuelve un valor en la cabeza de la pila. Si la pila está vacía, genera
una excepción.
Aplicaciones
La estructura pila tienen varias aplicaciones dentro de la ingeniería, de las más conocidas
es la que se utiliza dentro de la memoria RAM de un equipo de cómputo.
La memoria de las computadoras no es un espacio uniforme, el código que se ejecuta
utiliza tres diferentes segmentos de memoria: el texto (text), la pila (stack) y el montículo
(heap)
Cuando una aplicación inicia, el método principal es invocado y se reserva memoria en la
pila o stack. En el segmento de memoria de la pila es donde se alojan las variables
requeridas por las funciones del programa. Así mismo, cada vez que se llama una función
dentro del programa una sección de la pila, llamada marco o frame, se reserva y es ahí
donde las variables de la nueva función son almacenadas.
Figura 6. Regiones de la memoria RAM
Cuando una función manda llamar varias funciones, éstas generan un nuevo marco que
se va creando uno encima del otro y, cuando las funciones terminan, los marcos se liberan
de manera automática en orden inverso (LIFO).
Otra aplicación es la gestión de ventanas en Windows (cuando cerramos una ventana

siempre recuperamos la que teníamos detrás). Otro ejemplo es la evaluación general de
cualquier expresión matemática para evitar tener que calcular el número de variables
temporales que hacen falta.
ESTRUCTURA DE DATOS
III. DESARROLLO EN LABORATORIO:

1. Implementación de una Pila usando Arreglos:
stack = []
# append() función para insertar el elemento en la pila (push)

stack.append('a')
stack.append('b')
stack.append('c')
print('Pila')
print(stack)
#Función para eliminar un elemento de la pila en el orden LIFO (pop)

print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nPila después de eliminar los elementos:')

print(stack)
2. Implementación de una Pila utilizando listas enlazadas:

class Node:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
# Inicializando una Pila.
def __init__(self):
self.head = Node("Inicio")
self.size = 0
# Representación de cadena de la Pila

def __str__(self):
cur = self.head.next
out = ""
while cur:
out += str(cur.value) + "->"
cur = cur.next
return out[:-3]
# Tamaño actual de la Pila

ESTRUCTURA DE DATOS
def getSize(self):
return self.size
# Verificar si la Pila esta vacia

def isEmpty(self):
return self.size == 0
# Obtener el elemento de encima de la Pila.

def peek(self):
if self.isEmpty():
raise Exception("La Pila está vacia")
return self.head.next.value
# Inserta un element a la Pila.

def push(self, value):
node = Node(value)
node.next = self.head.next
self.head.next = node
self.size += 1
# Elimina un element de la Pila.

def pop(self):
if self.isEmpty():
raise Exception("No hay elemento que eliminar en una Pila vacia")
remove = self.head.next
self.head.next = self.head.next.next
self.size -= 1
return remove.value
stack = Stack()
for i in range(1, 11):
stack.push(i)
print(f"Pila: {stack}")
for _ in range(1, 6):

remove = stack.pop()
print(f"Pop: {remove}")
print(f"Pila: {stack}")
IV. EJERCICIOS PRÁCTICOS A DESARROLLAR:

1. Escriba una rutina que reciba una Pila P de números enteros y mueva sus
elementos a una nueva Pila, pero manteniendo el orden de salida de los mismos. Al
finalizar la Pila P no debe contener elementos.
ESTRUCTURA DE DATOS
V. BIBLIOGRAFÍA
1. The Algorithm Design Manual. Steven S. Skiena,Second Edition, Springer
2. Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, Clifford Stein, 3er Edition, McGraw-Hill.

Guía 08 - TAD Pila

Cargado por

Copyright:

Formatos disponibles

Guía 08 - TAD Pila

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Guía 08 - TAD Pila

Cargado por

Copyright:

Formatos disponibles

UNIVERSIDAD ANDINA DEL CUSCO

FACULTAD DE INGENIERÍA Y ARQUITECTURA

Guía de estudio Nº 08: TAD Pila.

Fecha: octubre 2022

Las funciones asociadas con la pila utilizando arreglos son:

• push(a) – Inserta el elemento 'a' en la parte superior de la pila – Complejidad de

Las funciones asociadas con la pila utilizando listas enlazadas son:

Figura 6. Regiones de la memoria RAM

Otra aplicación es la gestión de ventanas en Windows (cuando cerramos una ventana

III. DESARROLLO EN LABORATORIO:

# append() función para insertar el elemento en la pila (push)

#Función para eliminar un elemento de la pila en el orden LIFO (pop)

print('\nPila después de eliminar los elementos:')

2. Implementación de una Pila utilizando listas enlazadas:

# Representación de cadena de la Pila

# Tamaño actual de la Pila

# Verificar si la Pila esta vacia

# Obtener el elemento de encima de la Pila.

# Inserta un element a la Pila.

# Elimina un element de la Pila.

for _ in range(1, 6):

IV. EJERCICIOS PRÁCTICOS A DESARROLLAR:

También podría gustarte