Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1734227
  • 博文数量: 297
  • 博客积分: 285
  • 博客等级: 二等列兵
  • 技术积分: 3006
  • 用 户 组: 普通用户
  • 注册时间: 2010-03-06 22:04
个人简介

Linuxer, ex IBMer. GNU https://hmchzb19.github.io/

文章分类

全部博文(297)

文章存档

2020年(11)

2019年(15)

2018年(43)

2017年(79)

2016年(79)

2015年(58)

2014年(1)

2013年(8)

2012年(3)

分类: Python/Ruby

2015-07-09 14:38:00

LinkedStack

点击(此处)折叠或打开

  1. class LinkedStack:
  2.     #LIFO Stack implementation using a singly linked list for storage

  3.     #nested _Node class
  4.     class _Node:
  5.         __slots__='_element','_next'

  6.         def __init__(self,element,next):
  7.             self._element=element
  8.             self._next=next

  9. #------------------------------------------------
  10.     def __init__(self):
  11.         self._head=None
  12.         self._size=0

  13.     def __len__(self):
  14.         return self._size

  15.     def is_empty(self):
  16.         return self._size==0

  17.     def push(self,e):
  18.         self._head=self._Node(e,self._head)
  19.         self._size+=1

  20.     def top(self):
  21.         if self.is_empty():
  22.             raise Exception('Stack is empty')
  23.         return self._head._element

  24.     def pop(self):
  25.         if self.is_empty():
  26.             raise Exception("stack is empty")
  27.         answer=self._head._element
  28.         self._head=self._head._next
  29.         self._size-=1
  30.         return answer
LinkedQueue的实现:

点击(此处)折叠或打开

  1. class LinkedQueue:
  2.     #FIFO queue implementation using a singly linked list for storage

  3.     #nested _Node class
  4.     class _Node:
  5.         __slots__='_element','_next'

  6.         def __init__(self,element,next):
  7.             self._element=element
  8.             self._next=next

  9. #------------------------------------------------
  10.     def __init__(self):
  11.         self._head=None
  12.         self._tail=None
  13.         self._size=0

  14.     def is_empty(self):
  15.         return self._size==0

  16.     def __len__(self):
  17.         return self._size

  18.     def first(self):
  19.         if self.is_empty():
  20.             raise Exception("Queue is empty")
  21.         return self._head._element

  22.     def dequeue(self):
  23.         if self.is_empty():
  24.             raise Exception("Queue is empty")
  25.         answer=self._head._element
  26.         self._head=self._head._next
  27.         self._size-=1
  28.         if self.is_empty():
  29.             self._tail=None
  30.         return answer

  31.     def enqueue(self,e):
  32.         newest=self._Node(e,None)
  33.         if self.is_empty():
  34.             self._head=newest
  35.         else:
  36.             self._tail._next=newest
  37.         self._tail=newest
  38.         self._size+=1
CircularQueue

点击(此处)折叠或打开

  1. class CircularQueue:
  2.     #Queue implementation using circularly linked list for storage

  3.     #nested _Node class
  4.     class _Node:
  5.         __slots__='_element','_next'

  6.         def __init__(self,element,next):
  7.             self._element=element
  8.             self._next=next

  9. #------------------------------------------------
  10.     def __init__(self):

  11.         self._tail=None
  12.         self._size=0

  13.     def __len__(self):
  14.         return self._size

  15.     def is_empty(self):
  16.         return self._size==0

  17.     def first(self):
  18.         if self.is_empty():
  19.             raise Exception('Queue is empty')
  20.         head=self._tail._next
  21.         return head._element

  22.     def dequeue(self):
  23.         #remove and return the first element of the queue
  24.         if self.is_empty():
  25.             raise Exception("Queue is empty")
  26.         oldhead=self._tail._next
  27.         if self._size==1:
  28.             self._tail=None
  29.         else:
  30.             self._tail._next=oldhead._next
  31.         self._size-=1
  32.         return oldhead._element

  33.     def enqueue(self,e):
  34.         #Add an element to the back of queue
  35.         newest=self._Node(e,None)
  36.         if self.is_empty():
  37.             newest._next=newest
  38.         else:
  39.             newest._next=self._tail._next
  40.             self._tail._next=newest
  41.         self._tail=newest
  42.         self._size+=1

  43.     def rotate(self):
  44.         #rotate front element to the back of the queue
  45.         if self._size > 0:
  46.             self._tail = self._tail._next

阅读(1096) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~