- 算法4 --- 栈（python）
- :mushroom: `基本思想：`
- :mushroom: `进栈出栈变换形式：`
- 基本方法：
- :orange_book: 代码示例：
- :triangular_flag_on_post: 例子应用:one:：
- :bell: 思想：
- :triangular_flag_on_post: 例子应用:two:：
基本思想：
- 栈（stack）是限定仅在表尾进行插入和删除 *** 作的线性表。
- 栈是后进先出（Last In First Out, LIFO）的线性表，和队列顺序不同。
- 允许插入和删除的一端为栈顶（top），另一端为栈底（bottom），不含任何数据元素的为空栈。
- 栈的插入 *** 作，叫做进栈，也称为压栈、入栈。类似子d入壳。
- 栈的删除 *** 作，叫做出栈，也有的叫做d栈。如同子d出d夹。
进栈出栈变换形式：
举例来说，如果我们现在是有3个整形数字元素1、2、3依次进栈，会有那些出栈次序呢？
- 第一种： 1、2、3进，再3、2、1出。这种最简单，出栈次序为321.
- 第二种：1进，1出，2进，2出，3进，3出。这是进一个出一个，出栈次序为123.
- 第三种： 1进， 2进 ，2出，1出，3进，3出。出栈次序为213.
- 第四种：1进，1出，2进， 3进，3出，2出。出栈次序为132.
- 第五种：1进， 2进，2出， 3进，3出，1出。出栈次序为231.
基本方法：有没可能312这样的次序出栈呢？
答案肯定不可能。因为3先出栈，就意味着，3曾经进过栈，既然3进栈了，那也就意味着，1和2页进栈了，此时2一定在1上面，就是更接近栈顶，那么出栈只可能是321，不然不满足123依次进栈的要求，所以不会出现1比2先出栈的情况。
先通过python实现栈
栈的python实现
栈支持以下 *** 作:
Stack（） 创建一个空栈。不需要参数，且会返回一个空栈。
push（item）将一个元素添加到栈的顶端。他需要一个参数item，且无返回值。 （即进栈）
#pop（）将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容。 （即出栈）
peek（）返回栈顶端的元素，但是并不移除该元素。他不需要返回参数，也不会修改栈的内容。
isEmpty() 检查栈是否为空。它不需要参数，且会返回一个布尔值。
size（） 返回栈中元素的数目。它不需要参数，且会返回一个整数。
Class Stack: ##定义一个栈类
def __init__(self): ##初始化栈
self.items = []
def isEmpty(self): #判断是否为空
return self.items == []
def push(self,item): #进栈
self.items.append(item)
def pop(self): #出栈
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(slef): # 获取大小
return len(self.items)
进行调试
if __name__ == "__main__":
opstack = Stack() ## 建立一个空栈
a = [6,5,4]
opstack.push(a)
if not opstack.isEmpty():
print(opstack.pop())
🚩 例子应用1️⃣：运行结果：
[6, 5, 4]
🔔 思想：“xyzyx”是一个回文字符串，所谓回文字符串就是指正读反读均相同的字符序列，如“席主席”、“记书记”、“aha”和“ahaha”均是回文，但“ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。
- 首先我们需要读取这行字符串，并求出这个字符串的长度。
- 如果一个字符串是回文的话，那么它必须是中间对称的，我们需要求中点，即
mid = len / 2 -1
- 接下来将 mid 之前的字符全部入栈。
- 接下来进入判断回文的关键步骤。将当前栈中的字符依次出栈，看看是否能与 mid 之后
的字符一一匹配，如果都能匹配则说明这个字符串是回文字符串，否则这个字符串就不是回
文字符串。
具体代码如下：
def Palindrome_str(my_str):
L = len(my_str) #字符串长度
mid = len(my_str)/2 -1 #找出中间节点
## 后部分开始的起点位置
if L % 2 == 0:
next = int(mid) + 1
else:
next = int(mid) + 2
palindstack = Stack() ##创建空栈
## 特殊情况
if L <= 1:
print("{}是回文字符串".format(my_str))
return True
else:
for i in range(int(mid)+1): ## 前半部分入栈
str_bef = my_str[i]
print(str_bef)
palindstack.push(str_bef)
## 判断是否为回文
for j in range(next,L):
str_after = my_str[j]
print(str_after)
if str_after == palindstack.peek():
palindstack.pop()
else:
return False
if palindstack.isEmpty():
print("{} 是 回文字符串".format(my_str))
return True
if __name__ == "__main__":
s = "上海自来水来自海上"
# s = "haah"
ans = Palindrome_str(s)
print(ans)
上海自来水来自海上 是 回文字符串
True
haah 是 回文字符串
True
或者使用python自带的后进先出队列
# palindstack = Stack() ##创建空栈
palindstack = queue.LifoQueue() ##创建空栈
# palindstack.push(str_bef)
palindstack.put(str_bef)
# if str_after == palindstack.peek():
# palindstack.pop()
# else:
# return False
if str_after == palindstack.get():
continue
else:
return False
将上述代码进行相应更改即可
利用其他方法实现
def isParlinromic(my_str):
L = len(my_str) # 字符串长度
mid = len(my_str) / 2 - 1 # 找出中间节点
for i in range(int(mid)+1):
if my_str[i] != my_str[L-i-1]:
return False
return True
def isParlinromic02(my_str):
ls = list(my_str)
ls.reverse()
return my_str == "".join(ls)
def isParlinromic03(my_str):
return my_str == "".join(reversed(my_str))
def isParlinromic04(my_str):
return my_str == my_str[::-1]
if __name__ == "__main__":
# s = "上海自来水来自海上"
# s = "haah"
s = "hastah"
ans = isParlinromic03(s)
print(ans)
星期天小哼和小哈约在一起玩桌游，他们正在玩一个非常古怪的扑克游戏——“小猫钓鱼”。游戏的规则是这样的：将一副扑克牌平均分成两份，每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上，然后小哈也拿出手中的第一张扑克牌，并放在小哼刚打出的扑克牌的上面，就像这样两人交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时，游戏结束，对手获胜。
先出队尾的牌，收牌是从前往后收，即[3, 4, 5, 6, 4]，比如受理的牌为[1,2 ,5] 则收完[4, 5, 6, 4] 变为 [4, 5, 6, 4,1,2,5];
在出牌出的是队尾的牌，即 出的是： 5。
代码如下：
"""生成牌"""
card = []
# 生成牌
for i in range(1, 14):
if i == 1:
i = "A"
elif i == 11:
i = "J"
elif i == 12:
i = "Q"
elif i == 13:
i = "K"
"""同种牌4张，故添加4次"""
card.append(str(i))
card.append(str(i))
card.append(str(i))
card.append(str(i))
"""洗牌"""
for i in range(1000):
random.shuffle(card) # 1000次洗牌 保证牌够乱
"""发牌"""
n = int(len(card) / 2)
playerHa = card[:n]
playerHeng = card[n:]
# ## 测试数据
# playerHa = [2,4,1,2,5,6]
# playerHeng = [3,1,3,5,6,4]
"""展示两个人的牌"""
print("小哈的牌：",playerHa)
print("小哼的牌：",playerHeng)
"""模拟游戏过程"""
tmp = []
playercount = 0 ##记录谁出的牌
# desk_card = Stack()
def addCard(n):
global playerHa,playerHeng,tmp,playercount
playercount += 1
if n not in tmp: ## 如果没有相同的牌则把牌添加到tmp中
tmp.append(n)
print("桌上的牌：",tmp)
else:
tmp.append(n) # 如果在 先把牌添加到桌面上
nIndex = tmp.index(n) # 获取相同牌的索引
print('桌上的牌', tmp)
if playercount % 2 == 1: ## # 根据出牌计数器来判断是谁出的牌
playerHa = tmp[nIndex:] + playerHa
print('小哈的牌:', playerHa)
else:
playerHeng = tmp[nIndex:] + playerHeng # 把赢的牌添加到小哼手里中
print('小哼的牌:', playerHeng)
tmp = tmp[:nIndex] # 把已经赢的牌剔除
while True:
# 简化的代码
addCard(playerHa.pop())
addCard(playerHeng.pop())
if len(playerHa) == 0 or len(playerHeng) == 0:
print('游戏结束'.center(30, '*'))
if len(playerHa) > len(playerHeng):
print('小哈胜利')
print('小哈的牌:', playerHa)
print('小哼的牌:', playerHeng)
print('桌上的牌', tmp)
break
else:
print('小哼胜利')
print('小哼的牌:', playerHeng)
print('小哈的牌:', playerHa)
print('桌上的牌', tmp)
break
出牌时：队首先出，如【2,13,4】先出的是2
收牌时：如桌上已有牌：【2，3，4，5】这时出牌为3，则收牌为5，4，3的顺序收。
代码如下：
import pandas as pd
import numpy as np
import random
import queue
class Stack: ## 定义一个栈类
def __init__(self): ##初始化为空栈
self.items = []
def isEmpty(self): ## 判断空栈
return self.items == []
def push(self,item): ## 进栈
self.items.append(item)
def pop(self): ## 出栈
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self): ## 获取大小长度
return len(self.items)
"""生成牌洗牌发牌"""
def get_card():
"""生成牌"""
card = []
# 生成牌
for i in range(1, 14):
if i == 1:
i = "A"
elif i == 11:
i = "J"
elif i == 12:
i = "Q"
elif i == 13:
i = "K"
"""同种牌4张，故添加4次"""
card.append(str(i))
card.append(str(i))
card.append(str(i))
card.append(str(i))
"""洗牌"""
for i in range(100):
random.shuffle(card) # 1000次洗牌 保证牌够乱
playerHa = queue.Queue()
playerHeng = queue.Queue()
n = int(len(card) / 2)
Ha = card[:n]
Heng = card[n:]
for j in range(len(Ha)):
playerHa.put(Ha[j])
playerHeng.put(Heng[j])
return playerHa,playerHeng
def get_str_num(t):
num = 0
if t == "A":
num = 1
elif t == "J":
num = 11
elif t == "Q":
num = 12
elif t == "K":
num = 13
else:
num = int(t)
return num
def who_win(playerHa,playerHeng):
S = []
book = np.zeros(14)
while playerHa.qsize() != 0 and playerHeng.qsize() != 0:
"""小哼出牌"""
t = playerHeng.get()
num = get_str_num(t) ## 字母转换为数字
if book[num] == 0:
book[num] = 1
S.append(t) ## 桌上的牌
else:
playerHeng.put(t)
nIndex = S.index(t)
print("桌上的牌：", S)
print("相同的牌：", S[nIndex:][::-1])
for i in S[nIndex:][::-1]:
num = get_str_num(i) ## 字母转换为数字
book[num] = 0
print(i)
playerHeng.put(i)
# print(playerHa)
del S[nIndex:]
"""小哈出牌"""
t = playerHa.get()
num = get_str_num(t) ## 字母转换为数字
if book[num] == 0:
book[num] = 1
S.append(t)
else:
playerHa.put(t)
# pai = S.pop()
nIndex = S.index(t)
print("桌上的牌：", S)
print("相同的牌：", S[nIndex:][::-1])
for i in S[nIndex:][::-1]:
num = get_str_num(i) ## 字母转换为数字
book[num] = 0
playerHa.put(i)
# print(playerHa)
del S[nIndex:]
if playerHa.qsize() == 0:
print('游戏结束'.center(40, '*'))
print("小哼赢牌")
print("小哼手里的牌：")
while playerHeng.qsize() !=0:
print(playerHeng.get(),end=" ")
print("\n")
if len(S) == 0:
print("桌上已经没有牌了")
else:
print("桌上的牌：",S)
elif playerHeng.qsize() == 0:
print('游戏结束'.center(30, '*'))
print("小哈赢牌")
print("小哈手里的牌：")
while playerHa.qsize() != 0:
print(playerHa.get(),end=" ")
print("\n")
if len(S) == 0:
print("桌上已经没有牌了")
else:
print("桌上的牌：",S)
if __name__ == "__main__":
"""发牌"""
playerHa = get_card()[0]
playerHeng = get_card()[1]
"""游戏开始"""
who_win(playerHa, playerHeng)
* 第二个代码是按照《啊 哈 算法》这本书中的思想进行实现的。
* 桌子上的牌用栈表示，先进后出；手中的牌用队列表示，先进先出；有相同牌是用数组表示，即桶排序的思想很像。
💕 这些只是本人用来记录学习算法内容的一些笔记，用来监督自己学习的，有不对的地方望指正！
【参考文献】
- 啊哈磊，《啊哈！算法》，北京，人民邮电出版社.
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）