算法4 — 栈（python）

基本思想：

• 栈（stack）是限定仅在表尾进行插入和删除操作的线性表。
• 栈是后进先出（Last In First Out, LIFO）的线性表，和队列顺序不同。
• 允许插入和删除的一端为栈顶（top），另一端为栈底（bottom），不含任何数据元素的为空栈。
• 栈的插入操作，叫做进栈，也称为压栈、入栈。类似子弹入壳。
• 栈的删除操作，叫做出栈，也有的叫做弹栈。如同子弹出弹夹。

进栈出栈变换形式：

举例来说，如果我们现在是有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. 啊哈磊，《啊哈！算法》，北京，人民邮电出版社.