详细版本见个人博客：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实现堆栈和队列
