一、栈的应用：

栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。

例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。

栈还有一个著名的应用场景是面包屑导航，使用户在浏览页面时 可以轻松地回溯到上一级或更上一级页面。

二、队列的应用：

队列的输出顺序和输入顺序相同，所以队列通常用于对“历史”的回放，也就是按照“历史”顺 序，把“历史”重演一遍。

例如在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序 的。

再如网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存入队列的 顺序来依次抓取和解析的。

三、双端队列：

双端队列这种数据结构，可以说综合了栈和队列的优点，对双端队列来说，从队头一端可 以入队或出队，从队尾一端也可以入队或出队。

双端队列的实现：

class Deque(object):
    """双端队列"""
 
    def __init__(self):
        self.__list = []
 
    def add_front(self, item):
        """往队列的队头中添加一个item元素"""
        self.__list.insert(0, item)
 
    def add_rear(self, item):
        """往队列的队尾中添加一个item元素"""
        self.__list.append(item)
 
    def pop_front(self):
        """从队列头部删除一个元素"""
        return self.__list.pop(0)
 
    def pop_rear(self):
        """从队列头部删除一个元素"""
        return self.__list.pop()
 
    def is_empty(self):
        """判断一个队列是否为空"""
        return self.__list == []
 
    def size(self):
        """返回队列的大小"""
        return len(self.__list)
 

四、优先队列：

还有一种队列，它遵循的不是先入先出，而是谁的优先级最高，谁先出队。这种队列就是优先队列。

优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。关于优先队列的原理和使用情况，我们会在之后学习到。

五、栈、队列练习：

栈的入门：

1、括号匹配：

《LeetCode 20. 有效的括号》

分析：

由于每个元素最多入栈一次、出栈一次
故时间复杂度为O(n)

• 遇到左括号入栈
• 当出现右括号时，没有和它匹配的左括号，返回false
• 如果左右括号匹配，则直接出栈，消去一对括号；
• 不然，必然出现一个 右括号 没有相应的 左括号 进行匹配；
• 这时候如果栈为空，说明匹配完毕；否则，必然有左括号没有被匹配；

class Solution:
    def isValid(self, s)

        # 字符串有奇数个元素，不匹配
        if len(s) % 2 == 1:
            return False

        # 初始化栈
        stack = []

        pairs = {
            ')': '(',
            ']': '[',
            '}': '{'
        }

        for i in s:
            # 如果是左括号，压入栈
            if i not in pairs:
                stack.append(i)
            # 在遍历过程中，碰到空栈或者括号不匹配，返回 False。
            elif not stack or pairs[i] != stack.pop():
                return False

        # 全部遍历完，如果栈为空，返回 True，栈不为空，返回 False
        return not stack

2、回文链表：

《LeetCode 234. 回文链表》

在我们的生活中经常会碰到这种回文的结构，回文就是反转以后和以前一样的就是回文结构，例如 1->2->3->2->1，我们将它反转之后还是与原链表一样，我们就称这种链表结构为回文结构，那么如何来判断一个链表它是不是回文链表呢？

我们可以把链表存到栈中，利用栈后进先出的性质进行判定。

class Solution:
    def isPalindrome(self, head)
        stack = []
        # step1: push 
        curr = head
        while(curr):
            stack.append(curr)
            curr = curr.next
        # step2: pop and compare
        node1 = head
        while(stack):
            node2 = stack.pop()
            if node1.val != node2.val:
                return False
            node1 = node1.next
        return True

3、双栈判等：

《LeetCode 844. 比较含退格的字符串》

• 普通字符入栈，#出栈，注意判空操作；
• 然后就是对于两个字符串，判断它们生成的栈是否相等了。
• 对于字符串abc#d，最后得到的字符串为abd，如下图所示：

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def f(stack, word):
            for i in range(len(word)):
                if word[i] == '#':   #遇到退格键就pop
                    if stack != []:  #空的话就不动了
                        stack.pop()
                else:
                    stack.append(word[i])
            return stack
        
        return f([],s) == f([],t)