Python用list实现堆栈和队列
Python中可以用list来模拟栈和队列：
- 栈（stack）: 只能在一端进行数据操作，遵循后进先出（LIFO）原则
- 队列（queue）: 可以在两端进行数据操作，遵循先进先出（FIFO）原则，出队列的一端称为队首，入队列的一端称为队尾
栈
栈要记录的数据
- 栈顶位置 top：注意这个 top 有两种理解方式，一种是表示栈的最后一个数据的位置，另一种是表示栈的最后一个数据的下一个位置，这两种理解对栈的操作代码有一定的影响
- 栈最大大小 size
栈的操作
isEmpty()：判断栈是否为空isFull()：判断栈是否已满push(element)：向栈中添加一个值，注意栈是否为满的pop()：从栈中弹出一个值，注意栈是否为空
Python 列表实现栈
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 + 1if __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)队列
队列要记录的数据
- 队头位置 end
- 队列的大小 size
标准做法
利用数组 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 时，队列为满
队列的操作
- isEmpty()：判断队列是否为空
- isFull()：判断队列是否已满
- inQueue(element)：入队
- outQueue()：出队
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 elementif __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)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-11-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录