該書隨書源碼的語言為C;我參考書中內容和配套源碼,寫了一套Python格式的配套源碼。這套配套源碼並非直接翻譯C語言的配套源碼,而是結合我的理解略作了修改。
Stack 棧的結構定義
<code>class
Stack
:"""棧的結構定義"""
def
__init__
(self)
:"""初始化一個空棧"""
pass
def
__len__
(self)
:"""返回棧內元素數量"""
pass
def
is_empty
(self)
:"""返回棧是否為空棧"""
pass
def
clear
(self)
:"""清空棧"""
pass
def
top
(self)
:"""若棧存在且非空,則返回棧頂元素"""
pass
def
push
(self, value)
:"""若棧存在,則插入新元素value到棧中併成為棧頂元素"""
pass
def
pop
(self)
:"""若棧存在,則刪除棧頂元素並返回其值"""
pass
/<code>
ArrayStack 順序存儲結構的棧(Python列表存儲)
<code>from
Stack.Stackimport
Stack class
ArrayStack
(Stack)
:"""順序存儲結構的棧(Python列表存儲)"""
def
__init__
(self)
:"""初始化一個空棧"""
super().__init__() self._data = [] def
__len__
(self)
:"""返回棧內元素數量"""
return
len(self._data) def
is_empty
(self)
:"""返回棧是否為空棧"""
return
len(self._data) ==0
def
clear
(self)
:"""清空棧"""
self._data.clear() def
top
(self)
:"""若棧存在且非空,則返回棧頂元素"""
if
self.is_empty():raise
ValueError("Stack is Empty"
)return
self._data[-1
] def
push
(self, value)
:"""若棧存在,則插入新元素value到棧中併成為棧頂元素"""
self._data.append(value) def
pop
(self)
:"""若棧存在,則刪除棧頂元素並返回其值"""
if
self.is_empty():raise
ValueError("Stack is Empty"
)return
self._data.pop()/<code>
LinkedStack 鏈式存儲結構的棧(單鏈表存儲)
<code>from
LinkedList.SinglyLinkedNodeimport
SinglyLinkedNodefrom
Stack.Stackimport
Stack class
LinkedStack
(Stack)
:"""鏈式存儲結構的棧(單鏈表存儲)"""
def
__init__
(self)
: super().__init__() self._head =None
self._size =0
def
__len__
(self)
:"""返回棧中元素的數量"""
return
self._size def
is_empty
(self)
:"""返回棧是否為空"""
return
self._size ==0
def
clear
(self)
:"""清空棧"""
self._head =None
self._size =0
def
push
(self, value)
:"""向棧中壓入元素"""
self._head = SinglyLinkedNode(value, self._head) self._size +=1
def
top
(self)
:"""查詢棧頂元素"""
if
self.is_empty():raise
ValueError("Stack is Empty"
)return
self._head.value def
pop
(self)
:"""取出棧頂元素"""
if
self.is_empty():raise
ValueError("Stack is Empty"
) ans = self._head.value self._head = self._head.next self._size -=1
return
ans/<code>
其中: