Foros del Web » Programando para Internet » Python »

[Aporte] Pilas y Colas

Estas en el tema de [Aporte] Pilas y Colas en el foro de Python en Foros del Web. Primero que nada, entiendo perfectamente que existen clases o módulos completos, que no solamente implementan Pilas (Stacks) o Colas (Queues), si no que ademas implementan ...
  #1 (permalink)  
Antiguo 12/04/2012, 11:36
Avatar de razpeitia
Moderador
 
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 17 años, 5 meses
Puntos: 1360
[Aporte] Pilas y Colas

Primero que nada, entiendo perfectamente que existen clases o módulos completos, que no solamente implementan Pilas (Stacks) o Colas (Queues), si no que ademas implementan estructuras de datos mucho mas complejas.

Este aporte, esta hecho para los estudiantes tengan una noción de como implementar pilas y colas en python. Básicamente es una implementación casera.

Código Python:
Ver original
  1. #stack.py
  2. class Node:
  3.     def __init__(self, data):
  4.         self.data = data
  5.         self.next = None
  6.  
  7. class Stack:
  8.     def __init__(self):
  9.         self.__head = None
  10.         self.__size = 0
  11.  
  12.     def push(self, data):
  13.         new_node = Node(data)
  14.         new_node.next = self.__head
  15.         self.__head = new_node
  16.         self.__size += 1
  17.  
  18.     def top(self):
  19.         return self.__head.data
  20.  
  21.     def pop(self):
  22.         old_node = self.__head
  23.         self.__head = old_node.next
  24.         self.__size -= 1
  25.         return old_node.data
  26.  
  27.     def size(self):
  28.         return self.__size
  29.  
  30.     def is_empty(self):
  31.         return self.__head is None
  32.  
  33.     def __str__(self):
  34.         s = "["
  35.         head = self.__head
  36.         while head is not None:
  37.             s += str(head.data) + ", "
  38.             head = head.next
  39.         s += "]"
  40.         return s
  41.  
  42.     def __repr__(self):
  43.         return self.__str__()

Código Python:
Ver original
  1. #queue.py
  2. class Node:
  3.     def __init__(self, data):
  4.         self.data = data
  5.         self.next = None
  6.  
  7. class Queue:
  8.     def __init__(self):
  9.         self.__head = None
  10.         self.__tail = None
  11.         self.__size = 0
  12.  
  13.     def enqueue(self, data):
  14.         new_node = Node(data)
  15.         if self.__head is None or self.__tail is None:
  16.             self.__head = self.__tail = new_node
  17.         else:
  18.             self.__tail.next = new_node
  19.             self.__tail = new_node
  20.         self.__size += 1
  21.  
  22.     def top(self):
  23.         return self.__head.data
  24.  
  25.     def dequeue(self):
  26.         old_node = self.__head
  27.         self.__head = old_node.next
  28.         self.__size -= 1
  29.         return old_node.data
  30.  
  31.     def size(self):
  32.         return self.__size
  33.  
  34.     def is_empty(self):
  35.         return self.__head is None
  36.  
  37.     def __str__(self):
  38.         s = "["
  39.         head = self.__head
  40.         while head is not None:
  41.             s += str(head.data) + ", "
  42.             head = head.next
  43.         s += "]"
  44.         return s
  45.  
  46.     def __repr__(self):
  47.         return self.__str__()

Ejemplo de uso.
Código Python:
Ver original
  1. from queue import Queue
  2. queue = Queue()
  3. queue.enqueue(1)
  4. queue.enqueue(2)
  5. queue.enqueue(3)
  6. queue.top() #return 1
  7. queue.dequeue() #returns 1
  8. queue.dequeue() #returns 2
  9. queue.dequeue() #returns 3
  10. queue.is_empty() #returns True

Código Python:
Ver original
  1. from stack import Stack
  2. stack = Stack()
  3. stack.push(1)
  4. stack.push(2)
  5. stack.push(3)
  6. stack.top() #Returns 3
  7. stack.pop() #Returns 3
  8. stack.pop() #Returns 2
  9. stack.pop() #Returns 1
  10. queue.is_empty() #returns True

Mas adelante la explicación de por que funciona.

Etiquetas: colas, pilas
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 21:17.