- 面向对象解决栈问题
- 什么是面向对象
- 语法
- 栈问题
- 解析
- 列队和栈
- 怎么用面向对象来解决这个问题
- 代码
- 源码参考
- 本文参考资料
面向对象的程序设计（Object Oriented Programming，OOP）简单来说就是以对象为中心来设计和开发程序，也就是说将实现的软件需求抽象成不同的对象和对象之间的交互过程。
语法class Name(Object):
pass
# Name: 类的名字（可以随便换, 但是开头要大写）
# Object: 父类名字（一般用Object）
栈问题
已知队列中有n个元素，栈的容量为n-1，将队列经过栈输出有多少种情况
解析 列队和栈- 列队(queue): 元素先进先出
- 可以用排队来类比
- 先来的人可以先到
- 栈(stack): 元素先进后出
- 可以用弹匣来类比
- 最先压入的子弹是最后打出的
- 先分析清楚有什么对象
- 一个能模拟元素入栈和入列的工具
- 这个对象能做什么
- 能接收一个元素并进行入列和入栈的操作
- 这个对象有什么属性
- 一个列队和一个栈
定义类的构造方法
class Simulator(object):
def __init__(self):
self.que = list()
self.stk = list()
# 这个init方法是在我们创建对象的时候自动调用的，不需要手动调用
定义入栈和入列的方法
函数在类里面就叫方法它的第一个参数一定为self然后是其他我们需要的参数
- eg:
class Name(object):
def __init__(self):
pass
def func(self, var):
pass
这个入列和入栈的方法我们需要两个参数，一个是self(一定要有)，另外一个是我们要进行入列和入栈的元素，则这个方法可以定义成这样
class Simulator(object):
def __init__(self):
self.que = list()
self.stk = list()
def inPut(self, seqv):
pass
我们继续来分析：
我们接收了一个元素后，既可以入栈也可以入列，但是只能先去一个地方。
eg:
我们第一个元素为0则有两种情况
que: [0] | []
stk: [] | [0]
第二个元素为1，在第一个元素的基础上会出现四种情况
que: [0, 1] | [1] | [0] | []
stk: [] | [0] | [1] | [0, 1]
我们可以发现，当第一次操作时，是加入由我们传入的元素构成的列表，和一个空列表，之后的操作是原有列表加上由我们传入的元素构成的列表，但是要注意que和stk索引值一样的列表一定是一一对应关系（que和stk索引值一样的列表里的所有元素一定为我们之前已经传入的元素）
到这里我们可以写出这个完整的函数
class Simulator(object):
def __init__(self):
self.que = list()
self.stk = list()
def inPut(self, seqv):
if not(self.que or self.stk): # 当两个列表都为空既第一次操作
self.que.append([seqv])
self.stk.append([])
self.que.append([])
self.stk.append([seqv])
else:
n = len(self.que)
for i in range(n):
# 注意: 一定要在加[:]，加上后会再生成一个列表并进行操作
# 否则python会直接引用源地址会引发错误
self.que.append(self.que[i][:])
self.stk.append(self.stk[i][:] + [seqv])
self.que[i] += [seqv]
定义已入栈出栈入列的方法
我们已经入栈的元素还可以出栈入列，变成一种新的情况
则有：
def out(self):
n = len(self.que)
for i in range(n):
q, s = self.que[i][:], self.stk[i][:]
q.append(s.pop()) # 出栈入列
self.que.append(q[:])
self.stk.append(s[:])
但是问题来了，每次只能出栈一个元素吗？
看以下情况：
que: []
stk:[1, 2, 3]
则有
que: [3] | [3, 2] | [3, 2, 1]
stk:[1, 2] | [1] | []
这样三种情况
所以一共要执行几次我们并不知道（因为栈里有多少元素我们并不知道）但是我们知道什么时候结束（当栈里没有元素的时候我们就可以停止了）
所以我们可以加上一个while循环，条件为len(s) > 0
def out(self):
n = len(self.que)
for i in range(n):
q, s = self.que[i][:], self.stk[i][:]
while len(s) > 0:
q.append(s.pop())
self.que.append(q[:])
self.stk.append(s[:])
但是还有一个问题，当有些元素放出后，会有重复的情况
比如
que: [] | [0]
stk: [0] | []
经过以上操作后会变为
que: [] | [0] | [0]
stk: [0] | [] | []
显然第三种情况和第一种重复了
所以我们的代码可以改成这样，去掉重复情况
def out(self):
n = len(self.que)
for i in range(n):
q, s = self.que[i][:], self.stk[i][:]
while len(s) > 0:
q.append(s.pop())
if q not in self.que:
self.que.append(q[:])
self.stk.append(s[:])
或者这样：
def out(self):
n = len(self.que)
for i in range(n):
q, s = self.que[i][:], self.stk[i][:]
while len(s) > 0:
q.append(s.pop())
self.que.append(q[:])
self.stk.append(s[:])
q, s, self.que, self.stk = self.que, self.stk, [], []
for i in range(len(q)):
if q[i] not in self.que:
self.que.append(q[i])
self.stk.append(s[i])
将结果输出
结果就是 列队 + 栈的倒序(因为栈是先进后出)
def outPut(self):
res = list()
for i in range(len(self.que)):
res.append(self.que[i][:] + self.stk[i][::-1])
return res
但是又同样的一个问题，会有重复的情况
eg:
que1: [1, 2]
stk1: [3, 4]
res1: [1, 2, 4, 3]
que2: [1, 2, 4]
stk2: [3]
res2: [1, 2, 4, 3]
这两个虽然是两个情况，但是结果是一样的，只要一个就好了
所以我们的代码可以改成这样
def outPut(self):
res = list()
for i in range(len(self.que)):
lis = self.que[i][:] + self.stk[i][::-1]
if lis not in res:
res.append(lis)
return res
至此我们的类就写完了，我们只要创建对象开始运算就好了
sim = Simulator() # 创建对象
seq = input().split(",") # 获得要排列的内容
seqv = [i for i in range(len(seq))] # 取出获得内容的下标
for i in seqv:
sim.inPut(i)
sim.out()
res = sim.outPut() # 获得结果并输出
for i in res:
for k in i:
print(seq[k], end="")
print()
print("共{}个".format(len(res)))
可能有人会问：为什么要取出下标值，不能直接用获取的内容
原因是这样：再获取的内容中会有重复的内容，但是下标不一样。直接用内容可能会被误判，直接去掉了这种情况，但是用下标不会出现这样的情况。
最后一个问题，这个顺序是乱的，我们想要更有序的输出怎么办？
解决这个问题我们只要写个排序函数就好了(或者用python内置的排序函数)
def sort(lis):
for i in range(len(lis) - 1):
for j in range(len(lis) - i - 1):
if lis[j] > lis[j + 1]:
lis[j], lis[j + 1] = lis[j + 1], lis[j]
return lis
然后加到我们的代码里就好了
res = sort(sim.outPut())源码参考
class Simulator(object):
def __init__(self):
self.que = list()
self.stk = list()
def inPut(self, seqv):
if not(self.que or self.stk):
self.que.append([seqv])
self.stk.append([])
self.que.append([])
self.stk.append([seqv])
else:
n = len(self.que)
for i in range(n):
self.que.append(self.que[i][:])
self.stk.append(self.stk[i][:] + [seqv])
self.que[i] += [seqv]
def out(self):
n = len(self.que)
for i in range(n):
q, s = self.que[i][:], self.stk[i][:]
while len(s) > 0:
q.append(s.pop())
self.que.append(q[:])
self.stk.append(s[:])
q, s, self.que, self.stk = self.que, self.stk, [], []
for i in range(len(q)):
if q[i] not in self.que:
self.que.append(q[i])
self.stk.append(s[i])
def outPut(self):
res = list()
for i in range(len(self.que)):
lis = self.que[i][:] + self.stk[i][::-1]
if lis not in res:
res.append(lis)
return res
def sort(lis):
for i in range(len(lis) - 1):
for j in range(len(lis) - i - 1):
if lis[j] > lis[j + 1]:
lis[j], lis[j + 1] = lis[j + 1], lis[j]
return lis
if __name__ == '__main__':
sim = Simulator()
seq = input().split(",")
seqv = [i for i in range(len(seq))]
for i in seqv:
sim.inPut(i)
sim.out()
res = sort(sim.outPut())
for i in res:
for k in i:
print(seq[k], end="")
print()
print("共{}个".format(len(res)))
运行结果：
- 《Python 3.7编程快速入门》（潘中强 薛燚 著）
- 第5章 类和对象
