栈stack和队列queue都是线性操作的子集。
stack只在表尾进行插入或者删除操作，是线性表。stack的尾端是栈顶（top），表头是栈底（bottom）。
S = （，，…，），是表里第一个元素，称其为栈底bottom元素，是栈顶top元素，按顺序入栈，退栈的第一个元素是栈顶元素。（怎么感觉栈是沸腾片那种，最先装进去的bottom要最后才能吃到，封装前放进去的那一片top，顾客是最先吃到的呢嘻嘻）
栈是LIFO（last in first out）。
在看大三学《数据结构》用的书，当时用C语言上机，现在只看懂大概，不会写了，泪目。
一、顺序栈与链栈栈有两种存储结构：顺序栈、链栈。
1.1 顺序栈栈的顺序结构是利用一组地址连续的存储单元一次存放栈底到栈顶的数据元素。C语言上是在此同时放一个指针（记作top）指示栈顶元素，base一直指着栈底，top = base是空栈。
python使用栈有三种操作：①stack=[]；②collections.deque；③queue.LifoQueue. 目的都是实现栈的操作，常用的操作有：empty()、push(a)、pop()、top()、size()，因为是栈，查找中间的栈得不断拿出来栈顶的。
python中栈的实现 - 老张哈哈哈 - 博客园栈是一种线性数据结构，用先进后出或者是后进先出的方式存储数据，栈中数据的插入删除操作都是在栈顶端进行，常见栈的函数操作包括 empty() – 返回栈是否为空 – Time Complexihttps://www.cnblogs.com/laozhanghahaha/p/12302836.html 老张哈哈哈的blog写得挺清楚的，我还是消化了一下。
1.1.1 stack=[]stack = [] #stack = list()
# append(a) instand push(a)
stack.append('I')
stack.append(2)
stack.append(['my', 'hometown'])
stack
Out[1]: ['I', 2, ['my', 'hometown']]
#At that time, top is ['my', 'hometown'] and bottom is 'I'
#If we pop elements, the rule is:
print(stack.pop())
['my', 'hometown']
print(stack.pop())
2
print(stack.pop())
I
not stack #empty?
Out[15]: True
1.1.2 collections.deque
collections我只用过计数器Counter，使用方式也放下面了。
Python collections.Counter()函数_沃特么.拆基.达柴机的博客-CSDN博客_counter()函数原文链接：https://blog.csdn.net/qwe1257/article/details/83272340Python collections.Counter用法什么是collectionsCounterCounter操作例子什么是collectionscollections在python官方文档中的解释是High-performance container datatypes，...https://blog.csdn.net/rocking_struggling/article/details/104851741 collections.deque能提供时间复杂度O(1)的append(a)和pop()，比用列表的时间复杂度O(n)优秀。
import collections #from collections import deque
stack = collections.deque() #stack = deque()
stack.append('hi')
stack.append('friend!')
type(stack[0])
Out[2]: str
type(stack)
Out[3]: collections.deque
print(stack.pop())
friend!
print(stack.pop())
hi
1.1.3 queue.LifoQueue
栈是LIFO的线性表，队列queue也是线性表，这样记忆挺好的。用queue.LifoQueue可以设置栈的大小（老张的例子设置了），可以不设。用put()放入元素，get()输出栈顶元素。
from queue import LifoQueue
stack = LifoQueue()
stack.put('good')
stack.put('boy')
type(stack[0])
#we will get → TypeError: 'LifoQueue' object is not subscriptable
type(stack)
Out[4]: queue.LifoQueue
print(stack.get())
boy
print(stack.get())
good
stack
Out[5]:
1.2 链栈
还没遇到相关的题目，留个白
二、栈的应用与对应的leetcode题目栈的应用挺多的，这几天在leetcode刷简单题经常遇到，从3月21日开始总结一下，没写的是暂时没有遇到，不代表不能用。
2.1 括号匹配检验（20、有效的括号）题目涉及到顺序和急迫匹配的问题。先搞懂什么算是有效，什么是无效。看题目给的输入和输出：
输入 s = "()"；s = "()[]{}"；s = "{[]}"。输出 都是true
输入 s = "(]"；s = "([)]"。输出 都是false
观察可知首先要有对应的括号匹配，其次后来者得匹配完了pop了，先来者才能匹配，有LIFO那味道了。例如s = "([)]"，（是第一个输入的，急切想与）匹配，但第二个输入的是[，现在最急切的变成 [ 匹配一个 ] ，此时）输入，与 [ 的需求不匹配，直接就false了。
按照这个思路，使用顺序栈是再好不过了。
但是怎么安排括号配对，需要用字典。字典我再看看，还不太会。哈希表和字典啥关系啊晕。
