队列
队列和栈类似,但是采用的是先进先出原则,只能从尾部添加新元素,并从顶部移除元素
数组实现
链式实现
双端队列
双端队列是一种允许从队头和队尾同时添加或移除元素的特殊队列,在某种意义上,这种混合线性结构提供了栈和队列的所有功能
循环队列
当队列的长度是固定的时候,会出现队尾追队头的现象,因为只能在有限的空间上进行入队操作
优先级队列
普通队列的元素都会被插入到队尾,优先级队列的元素再插入的同时会考虑该元素的优先级来决定它的位置
阻塞队列
并发队列
应用
回文检查
回文是一个字符串,距离首尾两端相同位置处的字符相同,例如 radar,sos,rustsur 这类字符串。直接使用队列进行入队出队操作,与原字符串的倒序比较,这种较为直观但是费空间,而双端队列非常适合
从左到右处理字符串,将每个字符添加到 Deque 尾部,此时 deque 的首部保存字符串的第一个字符,尾部保存最后一个字符。此时可以直接利用 Deque 的双边出队特性,删除首尾字符并比较,只有当首尾字符相等时才继续。如果可以持续匹配首尾字符,最终要么用完字符,留下空队列,要么留出大小为 1 的队列。在这两种情况下,字符串均是回文,这取决于原始字符串的长度是偶数还是奇数