数据结构-线性表 4.栈和队列
- 栈是限定仅在表尾进行插入和删除操作的线性表
- 队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表
- 队列先进先出,栈先进后出。
一、栈(java中Stack.class)
允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表
1、栈的顺序存储结构
如用数组实现
栈底是:下标为0的一端
2、栈的链式存储结构
链栈的入栈操作:
链栈的出栈操作:
3、栈的经典实用
3.1 逆波兰表达式法(逆波兰表达式也叫后缀表达式,先操作数,后操作符)
标准四则运算表达式—中缀表达式
计算机采用:后缀表达式:
计算规则:
1、符号不入栈,数字入栈
2、碰到符号出栈
中缀表达式转后缀表达式
数字输出,运算符进栈,括号匹配出栈,栈顶优先级低出栈
3.2 、逆序输出
栈最大的特点是先进后出,所以逆序输出是栈经常用到的一个应用场景。首先把所有元素依次入栈,然后把所有元素出栈并输出,这样就实现了逆序输出。
二、队列
- 队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表
插入的一端称为队尾,删除的一端称为队头
1、队列的顺序储存
缺点:出队复杂度高0(n)
容易假溢出,队尾插入了,但是队头很多空
2、循环队列(优化顺序存储)
把队列头尾相接的数据结构成为循环队列
3、队列的链式存储及结构模式(队列的最优方案)(java中LinkedList)
空队列: