从简单的线性数据结构开始：栈与队列
16lz
2021-01-22
栈与队列
栈 (Stack)是一种后进先出(last in first off，LIFO)的数据结构
队列(Queue)则是一种先进先出 (fisrt in first out，FIFO)的结构
动画如下：
栈
队列
栈 (Stack)
栈是一种线性结构，与数组相比，栈对应的操作是数组的子集。
它只能从一端添加元素，也只能从一端取出元素(这一端称之为栈顶)。
Stack这种数据结构用途很广泛，在计算机的使用中，大量的运用了栈，比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作（Undo）、浏览器中的回退操作，编译器中的函数调用实现等等。
栈的实现
| 接口 | 说明 | 复杂度 |
|---|---|---|
| void push(E e) | 向栈中加入元素 | O(1) 均摊 |
| E pop() | 弹出栈顶元素 | O(1) 均摊 |
| E peek() | 查看栈顶元素 | O(1) |
| int getSize() | 获取栈中元素个数 | O(1) |
| boolean isEmpty() | 判断栈是否为空 | O(1) |
说明：push和pop操作在最后面进行，有可能触发resize，但均摊来算是O(1)的。
如果你想了解更多时间复杂度的分析，欢迎关注笔者后续要更新的文章：O(n)说明的是什么问题？
栈的实现可以通过 数组 或者 链表 实现，在这里我们使用 数组来实现上述接口。
在栈的设计中，用户只关注栈顶元素存取和栈长度，因此设计代码如下：
读者可以使用 栈 这种数据结构去解决LeetCode上的第20号问题：有效的括号，也可以查看 每天一算：Valid Parentheses。
队列 Queue
队列也是一种线性数据结构，与数组相比，队列对应的操作是数组的子集。
只能从一端 (队尾) 添加元素，只能从另一端 (队首) 取出元素。
队列的应用可以在播放器上的播放列表，数据流对象，异步的数据传输结构(文件IO，管道通讯，套接字等)上体现，当然最直观的的就是排队了。
队列的实现
| 接口 | 说明 | 复杂度 |
|---|---|---|
| void enqueue(E e) | 入队 | O(1) 均摊 |
| E dequeue() | 出队 | O(n) |
| E getFront() | 获取队首元素 | O(1) |
| int getSize() | 获取队列元素个数 | O(1) |
| boolean isEmpty() | 判断队列是否为空 | O(1) |
入队是从队尾开始，有可能触发resize，因此均摊下来是O(1)。出队是在队首，数组实现每次都要挪动所有元素,O(n)。
更多相关文章
- 面试必知必会|堆和优先队列
- Python办公自动化｜光速对比并提取两份Word/Excel中的不同元素
- 动画：队列是如何处理大量任务分发的？
- 动画: 快速排序 | 如何求第 K 大元素？
- 如何保证消息队列的高可用？
- PHP 消息队列 Kafka 使用
- PHP 框架 Hyperf 实现处理超时未支付订单和延时队列
- 谈谈PHP中的多进程消费队列