数据结构与算法 编程语言 ·

算法学习之栈与队列

算法学习之队列

一、 Stack

0x1 数组的子集

  • 栈也是一种线性结构
  • 相比数组,栈对应的操作是数组的子集
  • 只能从一端添加元素,也只能从一端取出元素
  • 这一端称为栈顶
  • 栈是一种后进先出的数据结构
    • Last In First Out (LIFO)
  • 在计算机的世界里,栈拥有着不可思议的作用

0x2 栈的应用

  • 无处不在的Undo操作(撤销)
  • 程序调用的系统栈
  • 括号匹配 - 编译器

0x3 栈的实现

二、队列 Queue

0x1 站队

  • 队列也是一种线性结构
  • 相比数组,队列对应的操作是数组的子集
  • 只能从一端(队尾)添加元素,只能从另一端(队首)取出元素
  • 队列是一种先进先出的数据结构(先到先得) FIFO

0x2 队列的实现

0x3 数组队列

0x4 循环队列

数组队列的实现出队的操作的复杂度是O(n),为了使得效率更高,这里编写循环队列。底层的实现仍然是数组,此时复杂度是O(1)。

参与评论