栈

之前总结的队列是一种先进先出的数据结构，今天要总结的是一种后进先出的数据结构，也就是栈。
栈（Stack）我们又称之为堆栈，它是一种运算受限的线性表，仅允许在表的一端进行插入和删除操作。我们把允许进行插入和删除的这一端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。

示意图.png

python实现栈

#定义一个类
#coding=utf-8
class Stack(object):
    # 初始化栈为一个空列表
    def __init__(self):
        self.items = []

    # 判断栈是否为空，返回布尔值
    def is_empty(self):
        return self.items == []

    # 返回栈顶元素
    def peek(self):
        return self.items[len(self.items) - 1]

    # 返回栈的大小
    def size(self):
        return len(self.items)

    # 新的元素入栈
    def push(self, item):
        self.items.append(item)

    # 栈顶元素出栈
    def pop(self):
        return self.items.pop()

栈的应用-----解密回文

这里我们需要判断一个字符串是否是回文字符串，所谓的回文字符串是指正读和反读均相同的字符序列，比如'cssc','sqqqs','好不好'均是回文，通过栈我们很容易判断一个字符串是否是回文。

#定义函用于判断字符串是否是回文
def Is_Plalindrome(mychar):
    my_stack = Stack()
    lenth=len(mychar)
    mid=int((lenth/2))-1
    for i in mychar[0:mid+1]:
        my_stack.push(i)
    if lenth%2==0:
        nextone=mid+1
    else:
        nextone=mid+2
    for j in mychar[nextone:]:
        if j==my_stack.peek():
            my_stack.pop()
    if my_stack.size()==0:
        print("Yes,{} is Plalindrome!".format(mychar))
    else:
        print("No,{} isn't Plalindrome!".format(mychar))
            
        
    
if __name__ == "__main__":
    # 初始化一个栈对象
    mychar1='ahahahhhh'
    mychar2='ahaha'
    mychar3='ahha'
    mychar4='好不好'
    Is_Plalindrome(mychar1)
    Is_Plalindrome(mychar2)
    Is_Plalindrome(mychar3)
    Is_Plalindrome(mychar4)
  

运行结果.png