操作受限的线性存储结构包括栈和队列。对于操作的限制是为了确保业务场景使用中的安全，确保不会被其他多余操作破坏。
栈
特点：先进后出、后进先出，只在一段插入和删除
实现：顺序栈、链式栈（动态扩容）
应用：函数调用栈、表达式求值、括号匹配、浏览器前进后退
- 函数调用栈
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈
- 表达式求值
使用两个栈实现，一个栈存储运算数，一个栈存储运算符。
依次读取表达式：
如果是数字存到运算数栈；
如果是运算符，与栈内前一个运算符比较优先级；
如果优先级高，则入栈；
如果优先级低，则取两个运算数进行计算，将结果压栈，再取一个运算符继续比较。
直到表达式结束，并且运算符只剩一个，做最后一次运算，得到结果。
- 括号匹配
从左往右匹配括号
如果是左括号则压入栈
如果是右括号则和栈顶的左括号比较
匹配则弹出栈顶元素，不匹配则判定失败
最后检查栈内元素是否为空，为空则匹配成功
- 浏览器前进后退
两个栈实现，第一个栈保存历史访问记录，当后退时，从第一个栈弹出记录，压入第二个栈。前进时，从第二个栈弹出记录，压入第一个栈。
队列
特点：先进先出，后进后出
实现：顺序队列，链式队列，循环队列，阻塞队列，并发队列
应用：对于大部分资源有限的场景，没有空闲资源时，都可以利用队列来实现请求排队
网友评论