資料結構與算法(一）
算法的概念
算法是計算機處理資訊的本質，因為計算機程式本質上是一個算法來告訴計算機确切的步驟來執行一個指定的任務。一般地，當算法在處理資訊時，會從輸入裝置或資料的存儲位址讀取資料，把結果寫入輸出裝置或某個存儲位址供以後再調用。
算法是獨立存在的一種解決問題的方法和思想。
對于算法而言，實作的語言并不重要，重要的是思想。
算法可以有不同的語言描述實作版本（如C描述、C++描述、Python描述等），我們現在是在用Python語言進行描述實作。
算法的五大特性
- 輸入: 算法具有0個或多個輸入
- 輸出: 算法至少有1個或多個輸出
- 有窮性: 算法在有限的步驟之後會自動結束而不會無限循環，并且每一個步驟可以在可接受的時間内完成
- 确定性：算法中的每一步都有确定的含義，不會出現二義性
- 可行性：算法的每一步都是可行的，也就是說每一步都能夠執行有限的次數完成
先來看一道題:
如果 i+j+k=1000，且 i^2+j^2=k^2（i,j,k 為自然數），如何求出所有i,j,k可能的組合?
1 #!/usr/bin/eny python
2 # -*- coding:utf-8 -*-
3 import time
4
5 a = time.time()
6 for i in range(1001):
7 for j in range(1001):
8 for k in range(1001):
9 if i + k + j == 1000 and i*i + j*j == k*k:
10 print i ,j ,k
11
12 b = time.time()
13 #輸出運作時間
14 print b-a 結果：
0 500 500
200 375 425
375 200 425
500 0 500
164.008999825 改：
#!/usr/bin/eny python
# -*- coding:utf-8 -*-
import time
a = time.time()
for i in range(1001):
for j in range(1001):
k = 1000 - i - j
if i*i + j*j == k*k:
print i ,j ,k
b = time.time()
print b-a 結果;
0 500 500
200 375 425
375 200 425
500 0 500
0.408999919891 算法效率衡量
執行時間反應算法效率
對于同一問題，我們給出了兩種解決算法，在兩種算法的實作中，我們對程式執行的時間進行了測算，發現兩段程式執行的時間相差懸殊（164秒相比于0.4秒），由此我們可以得出結論：實作算法程式的執行時間可以反應出算法的效率，即算法的優劣。
單靠時間值絕對可信嗎？
假設我們将第二次嘗試的算法程式運作在一台配置古老性能低下的計算機中，情況會如何？很可能運作的時間并不會比在我們的電腦中運作算法一的214.583347秒快多少。
單純依靠運作的時間來比較算法的優劣并不一定是客觀準确的！
程式的運作離不開計算機環境（包括硬體和作業系統），這些客觀原因會影響程式運作的速度并反應在程式的執行時間上。那麼如何才能客觀的評判一個算法的優劣呢？
時間複雜度與“大O記法”
我們假定計算機執行算法每一個基本操作的時間是固定的一個時間機關，那麼有多少個基本操作就代表會花費多少時間機關。雖然對于不同的機器環境而言，确切的機關時間是不同的，但是對于算法進行多少個基本操作（即花費多少時間機關）在規模數量級上卻是相同的，由此可以忽略機器環境的影響而客觀的反應算法的時間效率。
對于算法的時間效率，我們可以用“大O記法”來表示。
“大O記法”：對于單調的整數函數f，如果存在一個整數函數g和實常數c>0，使得對于充分大的n總有f(n)<=c*g(n)，就說函數g是f的一個漸近函數（忽略常數），記為f(n)=O(g(n))。也就是說，在趨向無窮的極限意義下，函數f的增長速度受到函數g的限制，亦即函數f與函數g的特征相似。
時間複雜度：假設存在函數g，使得算法A處理規模為n的問題示例所用時間為T(n)=O(g(n))，則稱O(g(n))為算法A的漸近時間複雜度，簡稱時間複雜度，記為T(n)
如何了解“大O記法”
對于算法進行特别具體的細緻分析雖然很好，但在實踐中的實際價值有限。對于算法的時間性質和空間性質，最重要的是其數量級和趨勢，這些是分析算法效率的主要部分。而計量算法基本操作數量的規模函數中那些常量因子可以忽略不計。例如，可以認為3n2和100n2屬于同一個量級，如果兩個算法處理同樣規模執行個體的代價分别為這兩個函數，就認為它們的效率“差不多”，都為n2級。
最壞時間複雜度
分析算法時，存在幾種可能的考慮：
- 算法完成工作最少需要多少基本操作，即最優時間複雜度
- 算法完成工作最多需要多少基本操作，即最壞時間複雜度
- 算法完成工作平均需要多少基本操作，即平均時間複雜度
對于最優時間複雜度，其價值不大，因為它沒有提供什麼有用資訊，其反映的隻是最樂觀最理想的情況，沒有參考價值。
對于最壞時間複雜度，提供了一種保證，表明算法在此種程度的基本操作中一定能完成工作。
對于平均時間複雜度，是對算法的一個全面評價，是以它完整全面的反映了這個算法的性質。但另一方面，這種衡量并沒有保證，不是每個計算都能在這個基本操作内完成。而且，對于平均情況的計算，也會因為應用算法的執行個體分布可能并不均勻而難以計算。
是以，我們主要關注算法的最壞情況，亦即最壞時間複雜度。
時間複雜度的幾條基本計算規則
- 基本操作，即隻有常數項，認為其時間複雜度為O(1)
- 順序結構，時間複雜度按加法進行計算
- 循環結構，時間複雜度按乘法進行計算
- 分支結構，時間複雜度取最大值
- 判斷一個算法的效率時，往往隻需要關注操作數量的最高次項，其它次要項和常數項可以忽略
- 在沒有特殊說明時，我們所分析的算法的時間複雜度都是指最壞時間複雜度
常見時間複雜度
| 執行次數函數舉例 | 階 | 非正式術語 |
|---|---|---|
| 12 | O(1) | 常數階 |
| 2n+3 | O(n) | 線性階 |
| 3n2+2n+1 | O(n2) | 平方階 |
| 5log2n+20 | O(logn) | 對數階 |
| 2n+3nlog2n+19 | O(nlogn) | 對數線性階 |
| 6n3+2n2+3n+4 | O(n3) | 立方階 |
| 2n | O(2n) | 指數階 |
注意，經常将log2n（以2為底的對數）簡寫成logn
常見時間複雜度之間的關系
所消耗的時間從小到大
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
Python内置類型性能分析
timeit子產品
timeit子產品可以用來測試一小段Python代碼的執行速度。
class timeit.Timer(stmt=\'pass\', setup=\'pass\', timer=<timer function>)
Timer是測量小段代碼執行速度的類。
stmt參數是要測試的代碼語句（statment）；
setup參數是運作代碼時需要的設定；
timer參數是一個定時器函數，與平台有關。
timeit.Timer.timeit(number=1000000)
Timer類中測試語句執行速度的對象方法。number參數是測試代碼時的測試次數，預設為1000000次。方法傳回執行代碼的平均耗時，一個float類型的秒數。
list的操作測試
1 def test1():
2 l = []
3 for i in range(1000):
4 l = l + [i]
5 def test2():
6 l = []
7 for i in range(1000):
8 l.append(i)
9 def test3():
10 l = [i for i in range(1000)]
11 def test4():
12 l = list(range(1000))
13
14 from timeit import Timer
15
16 t1 = Timer("test1()", "from __main__ import test1")
17 print("concat ",t1.timeit(number=1000), "seconds")
18 t2 = Timer("test2()", "from __main__ import test2")
19 print("append ",t2.timeit(number=1000), "seconds")
20 t3 = Timer("test3()", "from __main__ import test3")
21 print("comprehension ",t3.timeit(number=1000), "seconds")
22 t4 = Timer("test4()", "from __main__ import test4")
23 print("list range ",t4.timeit(number=1000), "seconds")
24
25 # (\'concat \', 1.7890608310699463, \'seconds\')
26 # (\'append \', 0.13796091079711914, \'seconds\')
27 # (\'comprehension \', 0.05671119689941406, \'seconds\')
28 # (\'list range \', 0.014147043228149414, \'seconds\') View Code
list内置操作的時間複雜度
dict内置操作的時間複雜度
資料結構
概念
資料是一個抽象的概念，将其進行分類後得到程式設計語言中的基本類型。如：int，float，char等。資料元素之間不是獨立的，存在特定的關系，這些關系便是結構。資料結構指資料對象中資料元素之間的關系。
Python給我們提供了很多現成的資料結構類型，這些系統自己定義好的，不需要我們自己去定義的資料結構叫做Python的内置資料結構，比如清單、元組、字典。而有些資料組織方式，Python系統裡面沒有直接定義，需要我們自己去定義實作這些資料的組織方式，這些資料組織方式稱之為Python的擴充資料結構，比如棧，隊列等。
算法與資料結構的差別
資料結構隻是靜态的描述了資料元素之間的關系。
高效的程式需要在資料結構的基礎上設計和選擇算法。
程式 = 資料結構 + 算法
總結：算法是為了解決實際問題而設計的，資料結構是算法需要處理的問題載體
抽象資料類型(Abstract Data Type)
抽象資料類型(ADT)的含義是指一個數學模型以及定義在此數學模型上的一組操作。即把資料類型和資料類型上的運算捆在一起，進行封裝。引入抽象資料類型的目的是把資料類型的表示和資料類型上運算的實作與這些資料類型和運算在程式中的引用隔開，使它們互相獨立。
最常用的資料運算有五種：
-
- 插入
- 删除
- 修改
- 查找
- 排序
在程式中，經常需要将一組（通常是同為某個類型的）資料元素作為整體管理和使用，需要建立這種元素組，用變量記錄它們，傳進傳出函數等。一組資料中包含的元素個數可能發生變化（可以增加或删除元素）。
對于這種需求，最簡單的解決方案便是将這樣一組元素看成一個序列，用元素在序列裡的位置和順序，表示實際應用中的某種有意義的資訊，或者表示資料之間的某種關系。
這樣的一組序列元素的組織形式，我們可以将其抽象為線性表。一個線性表是某類元素的一個集合，還記錄着元素之間的一種順序關系。線性表是最基本的資料結構之一，在實際程式中應用非常廣泛，它還經常被用作更複雜的資料結構的實作基礎。
根據線性表的實際存儲方式，分為兩種實作模型：
-
- 順序表，将元素順序地存放在一塊連續的存儲區裡，元素間的順序關系由它們的存儲順序自然表示。
- 連結清單，将元素存放在通過連結構造起來的一系列存儲塊中
順序表的基本形式
圖a表示的是順序表的基本形式，資料元素本身連續存儲，每個元素所占的存儲單元大小固定相同，元素的下标是其邏輯位址，而元素存儲的實體位址（實際記憶體位址）可以通過存儲區的起始位址Loc (e0)加上邏輯位址（第i個元素）與存儲單元大小（c）的乘積計算而得，即：
Loc(ei) = Loc(e0) + c*i
故，通路指定元素時無需從頭周遊，通過計算便可獲得對應位址，其時間複雜度為O(1)。
如果元素的大小不統一，則須采用圖b的元素外置的形式，将實際資料元素另行存儲，而順序表中各單元位置儲存對應元素的位址資訊（即連結）。由于每個連結所需的存儲量相同，通過上述公式，可以計算出元素連結的存儲位置，而後順着連結找到實際存儲的資料元素。注意，圖b中的c不再是資料元素的大小，而是存儲一個連結位址所需的存儲量，這個量通常很小。
圖b這樣的順序表也被稱為對實際資料的索引，這是最簡單的索引結構。
順序表的結構與實作
順序表的結構
一個順序表的完整資訊包括兩部分，一部分是表中的元素集合，另一部分是為實作正确操作而需記錄的資訊，即有關表的整體情況的資訊，這部分資訊主要包括元素存儲區的容量和目前表中已有的元素個數兩項。
順序表的兩種基本實作方式
圖a為一體式結構，存儲表資訊的單元與元素存儲區以連續的方式安排在一塊存儲區裡，兩部分資料的整體形成一個完整的順序表對象。
一體式結構整體性強，易于管理。但是由于資料元素存儲區域是表對象的一部分，順序表建立後，元素存儲區就固定了。
圖b為分離式結構，表對象裡隻儲存與整個表有關的資訊（即容量和元素個數），實際資料元素存放在另一個獨立的元素存儲區裡，通過連結與基本表對象關聯。
元素存儲區替換
一體式結構由于順序表資訊區與資料區連續存儲在一起，是以若想更換資料區，則隻能整體搬遷，即整個順序表對象（指存儲順序表的結構資訊的區域）改變了。
分離式結構若想更換資料區，隻需将表資訊區中的資料區連結位址更新即可，而該順序表對象不變。
元素存儲區擴充
采用分離式結構的順序表，若将資料區更換為存儲空間更大的區域，則可以在不改變表對象的前提下對其資料存儲區進行了擴充，所有使用這個表的地方都不必修改。隻要程式的運作環境（計算機系統）還有空閑存儲，這種表結構就不會因為滿了而導緻操作無法進行。人們把采用這種技術實作的順序表稱為動态順序表，因為其容量可以在使用中動态變化。
擴充的兩種政策
-
每次擴充增加強定數目的存儲位置，如每次擴充增加10個元素位置，這種政策可稱為線性增長。
特點：節省空間，但是擴充操作頻繁，操作次數多。
-
每次擴充容量加倍，如每次擴充增加一倍存儲空間。
特點：減少了擴充操作的執行次數，但可能會浪費空間資源。以空間換時間，推薦的方式。
順序表的操作
增加元素
如圖所示，為順序表增加新元素111的三種方式
a. 尾端加入元素，時間複雜度為O(1)
b. 非保序的加入元素（不常見），時間複雜度為O(1)
c. 保序的元素加入，時間複雜度為O(n)
删除元素
a. 删除表尾元素，時間複雜度為O(1)
b. 非保序的元素删除（不常見），時間複雜度為O(1)
c. 保序的元素删除，時間複雜度為O(n)
Python中的順序表
Python中的list和tuple兩種類型采用了順序表的實作技術，具有前面讨論的順序表的所有性質。
tuple是不可變類型，即不變的順序表，是以不支援改變其内部狀态的任何操作，而其他方面，則與list的性質類似。
list的基本實作技術
Python标準類型list就是一種元素個數可變的線性表，可以加入和删除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：
-
基于下标（位置）的高效元素通路和更新，時間複雜度應該是O(1)；
為滿足該特征，應該采用順序表技術，表中元素儲存在一塊連續的存儲區中。
-
允許任意加入元素，而且在不斷加入元素的過程中，表對象的辨別（函數id得到的值）不變。
為滿足該特征，就必須能更換元素存儲區，并且為保證更換存儲區時list對象的辨別id不變，隻能采用分離式實作技術。
在Python的官方實作中，list就是一種采用分離式技術實作的動态順序表。這就是為什麼用list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。
在Python的官方實作中，list實作采用了如下的政策：在建立空表（或者很小的表）時，系統配置設定一塊能容納8個元素的存儲區；在執行插入操作（insert或append）時，如果元素存儲區滿就換一塊4倍大的存儲區。但如果此時的表已經很大（目前的閥值為50000），則改變政策，采用加一倍的方法。引入這種改變政策的方式，是為了避免出現過多空閑的存儲位置。
連結清單
為什麼需要連結清單
順序表的建構需要預先知道資料大小來申請連續的存儲空間，而在進行擴充時又需要進行資料的搬遷，是以使用起來并不是很靈活。
連結清單結構可以充分利用計算機記憶體空間，實作靈活的記憶體動态管理。
連結清單的定義
連結清單（Linked list）是一種常見的基礎資料結構，是一種線性表，但是不像順序表一樣連續存儲資料，而是在每一個節點（資料存儲單元）裡存放下一個節點的位置資訊（即位址）。
單向連結清單
單向連結清單也叫單連結清單，是連結清單中最簡單的一種形式，它的每個節點包含兩個域，一個資訊域（元素域）和一個連結域。這個連結指向連結清單中的下一個節點，而最後一個節點的連結域則指向一個空值。
- 表元素域elem用來存放具體的資料。
- 連結域next用來存放下一個節點的位置（python中的辨別）
- 變量p指向連結清單的頭節點（首節點）的位置，從p出發能找到表中的任意節點。
單向循環連結清單
單連結清單的一個變形是單向循環連結清單，連結清單中最後一個節點的next域不再為None，而是指向連結清單的頭節點。
操作
- is_empty() 判斷連結清單是否為空
- length() 傳回連結清單的長度
- travel() 周遊
- add(item) 在頭部添加一個節點
- append(item) 在尾部添加一個節點
- insert(pos, item) 在指定位置pos添加節點
- remove(item) 删除一個節點
- search(item) 查找節點是否存在
實作
1 #!/usr/bin/eny python
2 # -*- coding:utf-8 -*-
3 class Node(object):
4 """節點"""
5 def __init__(self, item):
6 self.item = item
7 self.next = None
8
9
10 class SinCycLinkedlist(object):
11 """單向循環連結清單"""
12 def __init__(self):
13 self._head = None
14
15 def is_empty(self):
16 """判斷連結清單是否為空"""
17 return self._head == None
18
19 def length(self):
20 """傳回連結清單的長度"""
21 # 如果連結清單為空，傳回長度0
22 if self.is_empty():
23 return 0
24 count = 1
25 cur = self._head
26 while cur.next != self._head:
27 count += 1
28 cur = cur.next
29 return count
30
31 def travel(self):
32 """周遊連結清單"""
33 if self.is_empty():
34 return
35 cur = self._head
36 print cur.item,
37 while cur.next != self._head:
38 cur = cur.next
39 print cur.item,
40 print ""
41
42
43 def add(self, item):
44 """頭部添加節點"""
45 node = Node(item)
46 if self.is_empty():
47 self._head = node
48 node.next = self._head
49 else:
50 #添加的節點指向_head
51 node.next = self._head
52 # 移到連結清單尾部，将尾部節點的next指向node
53 cur = self._head
54 while cur.next != self._head:
55 cur = cur.next
56 cur.next = node
57 #_head指向添加node的
58 self._head = node
59
60 def append(self, item):
61 """尾部添加節點"""
62 node = Node(item)
63 if self.is_empty():
64 self._head = node
65 node.next = self._head
66 else:
67 # 移到連結清單尾部
68 cur = self._head
69 while cur.next != self._head:
70 cur = cur.next
71 # 将尾節點指向node
72 cur.next = node
73 # 将node指向頭節點_head
74 node.next = self._head
75
76 def insert(self, pos, item):
77 """在指定位置添加節點"""
78 if pos <= 0:
79 self.add(item)
80 elif pos > (self.length()-1):
81 self.append(item)
82 else:
83 node = Node(item)
84 cur = self._head
85 count = 0
86 # 移動到指定位置的前一個位置
87 while count < (pos-1):
88 count += 1
89 cur = cur.next
90 node.next = cur.next
91 cur.next = node
92
93 def remove(self, item):
94 """删除一個節點"""
95 # 若連結清單為空，則直接傳回
96 if self.is_empty():
97 return
98 # 将cur指向頭節點
99 cur = self._head
100 pre = None
101 # 若頭節點的元素就是要查找的元素item
102 if cur.item == item:
103 # 如果連結清單不止一個節點
104 if cur.next != self._head:
105 # 先找到尾節點，将尾節點的next指向第二個節點
106 while cur.next != self._head:
107 cur = cur.next
108 # cur指向了尾節點
109 cur.next = self._head.next
110 self._head = self._head.next
111 else:
112 # 連結清單隻有一個節點
113 self._head = None
114 else:
115 pre = self._head
116 # 第一個節點不是要删除的
117 while cur.next != self._head:
118 # 找到了要删除的元素
119 if cur.item == item:
120 # 删除
121 pre.next = cur.next
122 return
123 else:
124 pre = cur
125 cur = cur.next
126 # cur 指向尾節點
127 if cur.item == item:
128 # 尾部删除
129 pre.next = cur.next
130
131 def search(self, item):
132 """查找節點是否存在"""
133 if self.is_empty():
134 return False
135 cur = self._head
136 if cur.item == item:
137 return True
138 while cur.next != self._head:
139 cur = cur.next
140 if cur.item == item:
141 return True
142 return False
143
144 if __name__ == "__main__":
145 ll = SinCycLinkedlist()
146 ll.add(1)
147 ll.add(2)
148 ll.append(3)
149 ll.insert(2, 4)
150 ll.insert(4, 5)
151 ll.insert(0, 6)
152 print "length:",ll.length()
153 ll.travel()
154 print ll.search(3)
155 print ll.search(7)
156 ll.remove(1)
157 print "length:",ll.length()
158 ll.travel() View Code
雙向連結清單
一種更複雜的連結清單是“雙向連結清單”或“雙面連結清單”。每個節點有兩個連結：一個指向前一個節點，當此節點為第一個節點時，指向空值；而另一個指向下一個節點，當此節點為最後一個節點時，指向空值。
連結清單與順序表的對比
連結清單失去了順序表随機讀取的優點，同時連結清單由于增加了結點的指針域，空間開銷比較大，但對存儲空間的使用要相對靈活。
連結清單與順序表的各種操作複雜度如下所示：
| 操作 | 連結清單 | 順序表 |
|---|---|---|
| 通路元素 | O(n) | O(1) |
| 在頭部插入/删除 | O(1) | O(n) |
| 在尾部插入/删除 | O(n) | O(1) |
| 在中間插入/删除 | O(n) | O(n) |
注意雖然表面看起來複雜度都是 O(n)，但是連結清單和順序表在插入和删除時進行的是完全不同的操作。連結清單的主要耗時操作是周遊查找，删除和插入操作本身的複雜度是O(1)。順序表查找很快，主要耗時的操作是拷貝覆寫。因為除了目标元素在尾部的特殊情況，順序表進行插入和删除時需要對操作點之後的所有元素進行前後移位操作，隻能通過拷貝和覆寫的方法進行。
棧
棧（stack），有些地方稱為堆棧，是一種容器，可存入資料元素、通路元素、删除元素，它的特點在于隻能允許在容器的一端（稱為棧頂端名額，英語：top）進行加入資料（英語：push）和輸出資料（英語：pop）的運算。沒有了位置概念，保證任何時候可以通路、删除的元素都是此前最後存入的那個元素，确定了一種預設的通路順序。
由于棧資料結構隻允許在一端進行操作，因而按照後進先出（LIFO, Last In First Out）的原理運作。
棧結構實作
棧可以用順序表實作，也可以用連結清單實作。
棧的操作
- Stack() 建立一個新的空棧
- push(item) 添加一個新的元素item到棧頂
- pop() 彈出棧頂元素
- peek() 傳回棧頂元素
- is_empty() 判斷棧是否為空
- size() 傳回棧的元素個數
1 棧結構實作
2
3 棧可以用順序表實作，也可以用連結清單實作。
4
5 棧的操作
6
7 Stack() 建立一個新的空棧
8 push(item) 添加一個新的元素item到棧頂
9 pop() 彈出棧頂元素
10 peek() 傳回棧頂元素
11 is_empty() 判斷棧是否為空
12 size() 傳回棧的元素個數 View Code
結果：
3
itcast
itcast
world
hello
0 隊列
隊列（queue）是隻允許在一端進行插入操作，而在另一端進行删除操作的線性表。
隊列是一種先進先出的（First In First Out）的線性表，簡稱FIFO。允許插入的一端為隊尾，允許删除的一端為隊頭。隊列不允許在中間部位進行操作！假設隊列是q=（A1，A2，……，An），那麼A1就是隊頭元素，而An是隊尾元素。這樣我們就可以删除時，總是從A1開始，而插入時，總是在隊列最後。這也比較符合我們通常生活中的習慣，排在第一個的優先出列，最後來的當然排在隊伍最後。
隊列的實作
同棧一樣，隊列也可以用順序表或者連結清單實作。
操作
- Queue() 建立一個空的隊列
- enqueue(item) 往隊列中添加一個item元素
- dequeue() 從隊列頭部删除一個元素
- is_empty() 判斷一個隊列是否為空
- size() 傳回隊列的大小
1 #!/usr/bin/eny python
2 # -*- coding:utf-8 -*-
3
4
5 class Queue(object):
6 """隊列"""
7 def __init__(self):
8 self.items = []
9
10 def is_empty(self):
11 return self.items == []
12
13 def enqueue(self, item):
14 """進隊列"""
15 self.items.insert(0,item)
16
17 def dequeue(self):
18 """出隊列"""
19 return self.items.pop()
20
21 def size(self):
22 """傳回大小"""
23 return len(self.items)
24
25 if __name__ == "__main__":
26 q = Queue()
27 q.enqueue("hello")
28 q.enqueue("world")
29 q.enqueue("itcast")
30 print q.size()
31 print q.dequeue()
32 print q.dequeue()
33 print q.dequeue() View Code
結果：
3
hello
world
itcast 雙端隊列
雙端隊列（deque，全名double-ended queue），是一種具有隊列和棧的性質的資料結構。
雙端隊列中的元素可以從兩端彈出，其限定插入和删除操作在表的兩端進行。雙端隊列可以在隊列任意一端入隊和出隊。
操作
- Deque() 建立一個空的雙端隊列
- add_front(item) 從隊頭加入一個item元素
- add_rear(item) 從隊尾加入一個item元素
- remove_front() 從隊頭删除一個item元素
- remove_rear() 從隊尾删除一個item元素
- is_empty() 判斷雙端隊列是否為空
- size() 傳回隊列的大小
實作
1 class Deque(object):
2 """雙端隊列"""
3 def __init__(self):
4 self.items = []
5
6 def is_empty(self):
7 """判斷隊列是否為空"""
8 return self.items == []
9
10 def add_front(self, item):
11 """在隊頭添加元素"""
12 self.items.insert(0,item)
13
14 def add_rear(self, item):
15 """在隊尾添加元素"""
16 self.items.append(item)
17
18 def remove_front(self):
19 """從隊頭删除元素"""
20 return self.items.pop(0)
21
22 def remove_rear(self):
23 """從隊尾删除元素"""
24 return self.items.pop()
25
26 def size(self):
27 """傳回隊列大小"""
28 return len(self.items)
29
30
31 if __name__ == "__main__":
32 deque = Deque()
33 deque.add_front(1)
34 deque.add_front(2)
35 deque.add_rear(3)
36 deque.add_rear(4)
37 print deque.size()
38 print deque.remove_front()
39 print deque.remove_front()
40 print deque.remove_rear()
41 print deque.remove_rear() View Code
結果：
4
2
1
4
3 View Code