Trabajar con pilas

Estructuras de datos y algoritmos en Python

Miriam Antona

Software Engineer

Pilas

LIFO: Last-In First-Out
- El último insertado es el primero en salir

Una pila de libros.

Pilas

LIFO: Last-In First-Out
- El último insertado es siempre el primero en salir
Solo puedes añadir en la cima
- Push a la pila

Una pila de libros con un nuevo libro añadido en la cima.

Pilas

LIFO: Last-In First-Out
- El último insertado es siempre el primero en salir
Solo puedes añadir en la cima
- Push a la pila
Solo puedes tomar de la cima
- Pop de la pila

Una pila de libros con un libro tomado de la cima.

Pilas

LIFO: Last-In First-Out
- El último insertado es el primero en salir
Solo puedes añadir en la cima
- Push a la pila
Solo puedes quitar de la cima
- Pop de la pila
Solo puedes leer el último elemento
- Peek de la pila

Una pila de libros con una flecha apuntando a la tapa del libro en la cima.

Pilas: usos reales

Función deshacer

Una pila con un elemento.

Pilas: usos reales

Función deshacer
- push de cada pulsación

Una pila con un nuevo elemento añadido en la cima.

Pilas: usos reales

Función deshacer
- push de cada pulsación

Una pila con un nuevo elemento añadido en la cima.

Pilas: usos reales

Función deshacer
- push de cada pulsación

Una pila con un nuevo elemento añadido en la cima.

Pilas: usos reales

Función deshacer
- push de cada pulsación

Una pila con un nuevo elemento añadido en la cima.

Pilas: usos reales

Función deshacer
- push de cada pulsación
- pop de la última pulsación

Una pila donde se ha quitado un elemento de la cima.

Pilas: usos reales

Comprobador de símbolos: ( [ { } ] )
- push de símbolos de apertura

Una pila con un símbolo de apertura.

Pilas: usos reales

Comprobador de símbolos: ( [ { } ] )
- push de símbolos de apertura

Una pila con un nuevo símbolo de apertura añadido en la cima.

Pilas: usos reales

Comprobador de símbolos: ( [ { } ] )
- push de símbolos de apertura

Una pila con un nuevo símbolo de apertura añadido en la cima.

Pilas: usos reales

Comprobador de símbolos: ( [ { } ] )
- push de símbolos de apertura
- check símbolo de cierre

Una pila con símbolos de apertura y la palabra "check "}"".

Pilas: usos reales

Comprobador de símbolos: ( [ { } ] )
- push de símbolos de apertura
- check símbolo de cierre
- pop del símbolo de apertura coincidente

Una pila de la que se ha quitado un símbolo de apertura de la cima.

Pilas: usos reales

Llamadas a funciones
- push del bloque de memoria
- pop al terminar la ejecución

Pilas: implementación con listas enlazadas simples

Una pila representada como lista enlazada.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

Pilas: implementación con listas enlazadas simples

Una pila representada como lista enlazada con los nombres de las partes de los nodos.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

Pilas: implementación con listas enlazadas simples

Una pila representada como lista enlazada con la palabra "TOP" apuntando a la cima.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

Pilas: push

Representación de una pila vacía y una con elementos.

def push(self, data):

Pilas: push

Representación de una pila vacía y una con elementos donde se va a insertar un nuevo nodo.

def push(self, data): 
  new_node = Node(data)

  if self.top:

Pilas: push

Representación de una pila vacía y una con elementos, donde el nuevo nodo se conecta al elemento en la cima.

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top

Pilas: push

Representación de una pila vacía y una con elementos donde se ha insertado el nuevo nodo.

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node

Pilas: pop

def pop(self):

  if self.top is None:

    return None

  else:

Representación de una pila con la palabra "TOP" apuntando al nodo en la cima.

Pilas: pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

Representación de una pila con "popped_node" apuntando al nodo en la cima.

Pilas: pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

Representación de una pila con "popped_node" apuntando al nodo en la cima y "TOP" al segundo nodo.

Pilas: pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

Representación de una pila con "popped_node" apuntando a un nodo desconectado y "TOP" al nodo en la cima.

Pilas: pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

Representación de una pila con la palabra "TOP" apuntando al nodo en la cima.

Pilas: peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue en Python

LifoQueue:
- Módulo queue de Python
- se comporta como una pila

import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python