Python中可以用list来模拟栈和队列:
isEmpty()
:判断栈是否为空isFull()
:判断栈是否已满push(element)
:向栈中添加一个值,注意栈是否为满的pop()
:从栈中弹出一个值,注意栈是否为空 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)
利用数组 Q[1..n] 来实现含有 n-1 个元素队列(保留一位元素用来判断队列空或满)。该列有一个属性 Q.head 指向队头元素,属性 Q.tail 指向下一个新元素将要插入的位置,列中的元素存放在位置 Q.head, Q.head+1, …, Q.tail-1 上。
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)