如何實現一個雙端隊列？
作者 | 小 K
出品 | 公衆號：小 K 算法 （ID：xiaok365）
01 故事起源
隊列是一種先進先出的數據結構。
一般通過數組實現。
還需要定義 2 個指針，頭指針和尾指針。
02 插入和刪除
2.1 插入
從隊尾 tail 處插入，再將 tail 指針後移。
2.2 刪除
從隊首 head 處取出元素，再將 head 指針後移。
但數組是定長的，如果多次插入刪除，tail 指針就會超出數組範圍，而前面其實還是有空間的，所以常用的還是循環隊列。
03 循環隊列
循環其實就是讓 head,tail 兩個指針在數組內循環移動，當移動到隊尾時就跳到隊首。
通過取模就可以實現循環。
當 head==tail 時，即爲隊空。
當 head==(tail+1)%n 時，即爲隊滿。如果隊列長度爲 n，則只能裝 n-1 個元素，最後一個元素要空着。因爲如果放入元素，tail 會和 head 重合，就無法判斷是隊空還是隊滿。
04 雙端隊列
普通隊列只能隊首出，隊尾進，但有時我們需要隊首和隊尾都能進出，即雙端隊列。
4.1 插入
隊首插入，則 head 指針前移；隊尾插入，則 tail 指針後移。
4.2 刪除
隊首刪除，則 head 指針後移；隊尾刪除，則 tail 指針前移。
05 代碼實現
實現一個模板，以後可重複利用。
先定義必要的方法和變量。
template<typename T>
class Deque {
public:
explicit Deque(int capacity);
void PushFront(const T &node);
void PushBack(const T &node);
T PopFront();
T PopBack();
T Front() { return data_[head_]; }
T Back() { return data_[(tail_ - 1 + capacity_) % capacity_]; }
bool IsNotEmpty() { return head_ != tail_; };
bool IsEmpty() { return head_ == tail_; }
bool IsFull() { return (tail_ + 1) % capacity_ == head_; };
int Size();
int Head() { return head_; }
int Tail() { return tail_; }
public:
int capacity_, head_, tail_;
T *data_;
};構造函數
template<typename T>
Deque<T>::Deque(int capacity) {
capacity_ = capacity;
head_ = tail_ = 0;
data_ = new T[capacity_];
}插入
template<typename T>
void Deque<T>::PushBack(const T &node) {
if (IsFull()) {
std::__throw_logic_error("queue is full");
}
data_[tail_] = node;
tail_ = (tail_ + 1) % capacity_;
}
template<typename T>
void Deque<T>::PushFront(const T &node) {
if (IsFull()) {
std::__throw_logic_error("queue is full");
}
head_ = (head_ - 1 + capacity_) % capacity_;
data_[head_] = node;
}刪除
template<typename T>
T Deque<T>::PopBack() {
if (IsEmpty()) {
std::__throw_logic_error("queue is empty");
}
tail_ = (tail_ - 1 + capacity_) % capacity_;
return data_[tail_];
}
template<typename T>
T Deque<T>::PopFront() {
if (IsEmpty()) {
std::__throw_logic_error("queue is empty");
}
head_ = (head_ + 1) % capacity_;
return data_[(head_ - 1 + capacity_) % capacity_];
}size 方法
template<typename T>
int Deque<T>::Size() {
if (head_ <= tail_) {
return tail_ - head_;
} else {
return tail_ + (capacity_ - head_);
}
}使用案例
int main() {
Deque<int> deq(10);
deq.PushBack(2);
deq.PushFront(1);
deq.PushFront(0);
deq.PushBack(3);
printf("head=%d tail=%d size=%d back=%d\n", deq.Head(), deq.Tail(), deq.Size(), deq.Back());
while (deq.Size() > 2) {
printf("%d\n", deq.PopBack());
}
deq.PushBack(2);
deq.PushFront(1);
deq.PushFront(0);
deq.PushBack(3);
printf("head=%d tail=%d size=%d front=%d\n", deq.Head(), deq.Tail(), deq.Size(), deq.Front());
while (deq.IsNotEmpty()) {
printf("%d\n", deq.PopFront());
}
return 0;
}完整代碼已放在 github，地址：https://github.com/xiaok365/algorithm-cpp/tree/main/deque
06 總結
隊列是非常基礎且重要的數據結構，雙端隊列屬於隊列的升級。很多的算法都是基於隊列來實現，例如搜索中的 bfs，圖論中的 spfa，計算幾何中的 melkman 等。隊列結構本身很簡單，如何使用纔是比較難的，一定要深刻理解，以後才能熟練應用到不同的模型中。
本文原創作者：小 K，一個思維獨特的寫手。
文章首發平臺：微信公衆號【小 K 算法】。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/0OLPETbf8l26NOddNjT6uA