设有两个栈S1和S2,它们都采用顺序栈存储,并且共享一个固定容量的存储区s[0..M-1],为了尽量利用空间,减少溢出的可能,请设计这两个栈的存储方式。
class DoubleStack:
"""双栈类"""
def __init__(self, m):
"""构造函数,m为双栈共享的内存大小(实为队列长度)"""
self.m = m # 队列长度
self.data = [None for i in range(m)] # 数据存储区
self.top1 = -1 # 栈1顶指针
self.top2 = m # 栈2顶指针
def s1_is_enmpty(self):
"""返回栈1是否空"""
return self.top1 == -1
def s2_is_enmpty(self):
"""返回栈2是否空"""
return self.top2 == self.m
def s1_is_full(self):
"""返回栈1是否满"""
return self.top1 == self.top2 - 1
def s2_is_full(self):
"""返回栈2是否满"""
return self.top2 == self.top1 + 1
def get_from_s1(self):
"""栈1出栈"""
if not self.s1_is_enmpty():
e = self.data[self.top1]
self.top1 -= 1
return e
else:
raise RuntimeError("S1已空")
def get_from_s2(self):
"""栈2出栈"""
if not self.s2_is_enmpty():
e = self.data[self.top2]
self.top2 += 1
return e
else:
raise RuntimeError("S2已空")
def push_to_s1(self, e):
"""栈1进栈"""
if not self.s1_is_full():
self.top1 += 1
self.data[self.top1] = e
else:
raise RuntimeError("S1已慢")
def push_to_s2(self, e):
"""栈2进栈"""
if not self.s2_is_full():
self.top2 -= 1
self.data[self.top2] = e
else:
raise RuntimeError("S2已慢")
if __name__ == '__main__':
ds = DoubleStack(3)
print(ds.s1_is_enmpty())
print(ds.s2_is_enmpty())
ds.push_to_s1('x')
ds.push_to_s2('1')
print(ds.s1_is_enmpty())
print(ds.s2_is_enmpty())
print(ds.s1_is_full())
print(ds.s2_is_full())
ds.push_to_s1('y')
print(ds.s1_is_full())
print(ds.s2_is_full())
print(ds.get_from_s1())