<p id="169E3OQ6">作者 | 小K</p><p id="169E3OQ7">出品 | 公众号：小K算法 （ID：xiaok365）</p><p id="169E3OQG"><strong>0</strong><strong>1</strong></p><p id="169E3OQJ">故事起源</p><p id="169E3OQM">队列是一种先进先出的数据结构。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2F534b1b27j00ri8dho000hd200u000d7g00g20072.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OQU">一般通过数组实现。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2F777a6932j00ri8dho000fd200u000d6g00g20071.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OR6">还需要定义2个指针，头指针和尾指针。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2Fefj00ri8dho000id200u000evg00g2007y.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3ORJ"><strong>02</strong></p><p id="169E3ORM">插入和删除</p><p id="169E3ORP">2.1</p><p id="169E3ORQ"><strong>插入</strong></p><p id="169E3OS0">从队尾tail处插入，再将tail指针后移。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2F353f9aa7j00ri8dhp000ld200u000fdg00g20087.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OS8">2.2</p><p id="169E3OS9"><strong>删除</strong></p><p id="169E3OSF">从队首head处取出元素，再将head指针后移。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2F7f9d58f7j00ri8dhq000kd200u000f5g00g20083.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OSN">但数组是定长的，如果多次插入删除，tail指针就会超出数组范围，而前面其实还是有空间的，所以常用的还是循环队列。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2F3c7e55aej00ri8dhq000gd200u000fcg00g20087.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OT4"><strong>03</strong></p><p id="169E3OT7">循环队列</p><p id="169E3OTA">循环其实就是让head,tail两个指针在数组内循环移动，当移动到队尾时就跳到队首。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2Fd91664f0j00ri8dhq000hd200u000fig00g2008a.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OTI">通过取模就可以实现循环。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2F1cc239c6j00ri8dhr000vd200sz00edg00g2007y.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OTQ">当head==tail时，即为队空。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2Fb279b298j00ri8dhr000hd200t000eog00g20084.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OU2">当head==(tail+1)%n时，即为队满。如果队列长度为n，则只能装n-1个元素，最后一个元素要空着。因为如果放入元素，tail会和head重合，就无法判断是队空还是队满。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2F5f97c276j00ri8dhr000id200su00dxg00g2007q.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OUG"><strong>04</strong></p><p id="169E3OUJ">双端队列</p><p id="169E3OUM">普通队列只能队首出，队尾进，但有时我们需要队首和队尾都能进出，即双端队列。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2F60ef9f4cj00ri8dhs000jd200u000c9g00g2006k.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OUU">4.1</p><p id="169E3OUV"><strong>插入</strong></p><p id="169E3OV5">队首插入，则head指针前移；队尾插入，则tail指针后移。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2F91d49a0ej00ri8dht000pd200sz00eug00g20087.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3OVD">4.2</p><p id="169E3OVE"><strong>删除</strong></p><p id="169E3OVK">队首删除，则head指针后移；队尾删除，则tail指针前移。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2022%2F0915%2F6c4eb4e3j00ri8dhu000sd200t500f9g00g2008e.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="169E3P01"><strong>05</strong></p><p id="169E3P04">代码实现</p><p id="169E3P07">实现一个模板，以后可重复利用。</p><p id="169E3P08">先定义必要的方法和变量。</p><p id="169E3P0A">template&lt; typename T&gt;<br/>class Deque {<br/>public:<br/>explicit Deque(int capacity);<br/>void PushFront(const T &amp;node);<br/>void PushBack(const T &amp;node);<br/>T PopFront();<br/>T PopBack();<br/>T Front() { return data_[head_]; }<br/>T Back() { return data_[(tail_ - 1 + capacity_) % capacity_]; }<br/>bool IsNotEmpty() { return head_ != tail_; };<br/>bool IsEmpty() { return head_ == tail_; }<br/>bool IsFull() { return (tail_ + 1) % capacity_ == head_; };<br/>int Size();<br/>int Head() { return head_; }<br/>int Tail() { return tail_; }<br/>public:<br/>int capacity_, head_, tail_;<br/>T *data_;<br/>};<br/></p><p id="169E3P0B">构造函数</p><p id="169E3P0C">template&lt; typename T&gt;<br/>Deque::Deque( int capacity) {<br/>capacity_ = capacity;<br/>head_ = tail_ = 0;<br/>data_ = new T[capacity_];<br/>}<br/></p><p id="169E3P0D">插入</p><p id="169E3P0E">template&lt; typename T&gt;<br/>void Deque::PushBack( const T &amp;node) {<br/>if (IsFull()) {<br/>std::__throw_logic_error( "queue is full");<br/>}<br/>data_[tail_] = node;<br/>tail_ = (tail_ + 1) % capacity_;<br/>}<br/>template&lt; typename T&gt;<br/>void Deque::PushFront( const T &amp;node) {<br/>if (IsFull()) {<br/>std::__throw_logic_error( "queue is full");<br/>}<br/>head_ = (head_ - 1 + capacity_) % capacity_;<br/>data_[head_] = node;<br/>}<br/></p><p id="169E3P0F">删除</p><p id="169E3P0G">template&lt; typename T&gt;<br/>T Deque::PopBack() {<br/>if (IsEmpty()) {<br/>std::__throw_logic_error( "queue is empty");<br/>}<br/>tail_ = (tail_ - 1 + capacity_) % capacity_;<br/>return data_[tail_];<br/>}<br/>template&lt; typename T&gt;<br/>T Deque::PopFront() {<br/>if (IsEmpty()) {<br/>std::__throw_logic_error( "queue is empty");<br/>}<br/>head_ = (head_ + 1) % capacity_;<br/>return data_[(head_ - 1 + capacity_) % capacity_];<br/>}</p><p id="169E3P0I">size方法</p><p id="169E3P0J">template&lt; typename T&gt;<br/>int Deque::Size() {<br/>if (head_ &lt;= tail_) {<br/>return tail_ - head_;<br/>} else {<br/>return tail_ + (capacity_ - head_);<br/>}<br/>}<br/></p><p id="169E3P0K">使用案例</p><p id="169E3P0L">int main() {<br/>Deque deq(10);<br/>deq.PushBack( 2);<br/>deq.PushFront( 1);<br/>deq.PushFront( 0);<br/>deq.PushBack( 3);<br/>printf( "head=%d tail=%d size=%d back=%d 

”, deq.Head(), deq.Tail(), deq.Size(), deq.Back());
while (deq.Size() > 2) {
printf( “%d “, deq.PopBack());
}
deq.PushBack( 2);
deq.PushFront( 1);
deq.PushFront( 0);
deq.PushBack( 3);
printf( “head=%d tail=%d size=%d front=%d “, deq.Head(), deq.Tail(), deq.Size(), deq.Front());
while (deq.IsNotEmpty()) {
printf( “%d “, deq.PopFront());
}
return 0;
}

完整代码已放在github，地址：https://github.com/xiaok365/algorithm-cpp/tree/main/deque

06

总结

队列是非常基础且重要的数据结构，双端队列属于队列的升级。很多的算法都是基于队列来实现，例如搜索中的bfs，图论中的spfa，计算几何中的melkman等。队列结构本身很简单，如何使用才是比较难的，一定要深刻理解，以后才能熟练应用到不同的模型中。

不代表中科院物理所立场

如需转载请联系原公众号

来源：小k算法

编辑：just_iu

讯享网

1.

2.

3.

4.

5.

6.

7.

8.

9.