https://www.bilibili.com/video/av53583801/?p=32
学习笔记
文章目录
- 1 Stack
- 2 Queue
- 3 Double-End Queue
1 Stack
栈只是一个容器，数据存储形式不局限于某一种，比如顺序表、链表都可以，只要满足 FILO（First in Last out）。为了方便，我们这里采用顺序表的形式实现栈，因为 python 的 list 就可以当顺序表用！
class
Stack
(
object
)
:
"栈"
def
__init__
(
self
)
:
self
.
__list
=
[
]
# 用列表，也即顺序表的数据存储方式
def
is_empty
(
self
)
:
"判断栈是否为空，空返回True"
return
self
.
__list
==
[
]
def
size
(
self
)
:
"求栈元素的个数"
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 实现的话，如果
头入O(n)尾出O(1)
，和
尾入O(1)头出O(n)
，复杂度都是 O(n)！这个时候要根据实际操作来选择合适的写法，比如你是经常入队列的话，建议用
尾入O(1)头出O(n)
，如果你是经常出队列的话，就
头入O(n)尾出O(1)
class
Queue
(
object
)
:
"队列"
def
__init__
(
self
)
:
self
.
__list
=
[
]
# 用列表，也即顺序表的数据存储方式
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
和队列的区别就是，头部可入可出，尾部可入可出！我们实现的时候头部指的是 list 下标为 0 的地方！当然你也可以让 list 的最后一个元素是头部！
class
DeQueue
(
object
)
:
"双端队列"
def
__init__
(
self
)
:
self
.
__list
=
[
]
# 用列表，也即顺序表的数据存储方式
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
]
