栈

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。就像咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子，盘子洗净后，也只能摞在这一摞盘子的最上面。栈的基本操作有push()和pop()、peek()。所以栈又被称为LIFO表。堆与栈是C/C++语言内存管理和编译优化时使用的，在python里，递归层次太多，要改用堆栈，而不能用递归。

由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问。为了得到栈底的元素，必须先拿掉上面的元素。

入栈使用push()方法

入栈和出栈的过程

预览栈顶的元素

pop()方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了。

peek()方法则只返回栈顶元素，而不删除它。

为了记录栈顶元素的位置，同时也为了标记哪里可以加入新元素，我们使用变量top，当向栈内压入元素时，该变量增大；从栈内弹出元素时，该变量减小。

push()、pop()和peek()是栈的3个主要方法，但是栈还有其他方法和属性。

简单案例以及操作结果：

这里使用python的list对象模拟栈的实现：

栈应用

检查程序中成对的符号

用栈来检查符号是否成对。做一个空栈，如果字符是开放符号('({[')则将其push栈中。如果符号是个闭合符号(')]}'),则当栈空时报错，对应'()}'的错误。否则，将栈pop，如果弹出的符号不是对应的开放符号，则报错，对应'(}'的错误。文件末尾，如果栈为空，则报错，对应'({}'的错误。

进制转换

十进制转换二进制：把十进制转成二进制一直分解至商数为0。从最底左边数字开始读，之后读右边的数字，从下读到上。

后缀记法

使用一个栈，见到一个数时入栈，遇到一个运算符时就作用于从栈弹出的两个元素，将结果弹入栈中。中缀到后缀的转换：当读到一个操作数的时候，放到输出中。读到操作符(+,-,*,/)时，如果栈为空，则压入栈中，否则弹出栈元素放到输出中直到发现优先级更低的元素为止。读到'(',压入栈中，读到')',弹出栈元素并发到输出中直到发现'('为止。

队列

队列其实就是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出，这点和栈不一样。

PS：说一下在Python2.X的版本中队列模块是Queue，而Python3.X中的队列模块是queue，所以导入模块的时候请注意自己的Python环境

一个线性的数据结构

队列遵循FIFO的原则

队列头部为front，尾部为rear

队列操作举例

先进先出队列（FIFO）

class queue.Queue(maxsize=0)

Queue提供了一个基本的FIFO容器，使用方法很简单,maxsize是个整数，指明了队列中能存放的数据个数的上限。一旦达到上限，插入会导致阻塞，直到队列中的数据被消费掉。如果maxsize小于或者等于0，队列大小没有限制。

后进先出队列（LIFO）

class queue.LifoQueue(maxsize=0)

后进先出队列与栈的类似，使用也很简单

queue常用方法

讲到这里其实还有一种优先队列，小编留一个悬念，希望时刻关注小编，定期更新，点关注不迷路