【算法4】--- 栈(python)

【算法4】--- 栈(python),第1张

目录:
    • 算法4 --- 栈(python)
      • :mushroom: `基本思想:`
      • :mushroom: `进栈出栈变换形式:`
        • 基本方法:
        • :orange_book: 代码示例:
        • :triangular_flag_on_post: 例子应用:one::
        • :bell: 思想:
        • :triangular_flag_on_post: 例子应用:two::

算法4 — 栈(python) 🍄 基本思想:
  • 栈(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())

运行结果:
[6, 5, 4]

🚩 例子应用1️⃣:

“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)
🚩 例子应用2️⃣:

星期天小哼和小哈约在一起玩桌游,他们正在玩一个非常古怪的扑克游戏——“小猫钓鱼”。游戏的规则是这样的:将一副扑克牌平均分成两份,每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上,然后小哈也拿出手中的第一张扑克牌,并放在小哼刚打出的扑克牌的上面,就像这样两人交替出牌。出牌时,如果某人打出的牌与桌上某张牌的牌面相同,即可将两张相同的牌及其中间所夹的牌全部取走,并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时,游戏结束,对手获胜。

先出队尾的牌,收牌是从前往后收,即[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)

* 第二个代码是按照《啊 哈 算法》这本书中的思想进行实现的。

* 桌子上的牌用栈表示,先进后出;手中的牌用队列表示,先进先出;有相同牌是用数组表示,即桶排序的思想很像。

💕 这些只是本人用来记录学习算法内容的一些笔记,用来监督自己学习的,有不对的地方望指正!


【参考文献】

  1. 啊哈磊,《啊哈!算法》,北京,人民邮电出版社.

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/718519.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-25
下一篇 2022-04-25

发表评论

登录后才能评论

评论列表(0条)

保存