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
页:
[1]