《数据结构与算法-王争》学习笔记,记录备查

基本概念

队列,一种先进先出的线性数据结构。和栈一样,是一种操作受限的线性表数据结构

用数组实现的队列叫做顺序队列,对链表实现的队列叫做链式队列

循环队列,首位相连的一种顺序队列。

阻塞队列,在队列基础上加上了阻塞操作,当队列空时,出队阻塞,当队列满时,入队阻塞。

并发队列,线程安全的队列。两种实现:

  • 简单的使用即为普通队列加了锁。
  • 利用CAS原子操作,可以实现非常高效的并发队列。

操作

队列的主要操作有:入队(enqueue)和出队(dequeue)。在队头插入元素,在队尾删除元素。

操作顺序队列时,出队相当于操作队列尾的元素,为了我们能够保持队列可用,在删除元素之后,我们需要将数据往队尾移动。这样删除元素的时间复杂度为O(n)。插入元素的时间复杂度为O(1)。

在删除时,我们可以暂时不移动元素,待队列满,无法继续入队之后,再把所有的数据往队尾移动一次。这样出队的时间复杂度为O(1)。

操作链式队列时,存储结构不是连续的,不必移动元素,所以入队和出队的时间复杂度都是O(1)。

循环队列可以避免数据的迁移,又是顺序队列,但是会浪费一个存储元素的空间。循环队列需要注意判空和判满的条件:

  • 判空:head == tail
  • 判满:(tail+1)%n == head

应用

  • 阻塞队列常用来解决一些因系统性能导致的问题。
  • 循环并发队列常用来解决一些缓存的底层存储问题。