資料結構[Python--Stack] 的應用

難得有些許空閑，看一下Python的資料結構--Stack，現将幾個典型示例進行總結！

一、什麼是棧

     棧是一個有序集合，根據其特性可以稱為"先進後出"或"後進先出", 其中添加或删除都發生在同一端，這一端被稱為"棧頂"，與其對應的叫"棧底"。

    棧的底部很重要，因為其底部存儲的資料是時間最長的，最近的添加項總是最先會彈出，這種排序原則有時被稱為"LIFO"

二、棧

1. 棧的可用操作

<code>Stack()</code> 建立一個空的新棧。 它不需要參數，并傳回一個空棧。

<code>push(item)</code>将一個新項添加到棧的頂部。它需要 <code>item</code> 做參數并不傳回任何内容。

<code>pop()</code> 從棧中删除頂部項。它不需要參數并傳回<code>item</code> 。棧被修改。

<code>top()</code> 從棧傳回頂部項，但不會删除它。不需要參數。 不修改棧。

<code>isEmpty()</code>測試棧是否為空。不需要參數，并傳回布爾值。

<code>size()</code> 傳回棧中的<code>item</code> 數量。不需要參數，并傳回一個整數。

<code>clear</code> 清空棧，沒有傳回值

2. 利用Python 的内置的資料結構List實作棧全部操作

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

<code>class</code> <code>Stack():</code>

<code>    </code><code>def</code> <code>__init__(</code><code>self</code><code>):</code>

<code>        </code><code>self</code><code>.itmes </code><code>=</code> <code>[]</code>

<code>    </code><code>def</code> <code>isEmpty(</code><code>self</code><code>):</code>

<code>        </code><code>return</code> <code>self</code><code>.itmes </code><code>=</code><code>=</code> <code>[]</code>

<code>    </code><code>def</code> <code>clear(</code><code>self</code><code>):</code>

<code>        </code><code>del</code> <code>self</code><code>.itmes[:]</code>

<code>    </code><code>def</code> <code>push(</code><code>self</code><code>, item):</code>

<code>        </code><code>self</code><code>.items.append(item)</code>

<code>    </code><code>def</code> <code>pop(</code><code>self</code><code>):</code>

<code>        </code><code>return</code> <code>self</code><code>.itmes.pop()</code>

<code>    </code><code>def</code> <code>top(</code><code>self</code><code>):</code>

<code>        </code><code>return</code> <code>self</code><code>.items[</code><code>-</code><code>1</code><code>]</code>

<code>    </code><code>def</code> <code>size(</code><code>self</code><code>):</code>

<code>        </code><code>return</code> <code>len</code><code>(</code><code>self</code><code>.itmes)</code>

3. 棧的使用示例

3.1 進制轉換

16

17

18

19

20

21

22

23

24

25

26

27

<code>def</code> <code>divideBy2(decNumber, base):</code>

<code>    </code><code>remstack </code><code>=</code> <code>Stack()</code>

<code>    </code><code>while</code> <code>decNumber &gt; </code><code>0</code><code>:</code>

<code>        </code><code>rem </code><code>=</code> <code>decNumber </code><code>%</code> <code>base</code>

<code>        </code><code>remstack.push(rem)</code>

<code>        </code><code>decNumber </code><code>=</code> <code>decNumber </code><code>/</code><code>/</code> <code>base</code>

<code>    </code><code>binString </code><code>=</code> <code>""</code>

<code>    </code><code>while</code> <code>not</code> <code>remstack.empty():</code>

<code>        </code><code>binString </code><code>=</code> <code>binString </code><code>+</code> <code>str</code><code>(remstack.pop())</code>

<code>    </code><code>return</code> <code>binString</code>

<code>if</code> <code>__name__ </code><code>=</code><code>=</code> <code>'__main__'</code><code>:</code>

<code>    </code><code>print</code><code>(divideBy2(</code><code>42</code><code>, </code><code>2</code><code>))</code>

說明： 這是用List結構來實作的"棧", 同樣我們可以自己寫一個棧

3.2 自己寫棧

<code>class</code> <code>Node:</code>

<code>    </code><code>def</code> <code>__init__(</code><code>self</code><code>, value):</code>

<code>        </code><code>self</code><code>.value </code><code>=</code> <code>value</code>

<code>        </code><code>self</code><code>.</code><code>next</code> <code>=</code> <code>None</code>

<code>class</code> <code>Stack:</code>

<code>        </code><code>self</code><code>.top </code><code>=</code> <code>None</code>

<code>    </code><code>def</code> <code>push(</code><code>self</code><code>, value):</code>

<code>        </code><code>node </code><code>=</code> <code>Node(value)</code>

<code>        </code><code>node.</code><code>next</code> <code>=</code> <code>self</code><code>.top</code>

<code>        </code><code>self</code><code>.top </code><code>=</code> <code>node</code>

<code>        </code><code>node </code><code>=</code> <code>self</code><code>.top</code>

<code>        </code><code>self</code><code>.top </code><code>=</code> <code>node.</code><code>next</code>

<code>        </code><code>return</code> <code>node.value</code>

<code>s </code><code>=</code> <code>Stack()</code>

<code>s.push(</code><code>3</code><code>)</code>

<code>s.push(</code><code>'ac'</code><code>)</code>

<code>s.push(</code><code>'er'</code><code>)</code>

<code>s.pop()</code>

<code>s.push(</code><code>5</code><code>)</code>

說明

上面所定義的棧，是由top指針指向一個完整的Node執行個體

定義一個棧，使用指針控制其讀取的位置。

3.3 棧應用--字首表達式(波蘭式)

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

<code>from</code> <code>__future__ </code><code>import</code> <code>division</code>

<code>class</code> <code>Node():</code>

<code>class</code> <code>StackNode():</code>

<code>def</code> <code>compute_exec(op, ov1, ov2):</code>

<code>    </code><code>def</code> <code>add(ov1, ov2):</code>

<code>        </code><code>return</code> <code>ov1 </code><code>+</code> <code>ov2</code>

<code>    </code><code>def</code> <code>sub(ov1, ov2):</code>

<code>        </code><code>return</code> <code>ov1 </code><code>-</code> <code>ov2</code>

<code>    </code><code>def</code> <code>mul(ov1, ov2):</code>

<code>        </code><code>return</code> <code>ov1 </code><code>*</code> <code>ov2</code>

<code>    </code><code>def</code> <code>div(ov1, ov2):</code>

<code>        </code><code>return</code> <code>ov1 </code><code>/</code> <code>ov2</code>

<code>    </code><code>ops </code><code>=</code> <code>{add: </code><code>'+'</code><code>, sub: </code><code>'-'</code><code>, mul: </code><code>'*'</code><code>, div: </code><code>"/"</code><code>}</code>

<code>    </code><code>for</code> <code>k, v </code><code>in</code> <code>ops.items():</code>

<code>        </code><code>if</code> <code>v </code><code>=</code><code>=</code> <code>op:</code>

<code>            </code><code>ret </code><code>=</code> <code>k(ov1, ov2)</code>

<code>            </code><code>stack1.push(ret)</code>

<code>            </code><code>break</code>

<code>def</code> <code>perfix_reverse(string):  </code><code># reverse</code>

<code>    </code><code>tmp </code><code>=</code> <code>''</code>

<code>    </code><code>for</code> <code>s </code><code>in</code> <code>string[::</code><code>-</code><code>1</code><code>]:</code>

<code>        </code><code>if</code> <code>s </code><code>=</code><code>=</code> <code>"("</code><code>:</code>

<code>            </code><code>tmp </code><code>+</code><code>=</code> <code>")"</code>

<code>        </code><code>elif</code> <code>s </code><code>=</code><code>=</code> <code>")"</code><code>:</code>

<code>            </code><code>tmp </code><code>+</code><code>=</code> <code>"("</code>

<code>        </code><code>else</code><code>:</code>

<code>            </code><code>tmp </code><code>+</code><code>=</code> <code>s</code>

<code>    </code><code>return</code> <code>tmp</code>

<code>def</code> <code>infix_to_prefix(string):</code>

<code>    </code><code>opt </code><code>=</code> <code>''</code>

<code>    </code><code>string_tmp </code><code>=</code> <code>perfix_reverse(string)</code>

<code>    </code><code>for</code> <code>i </code><code>in</code> <code>string_tmp:  </code><code>#  字首表達式</code>

<code>        </code><code>if</code> <code>i.isdigit():</code>

<code>            </code><code>opt </code><code>=</code> <code>i </code><code>+</code> <code>opt</code>

<code>        </code><code>elif</code> <code>i !</code><code>=</code> <code>')'</code><code>:</code>

<code>            </code><code>stack1.push(i)</code>

<code>        </code><code>elif</code> <code>i </code><code>=</code><code>=</code> <code>")"</code><code>:</code>

<code>            </code><code>opt </code><code>=</code> <code>stack1.pop() </code><code>+</code> <code>opt</code>

<code>            </code><code>stack1.pop()</code>

<code>    </code><code>for</code> <code>s </code><code>in</code> <code>opt[::</code><code>-</code><code>1</code><code>]:</code>

<code>        </code><code>if</code> <code>s.isdigit():</code>

<code>            </code><code>stack1.push(s)</code>

<code>                </code><code>op1 </code><code>=</code> <code>s</code>

<code>                </code><code>ov1 </code><code>=</code> <code>stack1.pop()</code>

<code>                </code><code>ov2 </code><code>=</code> <code>stack1.pop()</code>

<code>                </code><code>compute_exec(op1, </code><code>int</code><code>(ov1), </code><code>int</code><code>(ov2))  </code><code># compute result </code>

<code>                </code><code>continue</code>

<code>    </code><code>return</code> <code>opt, stack1.pop()</code>

<code>    </code><code>stack1 </code><code>=</code> <code>StackNode()  </code><code># 操作符</code>

<code>    </code><code>infix </code><code>=</code> <code>[</code><code>'((3+4)*2)'</code><code>, </code><code>'((3+(4*2))-1)'</code><code>, </code><code>'(5*(1+2))'</code><code>]</code>

<code>    </code><code>for</code> <code>i, v </code><code>in</code> <code>enumerate</code><code>(infix):</code>

<code>        </code><code>print</code> <code>infix[i], </code><code>"==&gt;"</code><code>, infix_to_prefix(v)</code>

說明：

字首表達式就是說操作符位于操作數之前

表達式從右向左依次解析。将數值壓棧，遇到符号将棧頂的操作數與次位置彈出進行計算，結果再次入棧，直到表達式解析完成。

3.4 棧應用--字尾表達式（逆波蘭式）

<code>def</code> <code>postfix(expr):</code>

<code>    </code><code>for</code> <code>s </code><code>in</code> <code>expr:</code>

<code>            </code><code>stack2.push(s)</code>

<code>        </code><code>elif</code> <code>s !</code><code>=</code> <code>")"</code><code>:</code>

<code>            </code><code>top </code><code>=</code> <code>stack2.pop()</code>

<code>            </code><code>snext </code><code>=</code> <code>stack2.pop()</code>

<code>            </code><code>stack2.push(''.join([snext, top, stack1.pop()]))</code>

<code>    </code><code>post_expr </code><code>=</code> <code>stack2.pop()</code>

<code>    </code><code>for</code> <code>i </code><code>in</code> <code>post_expr:</code>

<code>            </code><code>op </code><code>=</code> <code>i</code>

<code>            </code><code>top </code><code>=</code> <code>stack1.pop()</code>

<code>            </code><code>snext </code><code>=</code> <code>stack1.pop()</code>

<code>            </code><code>compute_exec(op, </code><code>int</code><code>(snext), </code><code>int</code><code>(top))</code>

<code>    </code><code>return</code> <code>post_expr, stack1.pop()</code>

<code>    </code><code>stack2 </code><code>=</code> <code>StackNode()  </code><code># 操作數</code>

<code>    </code><code>exprs </code><code>=</code> <code>[</code><code>'((3+(4*2))-1)'</code><code>, </code><code>'((3*4)+(3/2))'</code><code>]</code>

<code>    </code><code>for</code> <code>e </code><code>in</code> <code>exprs:</code>

<code>        </code><code>print</code> <code>e, </code><code>"==&gt;"</code><code>, postfix(e)</code>

說明:

 字尾表達式就是說操作符位于操作數之後。

 表達式從左向右依次解析。将數值壓棧，遇到符号将棧頂的操作數與次位置彈出進行計算[次位操作數 棧頂操作數 操作符 ]，結果再次入棧，直到表達式解析完成

 計算表達式結果時同樣是[次位操作數 操作符 棧頂操作數 ]

四、總結

以上後兩個示例代碼基于自己了解所寫，可能存在bug

後兩個示例的缺點是沒有寫表達式合法性的檢查，表達式的優先級（如表達式無括号可能會導緻程式異常）

此處僅是對棧的一此粗淺了解及應用。

本文轉自 jinlinger 51CTO部落格，原文連結：http://blog.51cto.com/essun/1941041，如需轉載請自行聯系原作者