https://www.bilibili.com/video/av53583801/?p=32
學習筆記
文章目錄
- 1 Stack
- 2 Queue
- 3 Double-End Queue
1 Stack
棧只是一個容器，數(shù)據(jù)存儲形式不局限于某一種，比如順序表、鏈表都可以，只要滿足 FILO（First in Last out）。為了方便，我們這里采用順序表的形式實現(xiàn)棧，因為 python 的 list 就可以當順序表用！
class
Stack
(
object
)
:
"棧"
def
__init__
(
self
)
:
self
.
__list
=
[
]
# 用列表，也即順序表的數(shù)據(jù)存儲方式
def
is_empty
(
self
)
:
"判斷棧是否為空，空返回True"
return
self
.
__list
==
[
]
def
size
(
self
)
:
"求棧元素的個數(shù)"
return
len
(
self
.
__list
)
def
push
(
self
,
item
)
:
"進棧"
self
.
__list
.
append
(
item
)
#這里選擇在尾巴上加，復雜度 o(1)，如果用insert在頭上加復雜度為o(n)
def
peek
(
self
)
:
"返回棧頂元素"
if
self
.
is_empty
(
)
:
return
None
else
:
return
self
.
__list
[
-
1
]
def
pop
(
self
)
:
"出棧"
if
self
.
is_empty
(
)
:
return
None
else
:
return
self
.
__list
.
pop
(
)
if
__name__
==
"__main__"
:
s
=
Stack
(
)
print
(
"empty:"
,
s
.
is_empty
(
)
)
s
.
push
(
1
)
s
.
push
(
2
)
s
.
push
(
3
)
s
.
push
(
4
)
print
(
"empty:"
,
s
.
is_empty
(
)
)
print
(
"size:"
,
s
.
size
(
)
)
print
(
"peek:"
,
s
.
peek
(
)
)
print
(
s
.
pop
(
)
)
print
(
s
.
pop
(
)
)
print
(
s
.
pop
(
)
)
print
(
s
.
pop
(
)
)
output
empty
:
True
empty
:
False
size
:
4
peek
:
4
4
3
2
1
2 Queue
用 list 實現(xiàn)的話，如果
頭入O(n)尾出O(1)
，和
尾入O(1)頭出O(n)
，復雜度都是 O(n)！這個時候要根據(jù)實際操作來選擇合適的寫法，比如你是經(jīng)常入隊列的話，建議用
尾入O(1)頭出O(n)
，如果你是經(jīng)常出隊列的話，就
頭入O(n)尾出O(1)
class
Queue
(
object
)
:
"隊列"
def
__init__
(
self
)
:
self
.
__list
=
[
]
# 用列表，也即順序表的數(shù)據(jù)存儲方式
def
is_empty
(
self
)
:
"是否為空"
return
self
.
__list
==
[
]
def
enqueue
(
self
,
item
)
:
"入隊列"
self
.
__list
.
append
(
item
)
def
dequeue
(
self
)
:
"出隊列"
if
self
.
is_empty
(
)
:
return
None
else
:
return
self
.
__list
.
pop
(
0
)
def
size
(
self
)
:
"求隊列的長度"
return
len
(
self
.
__list
)
def
peek
(
self
)
:
"查看隊首元素"
if
self
.
is_empty
(
)
:
return
None
else
:
return
self
.
__list
[
0
]
if
__name__
==
"__main__"
:
q
=
Queue
(
)
print
(
"empty:"
,
q
.
is_empty
(
)
)
q
.
enqueue
(
1
)
q
.
enqueue
(
2
)
q
.
enqueue
(
3
)
q
.
enqueue
(
4
)
print
(
"empty:"
,
q
.
is_empty
(
)
)
print
(
"size:"
,
q
.
size
(
)
)
print
(
"peek:"
,
q
.
peek
(
)
)
print
(
q
.
dequeue
(
)
)
print
(
q
.
dequeue
(
)
)
print
(
q
.
dequeue
(
)
)
print
(
q
.
dequeue
(
)
)
output
empty
:
True
empty
:
False
size
:
4
peek
:
1
1
2
3
4
3 Double-End Queue
和隊列的區(qū)別就是，頭部可入可出，尾部可入可出！我們實現(xiàn)的時候頭部指的是 list 下標為 0 的地方！當然你也可以讓 list 的最后一個元素是頭部！
class
DeQueue
(
object
)
:
"雙端隊列"
def
__init__
(
self
)
:
self
.
__list
=
[
]
# 用列表，也即順序表的數(shù)據(jù)存儲方式
def
is_empty
(
self
)
:
"是否為空"
return
self
.
__list
==
[
]
def
add_front
(
self
,
item
)
:
"頭入隊列"
self
.
__list
.
insert
(
0
,
item
)
def
add_rear
(
self
,
item
)
:
"尾入隊列"
self
.
__list
.
append
(
item
)
def
pop_front
(
self
)
:
"頭出隊列"
if
self
.
is_empty
(
)
:
return
None
else
:
return
self
.
__list
.
pop
(
0
)
def
pop_rear
(
self
)
:
"尾出隊列"
if
self
.
is_empty
(
)
:
return
None
else
:
return
self
.
__list
.
pop
(
)
def
size
(
self
)
:
"求隊列的長度"
return
len
(
self
.
__list
)
def
peek
(
self
)
:
"查看隊首元素"
if
self
.
is_empty
(
)
:
return
None
else
:
return
self
.
__list
[
0
]
更多文章、技術(shù)交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
