LinkStack linkQueue 的实现，摘自Data Structures and Algorithms in python

还是简单才最好

LinkedStack

• class LinkedStack:
  
  
•     #LIFO Stack implementation using a singly linked list for storage
  
• 
  
•     #nested _Node class
  
•     class _Node:
  
•         __slots__='_element','_next'
  
• 
  
•         def __init__(self,element,next):
  
•             self._element=element
  
•             self._next=next
  
• 
  
• #------------------------------------------------
  
•     def __init__(self):
  
•         self._head=None
  
•         self._size=0
  
• 
  
•     def __len__(self):
  
•         return self._size
  
• 
  
•     def is_empty(self):
  
•         return self._size==0
  
• 
  
•     def push(self,e):
  
•         self._head=self._Node(e,self._head)
  
•         self._size+=1
  
• 
  
•     def top(self):
  
•         if self.is_empty():
  
•             raise Exception('Stack is empty')
  
•         return self._head._element
  
• 
  
•     def pop(self):
  
•         if self.is_empty():
  
•             raise Exception("stack is empty")
  
•         answer=self._head._element
  
•         self._head=self._head._next
  
•         self._size-=1
  
•         return answer
  

LinkedQueue的实现：

• class LinkedQueue:
  
  
•     #FIFO queue implementation using a singly linked list for storage
  
• 
  
•     #nested _Node class
  
•     class _Node:
  
•         __slots__='_element','_next'
  
• 
  
•         def __init__(self,element,next):
  
•             self._element=element
  
•             self._next=next
  
• 
  
• #------------------------------------------------
  
•     def __init__(self):
  
•         self._head=None
  
•         self._tail=None
  
•         self._size=0
  
• 
  
•     def is_empty(self):
  
•         return self._size==0
  
• 
  
•     def __len__(self):
  
•         return self._size
  
• 
  
•     def first(self):
  
•         if self.is_empty():
  
•             raise Exception("Queue is empty")
  
•         return self._head._element
  
• 
  
•     def dequeue(self):
  
•         if self.is_empty():
  
•             raise Exception("Queue is empty")
  
•         answer=self._head._element
  
•         self._head=self._head._next
  
•         self._size-=1
  
•         if self.is_empty():
  
•             self._tail=None
  
•         return answer
  
• 
  
•     def enqueue(self,e):
  
•         newest=self._Node(e,None)
  
•         if self.is_empty():
  
•             self._head=newest
  
•         else:
  
•             self._tail._next=newest
  
•         self._tail=newest
  
•         self._size+=1
  

CircularQueue

• class CircularQueue:
  
  
•     #Queue implementation using circularly linked list for storage
  
• 
  
•     #nested _Node class
  
•     class _Node:
  
•         __slots__='_element','_next'
  
• 
  
•         def __init__(self,element,next):
  
•             self._element=element
  
•             self._next=next
  
• 
  
• #------------------------------------------------
  
•     def __init__(self):
  
• 
  
•         self._tail=None
  
•         self._size=0
  
• 
  
•     def __len__(self):
  
•         return self._size
  
• 
  
•     def is_empty(self):
  
•         return self._size==0
  
• 
  
•     def first(self):
  
•         if self.is_empty():
  
•             raise Exception('Queue is empty')
  
•         head=self._tail._next
  
•         return head._element
  
• 
  
•     def dequeue(self):
  
•         #remove and return the first element of the queue
  
•         if self.is_empty():
  
•             raise Exception("Queue is empty")
  
•         oldhead=self._tail._next
  
•         if self._size==1:
  
•             self._tail=None
  
•         else:
  
•             self._tail._next=oldhead._next
  
•         self._size-=1
  
•         return oldhead._element
  
• 
  
•     def enqueue(self,e):
  
•         #Add an element to the back of queue
  
•         newest=self._Node(e,None)
  
•         if self.is_empty():
  
•             newest._next=newest
  
•         else:
  
•             newest._next=self._tail._next
  
•             self._tail._next=newest
  
•         self._tail=newest
  
•         self._size+=1
  
• 
  
•     def rotate(self):
  
•         #rotate front element to the back of the queue
  
•         if self._size > 0:
  
•             self._tail = self._tail._next