数据结构-栈

栈是链表的约束版本

新节点只能在栈顶插入和删除
后进先出的数据结构
最后一个节点设为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 = 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 tempNode
100     
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 representation
17         """
18 
19         return str( self._stackList )
20 
21     def push( self,element ):
22         """
23          push data onto stack
24         """
25         self._stackList.insertAtFront( element )
26 
27     def pop( self ):
28         """
29         pop data from stack
30         """
31 
32         return self._stackList.removeFromFront()
33 
34     def isEmpty( self ):
35         """
36         Return 1 if Stack is empty
37         """
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 ",stack
13 
14 while not stack.isEmpty():
15     pop = stack.pop()
16     print pop,"popped from stack"
17     print "The stack is: ", stack