这里重新学习一下栈和队列,栈是先进后出的,有点儿像弹夹中先压入的子弹后打出;队列是先进先出的,就像人排队一样。
在实现角度上看,栈和队列都可以有数组和链表两种形式:
- 数组结构实现较容易
- 用链表结构较复杂,牵扯到很多指针操作
1. 栈
栈的一些操作($O(1)$):
- pop 操作:从栈顶弹出元素
- top 或 peek 操作:获取最顶上元素
- push 操作:向栈顶压入元素
- size 操作:返回栈中元素个数
平时使用的递归函数实际上用到了提供的函数系统栈,递归的过程可以看做是递归函数一次进入函数栈的处理过程。
2. 队列
队列的一些操作($O(1)$):
- pop 操作:从队列头部弹出元素
- top 或 peek 操作:获取最头部元素
- push 操作:在队尾压入元素
- size 操作:返回队列中元素个数