首页 > 代码库 > 数据结构-2
数据结构-2
栈是链表的约束版本
新节点只能在栈顶插入和删除
后进先出的数据结构
最后一个节点设为None，表面是栈底
push和pop方法分别向栈添加和删除一个节点
实现分2个文件，测试采用1个文件
ListModule.py实现链表
1 # ListModule.py 2 # Classes List and Node definitions. 3 4 class Node: 5 """Single node in a data structure""" 6 7 def __init__( self, data ): 8 """Node constructor""" 9 10 self._data =http://www.mamicode.com/ data 11 self._nextNode = None 12 13 def __str__( self ): 14 """Node data representation""" 15 16 return str( self._data ) 17 18 class List: 19 """Linked list""" 20 21 def __init__( self ): 22 """List constructor""" 23 24 self._firstNode = None 25 self._lastNode = None 26 27 def __str__( self ): 28 """List string representation""" 29 30 if self.isEmpty(): 31 return "empty" 32 33 currentNode = self._firstNode 34 output = [] 35 36 while currentNode is not None: 37 output.append( str( currentNode._data ) ) 38 currentNode = currentNode._nextNode 39 40 return " ".join( output ) 41 42 def insertAtFront( self, value ): 43 """Insert node at front of list""" 44 45 newNode = Node( value ) 46 47 if self.isEmpty(): # List is empty 48 self._firstNode = self._lastNode = newNode 49 else: # List is not empty 50 newNode._nextNode = self._firstNode 51 self._firstNode = newNode 52 53 def insertAtBack( self, value ): 54 """Insert node at back of list""" 55 56 newNode = Node( value ) 57 58 if self.isEmpty(): # List is empty 59 self._firstNode = self._lastNode = newNode 60 else: # List is not empty 61 self._lastNode._nextNode = newNode 62 self._lastNode = newNode 63 64 def removeFromFront( self ): 65 """Delete node from front of list""" 66 67 if self.isEmpty(): # raise exception on empty list 68 raise IndexError, "remove from empty list" 69 70 tempNode = self._firstNode 71 72 if self._firstNode is self._lastNode: # one node in list 73 self._firstNode = self._lastNode = None 74 else: 75 self._firstNode = self._firstNode._nextNode 76 77 return tempNode 78 79 def removeFromBack( self ): 80 """Delete node from back of list""" 81 82 if self.isEmpty(): # raise exception on empty list 83 raise IndexError, "remove from empty list" 84 85 tempNode = self._lastNode 86 87 if self._firstNode is self._lastNode: # one node in list 88 self._firstNode = self._lastNode = None 89 else: 90 currentNode = self._firstNode 91 92 # locate second-to-last node 93 while currentNode._nextNode is not self._lastNode: 94 currentNode = currentNode._nextNode 95 96 currentNode._nextNode = None 97 self._lastNode = currentNode 98 99 return tempNode100 101 def isEmpty( self ):102 """Returns true if List is empty"""103 104 return self._firstNode is None
StackModule.py 为栈的实现
1 # StackModule.py 2 # Class Stack definition 3 4 from ListModule import List 5 6 class Stack( List ): 7 """ Stack composed from linked list """ 8 9 def __init__( self ):10 """ Stack constructor """11 12 self._stackList = List()13 14 def __str__(self):15 """16 Stack string representation17 """18 19 return str( self._stackList )20 21 def push( self,element ):22 """23 push data onto stack24 """25 self._stackList.insertAtFront( element )26 27 def pop( self ):28 """29 pop data from stack30 """31 32 return self._stackList.removeFromFront()33 34 def isEmpty( self ):35 """36 Return 1 if Stack is empty37 """38 39 return self._stackList.isEmpty()
测试文件testStack.py
1 # testStack.py 2 # Driver to test class Stack 3 4 from StackModule import Stack 5 6 stack = Stack() 7 8 print "Processing a stack" 9 10 for i in range( 4 ):11 stack.push( i )12 print "The stack is ",stack13 14 while not stack.isEmpty():15 pop = stack.pop()16 print pop,"popped from stack"17 print "The stack is: ", stack
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。