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#stack.py
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.__head = None
self.__size = 0
def push(self, data):
new_node = Node(data)
new_node.next = self.__head
self.__head = new_node
self.__size += 1
def top(self):
return self.__head.data
def pop(self):
old_node = self.__head
self.__head = old_node.next
self.__size -= 1
return old_node.data
def size(self):
return self.__size
def is_empty(self):
return self.__head is None
def __str__(self):
s = "["
head = self.__head
while head is not None:
s += str(head.data) + ", "
head = head.next
s += "]"
return s
def __repr__(self):
return self.__str__()
Código Python:
Ver original#queue.py
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.__head = None
self.__tail = None
self.__size = 0
def enqueue(self, data):
new_node = Node(data)
if self.__head is None or self.__tail is None:
self.__head = self.__tail = new_node
else:
self.__tail.next = new_node
self.__tail = new_node
self.__size += 1
def top(self):
return self.__head.data
def dequeue(self):
old_node = self.__head
self.__head = old_node.next
self.__size -= 1
return old_node.data
def size(self):
return self.__size
def is_empty(self):
return self.__head is None
def __str__(self):
s = "["
head = self.__head
while head is not None:
s += str(head.data) + ", "
head = head.next
s += "]"
return s
def __repr__(self):
return self.__str__()
Ejemplo de uso.
Código Python:
Ver originalfrom queue import Queue
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.top() #return 1
queue.dequeue() #returns 1
queue.dequeue() #returns 2
queue.dequeue() #returns 3
queue.is_empty() #returns True
Código Python:
Ver originalfrom stack import Stack
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.top() #Returns 3
stack.pop() #Returns 3
stack.pop() #Returns 2
stack.pop() #Returns 1
queue.is_empty() #returns True
Mas adelante la explicación de por que funciona.