詳細版本見個人博客：Python用list實現堆棧和隊列
Python中可以用list來模擬棧和隊列：
- 棧（stack） :只能在一端進行數據操作，遵循后進先出（LIFO）原則
- 隊列（queue） :可以在兩端進行數據操作，遵循先進先出（FIFO）原則，出隊列的一端稱為隊首，入隊列的一端稱為隊尾
一、棧
1、棧要記錄的數據
- 棧頂位置top：注意這個top有兩種理解方式，一種是表示棧的最后一個數據的位置，另一種是表示棧的最后一個數據的下一個位置，這兩種理解對棧的操作代碼有一定的影響
- 棧最大大小size
2、棧的操作
-
isEmpty()：判斷棧是否為空 -
isFull()：判斷棧是否已滿 -
push(element)：向棧中添加一個值， 注意棧是否為滿的 -
pop()：從棧中彈出一個值， 注意棧是否為空
3、Python列表實現棧
class
StackException
(
Exception
)
:
def
__init__
(
self
,
data
)
:
self
.
data
=
data
def
__str__
(
self
)
:
return
self
.
data
class
Stack
(
object
)
:
def
__init__
(
self
,
size
=
10
)
:
self
.
S
=
[
]
self
.
size
=
size
# 棧大小
self
.
top
=
-
1
# 棧頂位置
def
setSize
(
self
,
size
)
:
# 設置棧的大小
self
.
size
=
size
def
isEmpty
(
self
)
:
# 判斷棧是否為空
if
self
.
top
==
-
1
:
return
True
else
:
return
False
def
isFull
(
self
)
:
# 判斷棧是否滿
if
self
.
top
==
self
.
size
-
1
:
return
True
else
:
return
False
def
peek
(
self
)
:
# 查看棧頂的對象，但不移除
if
self
.
isEmpty
(
)
:
raise
StackException
(
'StackUnderflow'
)
else
:
element
=
self
.
S
[
-
1
]
return
element
def
pop
(
self
)
:
# 移除棧頂對象，并返回該對象的值
if
self
.
isEmpty
(
)
:
raise
StackException
(
'StackUnderflow'
)
else
:
element
=
self
.
S
[
-
1
]
self
.
top
=
self
.
top
-
1
del
self
.
S
[
-
1
]
return
element
def
push
(
self
,
element
)
:
# 把對象壓入棧頂
if
self
.
isFull
(
)
:
raise
StackException
(
'StackOverflow'
)
else
:
self
.
S
.
append
(
element
)
self
.
top
=
self
.
top
+
1
if
__name__
==
'__main__'
:
s
=
Stack
(
)
# 壓棧測試
for
i
in
range
(
10
)
:
s
.
push
(
i
)
# 棧滿測試
try
:
s
.
push
(
1
)
except
Exception
as
e
:
print
(
e
)
# 出棧測試
for
i
in
range
(
10
)
:
print
(
s
.
pop
(
)
)
# 棧空測試
try
:
s
.
pop
(
)
except
Exception
as
e
:
print
(
e
)
二、隊列
1、隊列要記錄的數據
- 隊頭位置end
- 隊列的大小size
2、標準做法
利用數組
Q[1..n]來實現含有n-1個元素隊列（保留一位元素用來判斷隊列空或滿）。該列有一個屬性Q.head指向隊頭元素，屬性Q.tail指向下一個新元素將要插入的位置，列中的元素存放在位置Q.head, Q.head+1, …, Q.tail-1上。
- 初始時，
Q.head = Q.tail = 1- 當
Q.head = Q.tail時， 隊列為空- 當
Q.head = Q.tail + 1時，隊列為滿
3、隊列的操作
-
isEmpty()：判斷隊列是否為空 -
isFull()：判斷隊列是否已滿 -
inQueue(element)：入隊 -
outQueue()：出隊
4、Python列表實現隊列
class
QueueException
(
Exception
)
:
def
__init__
(
self
,
data
)
:
self
.
data
=
data
def
__str__
(
self
)
:
return
self
.
data
class
Queue
(
object
)
:
def
__init__
(
self
,
size
=
10
)
:
self
.
Q
=
[
]
self
.
size
=
size
# 隊列大小
self
.
end
=
-
1
# 隊頭位置
def
setSize
(
self
,
size
)
:
# 設置隊列的大小
self
.
size
=
size
def
inQueue
(
self
,
element
)
:
# 對象入隊
if
self
.
end
<
self
.
size
-
1
:
self
.
Q
.
append
(
element
)
self
.
end
+=
1
else
:
raise
QueueException
(
'QueueFull'
)
def
outQueue
(
self
)
:
# 對象出隊
if
self
.
end
==
-
1
:
raise
QueueException
(
'QueueEmpty'
)
else
:
element
=
self
.
Q
[
0
]
self
.
Q
=
self
.
Q
[
1
:
]
self
.
end
-=
1
return
element
if
__name__
==
'__main__'
:
q
=
Queue
(
)
# 入隊測試
for
i
in
range
(
10
)
:
q
.
inQueue
(
i
)
# 隊列滿測試
try
:
q
.
inQueue
(
1
)
except
Exception
as
e
:
print
(
e
)
# 出隊測試
for
i
in
range
(
10
)
:
print
(
q
.
outQueue
(
)
)
# 隊列空測試
try
:
q
.
outQueue
(
)
except
Exception
as
e
:
print
(
e
)
詳細版本見個人博客：Python用list實現堆棧和隊列
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
