2.1栈(Stack)

特性 :后进先出的数据结构

常用方法:

Stack() 创建一个空的新栈。它不需要参数，并返回一个空栈。
push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
peek() 从栈返回顶部项，但不会删除它。不需要参数。不修改栈。
isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。
size() 返回栈中的 item 数量。不需要参数，并返回一个整数。

class Stack:
    def __init__(self):
        # 实例一个空列表对象
        self.items = []
        
    def isEmpty(self):
        # 判断列表中是否有值，空就返回True
        return self.items == []
    
    def push(self, item):
        # 从列表末尾添加数据
        self.items.append(item)

    def pop(self):
        # 列表方法pop会返回一个末尾已删除的值
        return self.items.pop()

    def peek(self):
        # 获取列表数据多少并取得最后一个
        return self.items[len(self.items) - 1]

    def size(self):
        # 返回列表数据的多少
        return len(self.items)


s = Stack()           # 实例化一个栈
print(s.isEmpty())    # 还没添加数据为True
print(s.push(1))      # 没有返回值None
print(s.pop())        # 返回已删除数据

View Code

应用:web浏览器的返回按钮的简单模拟

s = Stack()
def get_request(url):
    s.push(url)
    
def showCurrentPage():
    s.pop()
    
def back():
    print(s.pop())

get_request('www.1.com')
get_request('www.2.com')
get_request('www.3.com')

#显示当前页面
showCurrentPage()

#点击回退按钮
back()
back()

View Code

2.2队列(Queue)

特性 :先进先出

常用方法:

Queue() 创建一个空的新队列。它不需要参数，并返回一个空队列。
enqueue(item) 将新项添加到队尾。它需要 item 作为参数，并不返回任何内容。
dequeue() 从队首移除项。它不需要参数并返回 item。队列被修改。
isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。
size() 返回队列中的项数。它不需要参数，并返回一个整数。

class Queue():
    def __init__(self):
        self.items = []
        
    def enqueue(self):
        self.items.insert(0,item)
        
    def dequeue(self):
        return self.items.pop()
    
    def isEmpty(self):
        return self.items == []
    
    def size(self):
        return len(self.items)
    
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

View Code

应用:烫手的山芋

烫手山芋游戏介绍：6个孩子围城一个圈，排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋，需要在计时器计时1秒后将山芋传递给下一个孩子，依次类推。规则是，在计时器每计时7秒时，手里有山芋的孩子退出游戏。该游戏直到剩下一个孩子时结束，最后剩下的孩子获胜。请使用队列实现该游戏策略，排在第几个位置最终会获胜。
准则：队头孩子的手里永远要有山芋。

class Queue():
    def __init__(self):
        self.items = []
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

queue = Queue()
kids = ['A','B','C','D','E','F']
#将六个孩子添加在队列中,A是队头
for kid in kids:
    queue.enqueue(kid)
while queue.size()>1:
    #在7秒之内山芋会传递六次
    for i in range(6):
        kid = queue.dequeue()
        queue.enqueue(kid)
    queue.dequeue()    
print("获胜者是:", queue.dequeue())
# E

View Code

2.3双端队列(Dequeue)

同同列相比，有两个头部和尾部。可以在双端进行数据的插入和删除，提供了单数据结构中栈和队列的特性
常用方法:
- Deque() 创建一个空的新 deque。它不需要参数，并返回空的 deque。
- addFront(item) 将一个新项添加到 deque 的首部。它需要 item 参数并不返回任何内容。
- addRear(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。
- removeFront() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。
- removeRear() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。
- isEmpty() 测试 deque 是否为空。它不需要参数，并返回布尔值。
- size() 返回 deque 中的项数。它不需要参数，并返回一个整数。
```
class Dequeue():
    def __init__(self):
        self.items = []
        
    def isEmpty(self):
        return self.items == []
    
    def size(self):
        return len(self.items)
    
    def addFront(self,item):
        self.items.append(item)
        
    def addRear(self,item):
        self.items.insert(0,item)
        
    def removeFront(self):
        return self.items.pop()
    
    def removeRear(self):
        return self.items.pop(0)
```
View Code

应用: 回文检查

回文是一个字符串，读取首尾相同的字符，例如，radar toot madam。

def isHuiWen(s):
    ex = True
    q = Dequeue()
    #将字符串的每一个字符添加到双端队列中
    for ch in s:
        q.addFront(ch)
    for i in range(len(s)//2):
        font = q.removeFront()
        rear = q.removeRear()
        if font != rear:
            ex = False
            break
    return ex
    
print(isHuiWen('addan'))

View Code

python数据分析与算法之二栈和队列

2.1栈(Stack)

2.2队列(Queue)

2.3双端队列(Dequeue)

推荐阅读

python数据分析与算法之二 栈和队列

2.1栈(Stack)

2.2队列(Queue)

2.3双端队列(Dequeue)

推荐阅读

python数据分析与算法之二栈和队列