如何做一家网站,深圳网站建设费用多少,广东智能网站建设质量保障,聊城手机网站建设解决方案一#xff0c;概述
队列这个概念非常好理解。你可以把它想象成排队买票#xff0c;先来的先买#xff0c;后来的人只能站末尾#xff0c;不允许插队。先进者先出#xff0c;这就是典型的“队列”。
二#xff0c;顺序队列和链式队列
队列和栈一样#xff0c;也是一种…一概述
队列这个概念非常好理解。你可以把它想象成排队买票先来的先买后来的人只能站末尾不允许插队。先进者先出这就是典型的“队列”。
二顺序队列和链式队列
队列和栈一样也是一种抽象的数据结构操作上具有“先进先出”的特性队列只允许在队首进行删除操作而在队尾进行插入操作。基于数组实现的顺序队列的C代码如下
// 用数组实现的队列
class ArrayQueue(){// 数组items数组大小n
private:int n 20;int head 0; // 队头下标int tail 0; // 队尾下标public:// 带参数的构造函数申请一个大小为 capacity 的数组ArrayQueue(int capacity){// items new int[capacity];vectorint items(capacity);n capacity;}// 入队bool enqueue(int item){if(tail n) return False;items[tail] item;tail;return True;}// 时间复杂度为O(1)的入队操作bool enqueue2(int item){// tail n表示队列末尾没有空间了if(tail n){// tail n head 0表示整个队列都占满了if(head 0) return False;// 数据搬移for(ihead; itail; i){items[i-head] items[i];}// 重新更新 head 和 tailtail tail - head; // tail - headhead 0; // 队首位置}items[tail] item;tail;return True;}// 出队bool dequeue(){// head tail 表示队列为空if (head tail) return null;int ret items[tail];head;return ret;}
}入队时间复杂度为 O(1)。分析大部分情况下入队操作时间复杂度为 O(1)只有在 tail 在末尾时( tailn )才进行数据迁移此时的入队操作时间复杂度为 O(n)根据均摊时间复杂度得到入队时间复杂度为 O(1)。
三循环队列
前面用数组实现队列当 tail n 时会有数据搬移操作。循环队列首尾相连用数组实现循环队列代码的关键在于判断队列满和空的条件。
非循环队列: 队满tail n队空head tail 循环队列 队满(tail 1) % n head队空head tail
基于数组实现的循环队列的C代码如下
// 用数组实现的循环队列关键在于创建队头和队尾下标
class CircularQueue(){
private:int n 12;int items[];// head表示队头下标tail表示队尾下标int head 0;int tail 0;
public:CircularQueue(int capacity){// items new int[capacty];vectorint items(capacity);n capacity;}// 入队函数bool enqueue(int item){// 队列满了if((tail1)%n head) return False;items[tail] item;tail (tail 1) % n}// 出队函数int dequeue(){// // 如果head tail 表示队列为空if(head tail) return null;int ret items[head];head (head 1) % n;return ret;}
}四阻塞队列和并发队列
阻塞队列就是入队、出队操作都可以阻塞简单来说就是队列为空时队首取数据会被阻塞队列为满时队尾插入数据会被阻塞直到队列有空闲数据才允许在队尾插入数据。使用阻塞队列结构可以轻松实现“消费者-生产者模型”。并发队列就是队列的操作多线程安全。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁但是锁粒度大并发度会比较低同一时刻仅允许一个存或者取操作。实际上基于数组的循环队列利用 CAS 原子操作可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
参考资料
《数据结构与算法之美》-队列
