栈与队列通常放到一起来学习，也是基础中的基础，概念一定要十分的清晰明了

栈是先进后出的线性表

s.top():获取栈底元素
s.empty():判断栈是否为空
s.push():往栈中添加一个元素
s.pop():栈顶元素的弹出
s.size()：获取栈的长度

---

构建一个栈（基础）

class Stack(object):
    #定义初始化方法
    def __init__(self):
        #初始化一个空列表
        self.__list=[]

    # 入栈和出栈的函数体现了先进后出的理念
    # 入栈：将一个元素加入栈顶
    def push(self,item):
        self.__list.append(item)

    #出栈：将一个元素从栈顶删除
    def pop(self):
        return self.__list.pop()

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

    #判断栈是否为空
    def is_empty(self):
        return self.__list == []

    #计算栈的大小
    def size(self):
        return len(self.__list)

if __name__ == '__main__':
    stack=Stack()
    print('是否空栈吗',stack.is_empty())
    #压栈
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    print('是否空栈吗', stack.is_empty())
    print('栈的长度：',stack.size())
    #弹出
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    # 打印结果
    是否空栈吗 True
是否空栈吗 False
栈的长度： 4
4
3
2
1

队列是先进先出的线性表

q.front():获取队列的队头元素
q.push():在队尾添加一个新的元素进队列中
q.pop()：把我们的队头元素进行弹出
q.empty()：判断我们的队列是否为空
q.size():去求队列中的元素的个数

python标准库中包含四种队列：

1. queue.Queue
2. asyncio.Queue
3. multiprocessing.Queue
4. collections.deque

下面的这这张图很好的展示了这样的一个过程，它们的方式确实不太一样，不要弄混淆了

构建一个单端队列（基础必须掌握-顺序存储）

第一种创建方式：用列表创建

这个知识点是自己必须要掌握的点：将列表的末尾当作队列的头部，队列的尾部是列表下标为0的位置，主要实现以下几个函数：进队、出队、判断是否为空、计算队列的长度

class Queue:
    def __init__(self):
        self.queue=[]
    
    # 进队和出队的函数体现了队列的先进先出的特点
    # 进队：将元素添加到队尾
    def enqueue(self,item):
        self.queue.insert(0,item)  

    # 出队：将元素从队头删除
    def dequeue(self):
        self.queue.pop() 

    # 判断队列是否为空
    def is_empty(self):
        return self.queue==[]

    # 计算队列的大小
    def size(self):
        return len(self.queue)
    
if __name__ == '__main__':
    queue=Queue()
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    #判断队列是否空
    print(queue.is_empty())
    print('队列大小',queue.size())
    print('-----出队---------')
    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.dequeue())
# 打印结果如下：
False
队列大小 3
-----出队---------
None
None
None

第二种创建方式：python中的模块的方式

略

构建一个双端队列

这里既然讲到了双端队列的问题，就做一点相应的知识整理：
deque是双端队列（double-ended queue）的缩写，由于两端都能编辑(有两个头部和尾部，可以在双端进行数据的插入和删除)，deque既可以用来实现栈（stack）也可以用来实现队列（queue），栈与队列的完美结合。
deque支持丰富的操作方法，主要方法如图：
相比于list实现的队列，deque实现拥有更低的时间和空间复杂度。
list实现在出队（pop）和插入（insert）时的空间复杂度大约为O(n)，
deque在出队（pop）和入队（append）时的时间复杂度是O(1)。
细部剩余知识详见：
https://www.cnblogs.com/lincappu/p/12890765.html
https://www.jb51.net/article/183382.htm

第一种创建方式：用python内置的双端队列模块

创建双向对队列：

import collections
d = collections.deque()

append(往右边添加一个元素)

import collections
d = collections.deque()
d.append(1)
d.append(2)
print(d)
# 打印结果
deque([1, 2])

appendleft（往左边添加一个元素）

import collections
d = collections.deque()
d.append(1)
d.appendleft(2)
print(d)
# 打印结果
deque([2, 1])

clear(清空队列)

import collections
d=collections.deque()
d.append(1)
d.clear()
print(d)
# 打印结果
deque([])

copy(浅拷贝)

import collections
d=collections.deque()
d.append(1)
new_d=d.copy()
print(new_d)
# 打印结果
deque([1])

count(返回指定元素的出现次数)

import collections
d=collections.deque()
d.append(1)
d.append(1)
print(d.count(1))
# 打印结果
2

第二种创建方式：使用列表来创建

将列表的末尾作为双端队列的前端，列表中下标索引为0的位置作为双端队列的后端（和列表的模拟十分相似）

# 用列表来实现一个双端队列
class Deque:
    # 构造方法创建一个空列表
    def __init__(self):
        self.deque=[]
    
    # 向双端队列的两端添加元素
    # 通过append()向列表的末尾添加（即向双端队列的前端添加）
    # 通过insert()向列表的索引为0的位置添加（即向双端队列的后端添加）
    def addFront(self,item):
        self.deque.append(item)
    def addRear(self,item):
        self.deque.insert(0,item)
    
    # 通过pop()移除列表的末尾元素（即删除前端元素）
    # 通过pop(0)移除列表的索引为0的元素（即删除后端元素）
    def deleteFront(self):
        return self.deque.pop()
    def deleteRear(self):
        return self.deque.pop(0)
    
    # 返回双端队列的前端元素
    # 返回双端队列的后端元素
    def displayFront(self):
        return self.deque[len(self.deque)-1]
    def displayRear(self):
        return self.deque[0]

    # 判断双端队列是否为空
    def is_empty(self):
        return self.deque==[]
    
    # 返回双端队列的数目
    def size(self):
        return len(self.deque)
    

# 测试如下：
# 创建一个空的双端队列，即创建一个对象，对象名称=类名称()
d=Deque()
print(d.is_empty()) # 判断双端队列是否为空
print(d.size())  # 统计双端队列的长度
d.addFront(123)  # 向双端队列的前端添加元素
d.addFront(456)
d.addRear('xr')  # 向双端队列的后端添加元素
d.addRear('1996-07-26') 
print(d.size())
print(d.displayFront())
print(d.displayRear())
print('-------')
d.deleteFront()  # 删除双端队列的前端元素
print(d.size())
print(d.displayFront())
d.deleteRear()  # 删除双端队列的后端元素
print(d.size())
print(d.displayRear())
print(d.is_empty())
# 打印结果如下：
True
0
4
456       
1996-07-26
-------   
3
123       
2
xr
False

以下为主要的几道题目：

1. leetcoad155-最小栈（基础题）
2. leetcoad232-用两个栈实现队列（基础题）
3. leetcoad225-用队列实现栈（基础题）
4. leetcoad42-接雨水

leetcoad155-最小栈（easy-值得好好回顾）

1. 需要在常数时间内找到最小的元素，不能够使用遍历，遍历是O(n)级别的，通过辅助栈进行解决（空间换时间）:这里的理解非常到位，值得自己去整理与反思
2. 定义好两个栈
   1. 一个栈叫Stack,负责栈的正常操作
   2. 一个栈是min_stack，负责获取 stack 中的最小值(思路的重要性：遍历stack中的所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈)
3. 定义一个push函数:（针对普通栈和辅助栈都要执行：普通栈直接加入,最小栈看是不是比原来的元素更下再选择加入）
4. 定义一个pop函数：（针对普通栈和辅助栈都要执行：普通栈直接弹出，最小栈当顶元素和普通栈相等的时候才会弹出）
5. 定义一个top函数：在普通栈中操作，最后一个元素
6. 定义getmim函数：在最小栈中操作，最后一个元素

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        # 定义好两个栈，一个栈用作正常操作，一个栈用作获取栈中的最小值
        # stack普通栈，负责栈的正常进出
        self.stack=[]
        # min_stack：用栈顶来保存所有元素的最小值，负责获取和存储stack中的最小值
        self.min_stack=[]

    # 入栈
    def push(self, x: int) -> None:
        # 把先添加的元素放入到stack中
        self.stack.append(x)
        # 判断min_stack是否为空，如果为空，把新的元素添加进来
        if self.min_stack:
            # 获取min_stack的栈顶元素
            top = self.min_stack[-1]
            # 是否加入的元素是小于栈顶元素的
            if x<=top:
                self.min_stack.append(x)
        # 如果min_stack为空的话，直接把元素添加进去。
        else:
            self.min_stack.append(x)

    # 出栈
    def pop(self) -> None:
        # 记录此时出栈的元素
        x = self.stack[-1]

        # stack执行出栈操作
        self.stack.pop()

        # stack中的元素出栈，min_stack同步进行
        # 获取min_stack的栈顶元素
        top=self.min_stack[-1]
        #判断top 是否与stack中弹出的的元素相等，如果相等，需要把min_stack中的栈顶元素一并出栈
        if top ==x:
            self.min_stack.pop()

    # 获取栈顶元素
    def top(self) -> int:
        return self.stack[-1]

    # 获取栈中的最小元素
    def min(self) -> int:
        return self.min_stack[-1]

leetcoad232-用两个栈实现队列

这里的关键点我认为有以下几点：（看过动画之后一切都十分的明白了）

1. 一个栈负责压入元素，一个栈负责弹出元素（返回队首元素）
2. 压入元素很简单，但弹出元素就很讲究（弹出的过程中，如果不为空直接弹出元素，如果为空，一定要让进入的栈的全部元素都转移到弹出栈中再弹出元素）
   1. 如果负责弹出的栈有元素，直接弹出
   2. 如果发现进入的栈不为空，就不停的将一个栈的元素转移到另一个栈中

class MyQueue:
    def __init__(self):
        # 定义两个栈
        self.A,self.B=[],[]

    # 将元素推到队列的末尾
    def push(self, x: int) -> None:
        self.A.append(x)
 
    # 移除队首元素
    def pop(self) -> int:
        # 如果栈B为空
        if not self.B:
            while self.A:
                self.B.append(self.A.pop())
        return self.B.pop()
    
    # 返回队列开头的元素(pop和peek的区别，一个是删除，一个是返回)
    def peek(self) -> int:
        if not self.B:
            while self.A:
                self.B.append(self.A.pop())
        return self.B[-1]


    # 定义一个empy函数，如果为空返回true，如果不为空就返回false
    def empty(self) -> bool:
        # 判断是否两个栈都为空
        if not self.A and not self.B:
            return True
        else:
            return False

# 牛客网上也有相同的题
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        # stack1负责进栈
        # stack2负责出栈
        self.stack1 = []
        self.stack2 = []

    def push(self, node):
        # write code here
        # 将元素加入stack1中，表示队列的入队操作
        self.stack1.append(node)
        # print(self.stack1)
        return

    def pop(self):
        # return xx
        # 将stack2中的元素进行弹出，构成队列的队头元素（先进先出）
        # 如果stack2空的，只要stack1有元素，stack2就不断添加stack1弹出来的元素
        # 入股哟stack2不是空的，直接弹出就行
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
                #print(self.stack1)
                #print(self.stack2)
        return self.stack2.pop()

leetcoad225-用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
* void push(int x) 将元素 x 压入栈顶。
* int pop() 移除并返回栈顶元素。
* int top() 返回栈顶元素。
* boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：
* 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
* 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

leetcoad42-接雨水

题目描述：给定** n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水**。
示例：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
思路：这道题用到了单调递增栈的思想（之所以放在这里就是这个原因，题目本身并不简单，但是重在里面的思维的点）